题解：P11365 [Ynoi2024] 新本格魔法少女りすか

Solution

操作不弱于区间逆序对，考虑分块，设块长为 B。

对于散块对散块的贡献，直接把所有数加进去查一遍 BIT 即可，复杂度 O(\sum mB\log n)。

对于整块对其他的贡献，我们可以考虑预处理出 f_{i,j}，表示第 i 个块与一个前缀 j 产生的贡献，询问可以简单 O(\frac{n}{B}(n+\sum m)) 求出。但是空间爆炸了，逐块处理即可。

设 M=\sum m，取 B=\sqrt{\frac{n^2}{M\log n}+\frac{n}{\log n}} 有最优复杂度 O(\sqrt{(n^2M+nM^2)\log n})，难以通过。

考虑优化 BIT 部分。对于查询，可以压位使得单次计算量减少大约 6 次；对于清空，只要当前位置已经为 0 就不用再往上跑了，清空复杂度优化为 O(n)。可以通过。

Code

加了上述几个优化后微调一下块长还是能比较轻松地跑过的。

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
// Fast IO
constexpr int N=5e5+5,B=553,S=B+5,T=N/B+5;
struct node{
    int l,r;
    node(){l=r=0;}
    node(int _l,int _r){l=_l,r=_r;}
};
int n,len,q,a[N];pii num[N];
int tot,pos[N];node rngB[T];ll ans[N];
int m;node rngQ[N],rng[N],rng_[N];
ull b[N];int c[N],mdf[N],cnt;
inline void upd(int x){
    mdf[++cnt]=x;
    static int y,z;y=x&63,z=x>>6;
    b[z]|=1ull<<y;
    for(++z;z<=len;z+=z&-z)++c[z];
}
inline int ask(int x){
    static int y,z;y=x&63,z=x>>6;
    static int res;res=__builtin_popcountll(b[z]&((y==63?0:1ull<<(y+1))-1));
    for(;z;z-=z&-z)res+=c[z];
    return res;
}
inline void clr(int x){
    static int z;z=x>>6;
    b[z]=0;
    for(++z;z<=n;z+=z&-z)
        if(c[z])c[z]=0;
        else break;
}
void clear(){
    for(int i=1;i<=cnt;i++)
        clr(mdf[i]);
    cnt=0;
}
int op[N],s[N];ll sum[N];
vector<node> vec[T];
int main(){
    cin>>n>>q;len=(n>>6)+1;
    for(int i=1;i<=n;i++)cin>>a[i],num[i]=make_pair(a[i],n-i+1);
    sort(num+1,num+n+1);
    for(int i=1;i<=n;i++)a[i]=lower_bound(num+1,num+n+1,make_pair(a[i],n-i+1))-num;
    while(rngB[tot].r<n){
        ++tot;
        rngB[tot]=node(rngB[tot-1].r+1,rngB[tot-1].r+B);
    }
    rngB[tot].r=n;
    for(int i=1;i<=tot;i++){
        static int l,r;l=rngB[i].l,r=rngB[i].r;
        for(int j=l;j<=r;j++)
            pos[j]=i;
    }
    for(int i=1;i<=q;i++){
        op[i]=-1;
        int mi;cin>>mi;
        rngQ[i]=node(m+1,m+mi);
        while(mi--){
            ++m,cin>>rng[m].l>>rng[m].r;
            static int _l,_r,_x,_y,_L,_R;
            _l=rng[m].l,_r=rng[m].r,_x=pos[_l],_y=pos[_r],_L=rngB[_y].l,_R=rngB[_x].r;
            if(_y-_x<=1){
                for(int k=_l;k<=_r;k++)ans[i]+=ask(a[k]-1);
                for(int k=_l;k<=_r;k++)upd(a[k]);
            }
            else{
                vec[_x+1].emplace_back(i,m);
                vec[_y].emplace_back(-i,m);
                rng_[m]=node(_R+1,_L);
                for(int k=_l;k<=_R;k++)ans[i]+=ask(a[k]-1);
                for(int k=_L;k<=_r;k++)ans[i]+=ask(a[k]-1);
                for(int k=_l;k<=_R;k++)upd(a[k]);
                for(int k=_L;k<=_r;k++)upd(a[k]);
            }
        }
        clear();
    }
    for(int u=1;u<=tot;u++){
        static int _L,_R,_sum;
        _L=rngB[u].l,_R=rngB[u].r,_sum=_R-_L+1;
        for(int i=_L;i<=_R;i++)++s[a[i]];
        for(int i=1;i<=n;i++)s[i]+=s[i-1];
        sum[_L]=0;for(int i=_L-1;i>=1;i--)sum[i]=sum[i+1]+_sum-s[a[i]];
        sum[_R]=0;for(int i=_R+1;i<=n;i++)sum[i]=sum[i-1]+s[a[i]-1];
        for(auto &o:vec[u]){
            if(o.l>0)op[o.l]=o.r;
            else op[-o.l]=-1;
        }
        for(int o=1;o<=q;o++){
            if(!~op[o])continue;
            static int from,p,to;from=rngQ[o].l,p=op[o],to=rngQ[o].r;
            for(int i=from;i<p;++i){
                ans[o]+=sum[rng[i].l]-sum[rng[i].r+1];
                ans[o]-=sum[rng_[i].l]-sum[rng_[i].r];
            }
            for(int i=p+1;i<=to;++i)
                ans[o]+=sum[rng[i].r]-sum[rng[i].l-1];
        }
        for(int i=1;i<=n;i++)s[i]=0;
    }
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}