题解：P9986 [Ynoi2079] r2pspc

Seauy · 2025-03-03 21:53:28 · 题解

给个理论打不过 O(n\sqrt q)，实测干不过 O(\frac{nq}{w})，但可能有点意思的做法。

首先值域可以简化成严格 n 之内，方法是把暴力计算 \sum_{i=1}^n 2^{a_i} 时始终没变化的位全删掉。

然后考虑对一个数加 2^{a_i} 究竟在干啥，就是将最低的比 a_i 高的 0 和中间连续的 1 分别变为 1 和 0。如果我们能快速维护出连续 1 段并支持单点改，或许就能用莫队做出来了。

当只有二进制加法时，每次操作改变的位数是 O(1) 的，因此考虑不删莫队。在莫队右端点拓展的时候，我们可能会合并两段、在某段删除插入一个元素，容易想到直接用并查集维护。由于要删除元素所以改成 leafy 的，也就是代表 n 个二进制位的结点全是叶子，中间结点是辅助维护联通性的。这么做的正确性一在于每次插入或删除的元素都在段的边缘（不用支持分裂段），二是删除元素不会增加并查集势能，所以均摊复杂度还是对的。

不过拓展左端点时就不能在并查集上做修改操作了，否则需要撤销复杂度就不对了。发现如果加入的 2^{a_i} 是严格递减的就很容易维护，因为后面加入 2^{a_i} 涉及的连续 1 段有多长，只跟 a_i 在并查集中所处的段，以及上次加入 2^{a_j} 后 a_j 所在的段如何有关。所以把块中所有 a_i 排序，查询时从大到小扫，处理出块内 \sum 2^{a_i} 从高到低哪些二进制位为 1，就能只用并查集 Find 算出答案了。

路径压缩+按秩合并就能做到单次查询/修改均摊 O(\alpha(n))，至于这玩意能否改成 O(1)，反正直接序列线性并查集是不对的，因为并查集结点数量并非 \frac{n}{w}。丘老师指出：

我没看懂 /ll

时间 O(n\sqrt q\ \alpha(n)+q)，空间 O(n+q)。容易发现题解区只有 bitset 的做法给了代码，所以我喜提最劣解。参考代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5,MAXM=1e6,SIZE=2e5;

int Read()
{
    int res=0;char c;
    while(!isdigit(c=getchar()));
    while(isdigit(c)) res=res*10+c-'0',c=getchar();
    return res;
}
void Print(int x)
{
    if(x<10) {putchar('0'+x);return;}
    int y=x/10; Print(y),putchar('0'+x-y*10);
}

int n,m,A[MAXN+5],Q[MAXN+5];
int ql[MAXM+5],qr[MAXM+5],ans[MAXM+5];
bool B[MAXN+5];int tim[MAXN+5],T;
int stk[MAXN+5],tp;
int S,Bloc[MAXN+5];

bool cmp(int a,int b) {return A[a]<A[b];}

int Head[MAXN+5],nxt[MAXM+5];
void Insert(int x,int v) {nxt[v]=Head[x],Head[x]=v;}

int fa[SIZE+5],h[SIZE+5],lef[SIZE+5],tot;
int Find(int x) {return fa[x]==x ? x : fa[x]=Find(fa[x]);}
int Union(int a,int b)
{
    a=Find(a),b=Find(b);
    lef[b]=lef[a];
    if(h[a]<h[b]) swap(a,b);
    fa[b]=a,h[a]=max(h[a],h[b]+1);
    return a;
}

int main()
{
    n=Read(),m=Read();
    for(int i=1;i<=n;i++) A[i]=Read(),Q[i]=i;
    sort(Q+1,Q+n+1,cmp);
    for(int i=1,j,cnt=0,rnk=1;i<=n;i=j)
    {
        j=i; while(j<=n && A[Q[j]]==A[Q[i]]) ++j;
        int d=A[Q[j]]-A[Q[i]];
        for(int k=i;k<j;k++) A[Q[k]]=rnk;
        cnt+=j-i;
        rnk+=min(cnt,d),cnt=max(0,cnt-d);
    }
    S=ceil(1.0*n/sqrt(m));
    for(int i=1,L=1,R;L<=n;i++,L=R) {R=min(n+1,L+S); for(int j=L;j<R;j++) Bloc[j]=i;}
    for(int i=1;i<=m;i++)
    {
        ql[i]=Read(),qr[i]=Read();
        if(Bloc[ql[i]]==Bloc[qr[i]])
        {
            ++T;
            for(int j=ql[i];j<=qr[i];j++)
            {
                int x=A[j];
                while(tim[x]==T && B[x]) --ans[i],B[x++]=0;
                ++ans[i],tim[x]=T,B[x]=1;
            }
        }
        else Insert(qr[i],i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=Head[i],k;j;j=k) k=nxt[j],Insert(Bloc[ql[j]],j);
        Head[i]=0;
    }
    stk[0]=n+1;
    for(int i=1,L=1,R;L<=n;i++,L=R+1)
    {
        R=min(n,L+S-1);
        if(!Head[i]) continue;
        for(int j=1;j<=S;j++) Q[j]=L+j-1;
        sort(Q+1,Q+S+1,cmp);
        for(int j=1;j<=n+1;j++) fa[j]=j; tot=n+1;
        int pre=0;
        for(int j=Head[i],k;j;pre=j,j=k) k=nxt[j],nxt[j]=pre;
        Head[i]=pre;
        int MoR=R,cnt=0;
        for(int j=Head[i];j;j=nxt[j])
        {
            while(MoR<qr[j])
            {
                int x=A[++MoR];
                if(fa[x]==x)//zero
                {
                    if(fa[x-1]!=x-1)
                    {
                        if(fa[x+1]!=x+1) fa[x]=Union(x+1,x-1);
                        else lef[fa[x]=Find(x-1)]=x;
                    }
                    else if(fa[x+1]!=x+1) fa[x]=Find(x+1);
                    else fa[x]=++tot,fa[tot]=tot,h[tot]=1,lef[tot]=x;
                }
                else
                {
                    lef[Find(x)]=x-1;
                    while(fa[x]!=x) fa[x]=x,--cnt,++x;
                    if(fa[x+1]!=x+1) fa[x]=Find(x+1);
                    else fa[x]=++tot,fa[tot]=tot,h[tot]=1,lef[tot]=x;
                }
                ++cnt;
            }
            tp=0;
            for(int k=S;k;k--)
                if(Q[k]>=ql[j])
                {
                    int x=A[Q[k]];
                    while(stk[tp]==x) --tp,++x;
                    stk[++tp]=x;
                }
            ans[j]=cnt;
            int lst=n;
            for(int k=1;k<=tp;k++)
                if(fa[stk[k]]==stk[k])
                {
                    ++ans[j];
                    if(stk[k-1]==stk[k]+1) continue;
                    if(fa[stk[k]+1]==stk[k]+1) {lst=stk[k];continue;}
                    int x=Find(stk[k]+1);
                    if(Find(stk[k-1]-1)!=x) lst=lef[x];
                }
                else
                {
                    int x=Find(stk[k]);
                    if(Find(stk[k-1]-1)==x) ans[j]-=lst-stk[k];
                    else ans[j]-=lef[x]-stk[k];
                    lst=stk[k]-1;
                }
        }
    }
    for(int i=1;i<=m;i++) Print(ans[i]),putchar('\n');
    return 0;
}