题意

对于集合S，有两种操作：1、B X；2、A Y。B X代表将X加入集合S，并赋予X一个序号，代表它是第几个数；A Y代表从集合S中找出mod Y最小的数，输出的是该数的序号。

做法

非常厉害的一个题。

对 y 进行讨论，小的 y 每次加数的时候暴力更新，而大的 y 转换成 rmq 问题。
（这个我觉得是这题的难点，对于取模操作我很难去往看起来复杂度更高的 rmq 上面想。）

注意到这个 rmq 我们是可以离线的，而对于静态的问题是可以单调栈的（参考之前的 O(n)-O(1) 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("");
    }

}

Posted by xiaodao
Category: 日常