题解：P8419 [THUPC 2022 决赛] riapq

· · 题解

不弱于区间逆序对，考虑以 S=\mathcal{O}(\sqrt{n}) 为块长分块。

记 f_x(l,r) 为区间 [l,r] 中 \le a_x 的点数。

那么修改就是对于 [l,r] 中的 b_x \gets b_x+f_{x}(l,x)。考虑差分有 f_{x}(1,x)-f_{x}(1,l-1)。

对于 f_{x}(1,x)，只有 \mathcal{O}(n) 个不同情况，直接数点求出每个 f_{x}(1,x)，然后在查询乘上出现次数加上。

对于 f_{x}(1,l-1)，考虑 [1,l) 中的每个整块，利用树状数组记录该块对每个 b_i 的贡献次数，查询时乘上贡献大小加上。

考虑 [1,l) 中的散块，考虑其对 [l,r] 中的整块的贡献，我们在每个块中开一个树状数组记录插入的数中 \le x 的数的出现次数，直接序列维差分一下，只有 \mathcal{O}(\sqrt{n}) 次树状数组。

散块对散块的贡献，直接暴力树状数组即可。被卡常的话可能要换成归并排序。

总的时间复杂度为 \mathcal{O}(n\sqrt{n}\log n)，但是这个做法被卡常了。

#include<bits/stdc++.h>
#define ll long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    unsigned int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=200003,block=1000,S=N/block+3;
int n,m,tot,c,sa,sb;ll b[N];
int p[N],A[N],B[N],a[N],f[N],bl[N],L[S],R[S],w[S][N];
inline int get(int x,int y){return __builtin_popcountll(x&(((y&63)==63?0:(1ull<<((y&63)+1)))-1));}
struct BIT
{
    int c[N];
    inline void add(int x){for(;x<=n;x+=x&-x)++c[x];}
    inline void del(int x){for(;x<=n;x+=x&-x)--c[x];}
    inline int ask(int x){int s=0;for(;x;x^=x&-x)s+=c[x];return s;}
}s[S],g[S],G;
inline bool cmp(int x,int y){return a[x]<a[y];}
inline void merge(){for(int i=1,j=1;i<=sb;b[B[i]]+=j-1,++i)while(j<=sa&&a[A[j]]<=a[B[i]])++j;}
inline void add(int l,int r)
{
    c=l-1,G.add(l),G.del(r+1);if(!c)return;sa=sb=0;
    for(int i=1;i<bl[c];++i)g[i].add(l),g[i].del(r+1);
    if(bl[l]==bl[r]){for(int i=L[bl[l]];i<=R[bl[l]];++i)if(p[i]>=l&&p[i]<=r)B[++sb]=p[i];}
    else
    {
        if(bl[l]+1<bl[r])for(int i=L[bl[c]];i<=c;++i)s[bl[l]+1].add(a[i]),s[bl[r]].del(a[i]);
        int p1=L[bl[l]],p2=L[bl[r]];
        while(p1<=R[bl[l]]||p2<=R[bl[r]])
            if(p[p1]<l)++p1;
            else if(p[p2]>r)++p2;
            else if(p1>R[bl[l]])B[++sb]=p[p2++];
            else if(p2>R[bl[r]]||a[p[p1]]<a[p[p2]])B[++sb]=p[p1++];
            else B[++sb]=p[p2++];
    }
    for(int i=L[bl[c]];i<=R[bl[c]];++i)if(p[i]<=c)A[++sa]=p[i];
    merge();
}
inline ll ask(int x)
{
    ll res=1ll*f[x]*G.ask(x)-b[x],v=a[x];
    for(int i=1;i<bl[x];++i)res-=1ll*g[i].ask(x)*w[i][v]+s[i].ask(v);
    res-=s[bl[x]].ask(v);
    return res;
}
signed main()
{
    n=rd,m=rd,tot=(n-1)/block+1;
    for(int i=1;i<=tot;++i)L[i]=R[i-1]+1,R[i]=i*block;R[tot]=n;
    for(int i=1;i<=n;bl[i]=(i-1)/block+1,p[i]=i,++i)a[i]=rd;
    for(int i=1;i<=n;++i)G.add(a[i]),f[i]=G.ask(a[i]);
    for(int i=1;i<=tot;++i)sort(p+L[i],p+R[i]+1,cmp);   
    memset(G.c,0,sizeof(G.c));
    for(int i=1;i<=n;++i)++w[bl[i]][a[i]];
    for(int j=1;j<=tot;++j)for(int i=2;i<=n;++i)w[j][i]+=w[j][i-1];
    for(int i=1,op,l;i<=m;++i)
    {
        op=rd,l=rd;
        if(op==1)add(l,rd);
        if(op==2)cout<<ask(l)<<'\n';
    }
    return 0;
}

还是分块，考虑直接维护 b 序列。

对于 j 在散块情况，直接求出 f_j(l,j) 的值加到 b_j。这里先将所有 f_x(l,r) 离线，使用 \mathcal{O}(\sqrt{n}) 单点加，\mathcal{O}(1) 前缀和的分块维护离线二维数点即可。

对于 i,j 均在整块的情况，记录 w_{x,y} 表示块 x,x+1,\ldots,y-1,y 对 y 贡献的次数即可，贡献容易预处理，i,j 同块的贡献可以询问时暴力算。

对于 i 在散块，j 在整块的情况，和上面做法中散块对整块的贡献是相似的。不妨将其看作在一个 \sqrt{n} \times n 的平面上支持 \mathcal{O}(1) 单点加，\mathcal{O}(\sqrt{n}) 二维前缀和。

考虑对于 \sqrt{n} 这一维上以 \mathcal{O}(\sqrt[4]{n}) 为块长分块，每个元素都是一个值域分块。然后单点加和前缀和的次数分别为 \mathcal{O}(n\sqrt{n}) 和 \mathcal{O}(n\sqrt[4]{n})。

每个元素的值域分块就需要做到 \mathcal{O}(1) 单点加， \mathcal{O}(\sqrt[4]{n}) 前缀和。可以分别以 \mathcal{O}(n ^{\frac{3}{4}}),\mathcal{O}(n ^{\frac{1}{2}}),\mathcal{O}(n ^{\frac{1}{4}}) 分块，然后每一层的块的数量都是 \mathcal{O}(\sqrt[4]{n})，复杂度就对了。

时空复杂度均为 \mathcal{O}(n\sqrt{n})。

#include<bits/stdc++.h>
#define ll long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    unsigned int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=200003,B1=20,B2=B1*B1,B3=B2*B1;
const int S1=N/B1+1,S2=N/B2+1,S3=N/B3+1;
int n,m,tot1,tot2,tot3,cnt;
int op[N],f[N],al[N],ar[N],b1[N],b2[N],b3[N],a[N],tg[S2][S2];
int L1[S1],R1[S1],L2[S2],R2[S2],L3[S3],R3[S3],sum[B2*N<<1];
struct node{int x,y,z;};vector<node> q[N];
ll b[N];short w[S2][N];
struct blk
{
    int c[N],t[S2];
    inline void add(int x)
    {
        for(int i=x;i<=R2[b2[x]];++i)++c[i];
        for(int i=b2[x]+1;i<=tot2;++i)++t[i];
    }
    inline int ask(int x){return c[x]+t[b2[x]];}
}G;
struct blk2
{
    int t[N],t1[S1],t2[S2],t3[S3];
    inline void add(int x,int v){t[x]+=v,t1[b1[x]]+=v,t2[b2[x]]+=v,t3[b3[x]]+=v;}
    inline int ask(int x)
    {
        int s=0;
        for(int i=1;i<b3[x];++i)s+=t3[i];
        for(int i=b2[L3[b3[x]]];i<b2[x];++i)s+=t2[i];
        for(int i=b1[L2[b2[x]]];i<b1[x];++i)s+=t1[i];
        for(int i=L1[b1[x]];i<=x;++i)s+=t[i];
        return s;
    }
}tk[S3],ck[S2];
inline void ADD(int x,int y,int v){tk[b1[x]].add(y,v),ck[x].add(y,v);}
inline ll ASK(int x,int y)
{
    ll res=0;
    for(int i=1;i<b1[x];++i)res+=tk[i].ask(y);
    for(int i=L1[b1[x]];i<=x;++i)res+=ck[i].ask(y);
    return res;
}
inline void add(int l,int r)
{
    if(b2[l]==b2[r]){for(int i=l;i<=r;++i)b[i]+=f[i]-sum[++cnt];return;}
    add(l,R2[b2[l]]),add(L2[b2[r]],r);
    for(int i=b2[l]+1;i<b2[r];++i)++tg[b2[l]+1][i];
    for(int i=l;i<=R2[b2[l]];++i)ADD(b2[l]+1,a[i],1),ADD(b2[r],a[i],-1);
}
inline void irt(int l,int r)
{
    if(!l)return;
    if(b2[l]==b2[r]){q[l-1].push_back({l,r,cnt}),cnt+=r-l+1;return;}
    q[l-1].push_back({l,R2[b2[l]],cnt}),cnt+=R2[b2[l]]-l+1;
    q[l-1].push_back({L2[b2[r]],r,cnt}),cnt+=r-L2[b2[r]]+1;
}
inline void irt2(int x){q[L2[b2[x]]-1].push_back({x,x,cnt});++cnt;}
inline ll ask(int x)
{
    ll res=b[x];int v=a[x],c=0;
    for(int i=1;i<b2[x];++i)res+=1ll*w[i][v]*(c+=tg[i][b2[x]]);
    res+=1ll*(c+tg[b2[x]][b2[x]])*(f[x]-sum[++cnt]);
    return res+ASK(b2[x],v);
}
signed main()
{
    n=rd,m=rd,tot1=(n-1)/B1+1,tot2=(n-1)/B2+1,tot3=(n-1)/B3+1,cnt=1;
    for(int i=1;i<=tot1;++i)L1[i]=R1[i-1]+1,R1[i]=i*B1;R1[tot1]=n;
    for(int i=1;i<=tot2;++i)L2[i]=R2[i-1]+1,R2[i]=i*B2;R2[tot2]=n;
    for(int i=1;i<=tot3;++i)L3[i]=R3[i-1]+1,R3[i]=i*B3;R3[tot3]=n;
    for(int i=1;i<=n;++i)a[i]=rd,b1[i]=(i-1)/B1+1,b2[i]=(i-1)/B2+1,b3[i]=(i-1)/B3+1;
    for(int i=1;i<=n;++i)++w[b2[i]][a[i]];
    for(int j=1;j<=tot2;++j)for(int i=2;i<=n;++i)w[j][i]+=w[j][i-1];
    for(int i=1;i<=m;++i){op[i]=rd,al[i]=rd;if(op[i]==1)irt(al[i],ar[i]=rd);if(op[i]==2)irt2(al[i]);}
    for(int i=1;i<=n;f[i]=G.ask(a[i]),++i)
    {
        G.add(a[i]);
        for(auto [l,r,id]:q[i])for(int j=l;j<=r;++j)sum[id+j-l]=G.ask(a[j]);
    }
    cnt=0;
    for(int i=1;i<=m;++i)
        if(op[i]==1)add(al[i],ar[i]);
        else cout<<ask(al[i])<<'\n';
    return 0;
}