【[CQOI2011]动态逆序对】

这是我的第一个数据结构套数据结构

不是线段树套\(Splay\)，而是非常蛇皮的块状链表套树状数组

如果这里按照\(\sqrt{n}\)的大小来分块，那么就需要\(n\sqrt{n}\)的空间，可能开不下，于是我们按照\(1000\)分块，也就只会分出\(100\)个块，就能开下空间了

之后每一次查询的时候直接查询树状数组就好了，每次修改则非常的块，直接找到对应的块改动这个块的树状数组就好了

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define lowbit(x) ((x)&(-x))
#define re register
#define maxn 100005
#define LL long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
int a[maxn],b[maxn];
int l[1005],r[1005],sz[1005];
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<‘0‘||c>‘9‘) c=getchar();
    while(c>=‘0‘&&c<=‘9‘)
        x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
int c[maxn];
int bit[101][maxn];
int n,m,tot,len;
LL ans;
int to[maxn],vis[maxn];
inline void add(int x)
{
    for(re int i=x;i<=n;i+=lowbit(i))
        c[i]++;
}
inline int ask(int x)
{
    int now=0;
    for(re int i=x;i;i-=lowbit(i))
        now+=c[i];
    return now;
}
inline void get_pair()
{
    for(re int i=1;i<=n;i++)
    {
        ans+=ask(n)-ask(a[i]);
        add(a[i]);
    }
}
inline void B_add(int o,int x,int val)
{
    for(re int i=x;i<=n;i+=lowbit(i)) bit[o][i]+=val;
}
inline int B_ask(int o,int x)
{
    int now=0;
    for(re int i=x;i;i-=lowbit(i)) now+=bit[o][i];
    return now;
}
inline void build_block()
{
    len=1000;
    int k=1;
    while(k<=n)
    {
        l[++tot]=k;
        r[tot]=min(n,k+len-1);
        k=r[tot]+1;
        for(re int i=l[tot];i<=r[tot];i++) 
            B_add(tot,a[i],1);
    }
}
inline int get_num(int x)
{
    if(x%len==0) return x/len;
    return x/len+1;
}
inline void BL_change(int x)
{
    vis[to[x]]=1;
    int now=get_num(to[x]);
    B_add(now,x,-1);
}
inline int BL_find_less(int x,int y,int val)
{
    int num=0;
    for(re int i=x;i<=y;i++)
        if(!vis[i]&&a[i]<val) num++;
    return num;
}
inline int BL_find_more(int x,int y,int val)
{
    int num=0;
    for(re int i=x;i<=y;i++)
        if(!vis[i]&&a[i]>val) num++;
    return num;
}
inline int find_less(int x,int y,int val)
{
    int num=0;
    for(re int i=1;i<=tot;i++)
    {
        if(x>l[i]&&y<r[i]) return BL_find_less(x,y,val);
        if(x<=l[i]&&y>=r[i]) num+=B_ask(i,val);
            else if(x<=l[i]&&y<r[i]) num+=BL_find_less(l[i],y,val);
                else if(y>=r[i]&&x>l[i]) num+=BL_find_less(x,r[i],val);
    }
    return num;
}
inline int find_more(int x,int y,int val)
{
    int num=0;
    for(re int i=1;i<=tot;i++)
    {
        if(x>l[i]&&y<r[i]) return BL_find_more(x,y,val);
        if(x<=l[i]&&y>=r[i]) num+=B_ask(i,n)-B_ask(i,val);
            else if(x<=l[i]&&y<r[i]) num+=BL_find_more(l[i],y,val);
                else if(y>=r[i]&&x>l[i]) num+=BL_find_more(x,r[i],val);
    }
    return num;
}
int main()
{
    n=read(),m=read();
    for(re int i=1;i<=n;i++) a[i]=read(),to[a[i]]=i;
    get_pair(),build_block();
    int x;
    while(m--)
    {
        printf("%lld\n",ans);
        x=read();
        if(to[x]!=1) ans-=find_more(1,to[x]-1,x);
        if(to[x]!=n) ans-=find_less(to[x]+1,n,x);
        BL_change(x);
    }
    return 0;
}

【[CQOI2011]动态逆序对】

原文：https://www.cnblogs.com/asuldb/p/10205718.html