This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll maxn = 1e5 + 3;
const ll mod = 1e9 + 7;
int n, Q, prime[maxn];
bool vis[maxn];
multiset<int>st[4 * maxn];
void sang()
{
for(int i = 1 ; i <= n ; ++i) prime[i] = i;
for(ll i = 2 ; i <= n ; ++i)
{
if(prime[i] == i)
for(ll j = i * i ; j <= n ; j += i)
prime[j] = i;
}
}
void constructST(int si, int l, int r)
{
if(l == r)
{
while(l != 1)
{
int so = prime[l];
st[si].insert(so);
while(l % so == 0)
{
l /= so;
}
}
return;
}
ll mid = (l + r) / 2;
constructST(si * 2, l, mid);
constructST(si * 2 + 1, mid + 1, r);
}
int get(int si, int sl, int sr, int l, int r)
{
if(l <= sl && sr <= r)
{
auto it = st[si].begin();
while(it != st[si].end())
{
int so = (*it);
++it;
if(it != st[si].end() && (*it) == so)
{
return 1;
}
}
return 0;
}
if(l > sr || r < sl) return 0;
ll mid = (sl + sr) / 2;
return get(si * 2, sl, mid, l, r) + get(si * 2 + 1, mid + 1, sr, l, r);
}
vector<int>q;
void update(int ty, int si, int sl, int sr, int pos)
{
if(sl > pos || sr < pos) return;
if(sl == sr)
{
for(auto it = st[si].begin() ; it != st[si].end() ; ++it)
q.push_back((*it));
return;
}
ll mid = (sl + sr)/2;
update(ty, si * 2, sl, mid, pos);
update(ty, si * 2 + 1, mid + 1, sr, pos);
if(ty == 1) for(int so : q) st[si].insert(so);
else for(int so : q) st[si].erase(st[si].find(so));
}
void sub2()
{
sang();
constructST(1, 1, n);
while(Q--)
{
char ty;
cin>>ty;
if(ty == 'S')
{
int x;
cin>>x;
q.clear();
vis[x] = 1 - vis[x];
update(vis[x], 1, 1, n, x);
}
else
{
int l, r;
cin>>l>>r;
if(l == r)
{
cout<<"NO"<<'\n';
continue;
}
int ans = get(1, 1, n, l, r);
if(ans) cout<<"YES";
else cout<<"NO";
cout<<'\n';
}
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void sub1()
{
while(Q--)
{
char ty;
cin>>ty;
if(ty == 'S')
{
int x;
cin>>x;
vis[x] = 1 - vis[x];
}
else
{
int l, r;
cin>>l>>r;
if(l == r)
{
cout<<"NO"<<'\n';
continue;
}
for(int i = l ; i <= r ; ++i)
{
if(vis[i])
{
for(int j = i + 1 ; j <= r ; ++j)
if(vis[j] && __gcd(i, j) != 1)
{
cout<<"YES"<<'\n';
goto done;
}
}
}
cout<<"NO"<<'\n';
done:
;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("RADIO.INP","r",stdin);
// freopen("RADIO.OUT","w",stdout);
cin>>n>>Q;
if(n <= 100 && Q <= 200) sub1();
else sub2();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |