# 某岛

… : "…アッカリ～ン . .. . " .. .
May 12, 2023

# HDU 3303. Harmony Forever

## 做法

（这个我觉得是这题的难点，对于取模操作我很难去往看起来复杂度更高的 rmq 上面想。）

```const int N = int(4e4) + 9, M = int(5e5) + 9, SM = 1009;
char T[N]; int n, A[N], AA[N], P[M+1], id[M], nn;
VI res;

int Find(int x){
return P[x] == x ? x : P[x] = Find(P[x]);
}

void Union(int x, int y){
x = Find(x), y = Find(y);
assert(x != y);
P[x] = y;
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

//cout << sqrt(M) << endl;

int __size__ = 256 << 20; // 256MB
char *__p__ = (char*)malloc(__size__) + __size__;
__asm__("movl %0, %%esp\n" :: "r"(__p__));

while(RD(n)){

printf("Case %d:\n", ++Case);

nn = 0; REP_1(i, M) P[i] = i;

RST(id); REP_1(i, n){
RC(T[i]); RD(A[i]);
if (T[i] == 'B') AA[++nn] = A[i], id[A[i]] = -nn;
}

FOR(i, 1, M){
if (!id[i]) Union(i, i+1);
}

CLR(res); DWN_1(i, n, 1) if (T[i] == 'B'){
Union(A[i], A[i]+1);
--nn;
}
else{

int r = A[i]; if (Find(1) == M){
res.PB(-1);
continue;
}

if (r < SM){
PII ar = MP(INF, 0);
DWN_1(t, nn, 1){
checkMin(ar, MP(AA[t]%r, -t));
if (!ar.fi) break;
}
res.PB(-ar.se);
continue;
}

PII a=MP(INF,0); int tt;

for(int it=Find(1);it!=M;it=Find(min(M, it+(r-tt)))){
checkMin(a, MP(tt=it%r, id[it]));
}
res.PB(-a.se);
}

RVS(res); ECH(it, res) OT(*it);
puts("");
}

}
```