#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPD(i, n) for (int i = (n) - 1; i >= 0; --i)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*
Phu Trong from Nguyen Tat Thanh High School for gifted student
*/
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
#define N 1000000
#define MAX 1000005
int numRadio, numQuery;
bool on[MAX];
int lp[MAX];
void init(void){
for (int i = 2; i * i <= N; ++i){
if(lp[i]) continue;
lp[i] = i;
for (int j = i * i; j <= N; j += i) {
if(!lp[j]) lp[j] = i;
}
}
for (int i = 2; i <= N; ++i) if (!lp[i]) lp[i] = i;
}
int seg[MAX * 2];
void upd(int p, int val){
for (seg[p += N] = val; p > 0; p >>= 1){
seg[p >> 1] = min(seg[p], seg[p ^ 1]);
}
}
int query(int l, int r){
int ID = 1e9;
for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1){
if (l & 1) minimize(ID, seg[l++]);
if (r & 1) minimize(ID, seg[--r]);
}
return ID;
}
set<int> st[MAX];
multiset<int> nxt[MAX];
void upd(int p){
if ((int)nxt[p].size()) upd(p, *nxt[p].begin());
else upd(p, 1e9);
}
void add(int x, int id){
while (x > 1){
int d = lp[x];
while (x % d == 0) x /= d;
auto it = st[d].lower_bound(id);
assert(*it != id);
int f = 0;
if (it != st[d].end()){
nxt[id].insert(*it);
upd(id);
f = *it;
}
if (it != st[d].begin()){
it = prev(it);
nxt[*it].insert(id);
if (f) nxt[*it].erase(nxt[*it].find(f));
upd(*it);
}
st[d].insert(id);
}
}
void sub(int x, int id){
while (x > 1){
int d = lp[x];
while (x % d == 0) x /= d;
auto it = st[d].lower_bound(id);
assert(*it == id);
int f = 0;
if (next(it) != st[d].end()){
nxt[id].erase(nxt[id].find(*next(it)));
f = *next(it);
upd(p);
}
if (it != st[d].begin()){
nxt[*prev(it)].erase(nxt[*prev(it)].find(id));
if(f)
nxt[*prev(it)].insert(f);
upd(*prev(it))
}
st[d].erase(id);
}
assert(nxt[id].size() == 0);
}
void process(void){
cin >> numRadio >> numQuery;
memset(seg, 0x3f, sizeof seg);
for (int i = 1; i <= numQuery; ++i){
char c; cin >> c;
if(c == 'S'){
int x; cin >> x;
if(on[x]) sub(x, x);
else add(x, x);
on[x] = !on[x];
}
else{
int l, r; cin >> l >> r;
int ID = query(l, r);
cout << (ID <= r ? "DA\n" : "NE\n");
}
}
}
signed main(){
#define name "Whisper"
cin.tie(nullptr) -> sync_with_stdio(false);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
init();
process();
}
Compilation message
Main.cpp: In function 'void sub(int, int)':
Main.cpp:117:17: error: 'p' was not declared in this scope
117 | upd(p);
| ^
Main.cpp:124:27: error: expected ';' before '}' token
124 | upd(*prev(it))
| ^
| ;
125 | }
| ~
