[CQOI2011] 动态逆序对

题意

给出一个 的排列 ,要求做 次删除操作,每次删掉一个数 ,求每次删除操作前整个序列的逆序对。

.

教训

这道题告诉我永远不要相信 是有区别的

他们只是在告诉你,你的程序有问题……

我一个点 ,调了 20 分钟,结果开大数组就过了……

不说废话了,我们分析一下

分析

静态逆序对

静态逆序对直接树状数组求啊

那么我们考虑一下如何维护这个删除操作

问题转化

删除操作

对于我们删除的第一个数 ,与 有关的一些逆序对就会消失,具体为

这个东西分两半,可以用树状树状算

但是直接用这个算的话,会把 与已经被删除的数的逆序对包括进来

那么我们就去求每次删除后 与已经被删除的数的逆序对,然后减掉它就好啦

维护已删除序列

也就是说,我们把删除操作转变为添加的操作,具体方案为

维护当前逆序对数 ,对于每个删除 的操作:

  1. 输出 .
  2. 在已删除的序列中统计在 前面比 大的数的个数,在 后面比 小的数的个数,两者的和记为 .
  3. 对于完全序列,与 有关的逆序对有 个(即上述和式)
  4. 那么 .
  5. 添加到已删除的序列中
    那么现在就要考虑维护已删除的序列了

树状数组套权值线段树

考虑到要统计比 大的数和比 小的数的个数,想到建权值线段树做类似 BST 的查询

又因为是区间查询,那么持久化一下,在历史版本上做前缀和查询操作

不过,我们的添加(修改)操作是无序的,在修改的时候,就会影响后面的前缀和

那么我们用树状数组维护前缀和就行

小 Trick

计算和式

其实只用树状数组维护前一个 就行,后一个可以通过结合当前元素的下标和当前元素的值计算得到

在删除序列上统计逆序对

只用写一个查询函数就行

查找在 前比它大的数,以及整个序列中比它大的数

然后结合 前面的数的个数就可以算出来在 后面比 小的数的个数

代码

#include<cstdio>
using namespace std;
const int N=1e5+10,LST=1<<24;
int n,m,tot;
int lc[LST],rc[LST],rt[LST],cnt[LST];

void pushdown(int u){// 新建子结点
    if(lc[u]||rc[u])return;
    lc[u]=++tot,rc[u]=++tot;
}
void pushup(int u){cnt[u]=cnt[lc[u]]+cnt[rc[u]];}
void add(int u,int l,int r,int v){// 直接在树上修改
    if(l==r){++cnt[u];return;}
    pushdown(u);// 如果没有结点就新建
    int mid=(l+r)>>1;
    if(v<=mid)add(lc[u],l,mid,v);
    else add(rc[u],mid+1,r,v);
    pushup(u);// 上传修改
}
int query(int u,int l,int r,int k){// 在以 u 为根的子树内大于 k 的个数
    if(cnt[u]==0)return 0;
    if(l==r)return l>k;
    int mid=(l+r)>>1;
    if(mid<k)return query(rc[u],mid+1,r,k);
    else return query(lc[u],l,mid,k)+cnt[rc[u]];
}
// 树状数组的部分
int c[N],pos[N],s1[N],s2[N];
//s1[i] 表示在 i 前面,比 i 大的数的个数;s2 表示在 i 后面比 i 小的数的个数
void add(int p){//+1
    for(int i=p;i<=n;i+=i&-i)c[i]++;
}
int pre(int p){
    int res=0;
    for(int i=p;i>=1;i-=i&-i)res+=c[i];
    return res;
}
long long ans;
signed main(){scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++){scanf("%d",&x),pos[x]=i;
        s1[x]=pre(n+1-x),s2[x]=x-i+s1[x];
        ans+=s1[x],add(n+1-x);// 倒序计入树状数组
        rt[i]=++tot;// 初始化根结点
    }
    for(int i=1,x;i<=m;i++){printf("%lld\n",ans);// 输出删除前的答案
        scanf("%d",&x);
        int t1=0,t2=0,t3=0;
        //t1 表示在 x 前面比 x 大的数的个数,t2 表示在 x 前面的数的总数(不包括 x)
        for(int i=pos[x];i>=1;i-=i&-i)t1+=query(rt[i],1,n,x),t2+=cnt[rt[i]];
        for(int i=n;i>=1;i-=i&-i)t3+=query(rt[i],1,n,x);// 整个序列中比 x 大的数的个数
        int nxd=t1+t1-t2-t3+i-1;
        ans=ans-s1[x]-s2[x]+nxd;// 更新答案
        for(int i=pos[x];i<=n;i+=i&-i)add(rt[i],1,n,x);
    }
    return 0;
}

 上一篇
DP 优化微剖 2 DP 优化微剖 2
引言和《鹰蛋》一样的优化思路 书稿复制 - 问题引入对于长度为 的序列序列 ,要求将其分为 段,使得每一段的和的最大值最小 DP 思路 表示前 个数分 段的最小最大值,记 $S[k]=
2019.01.24
下一篇 
[SDOI2010] 粟粟的书架 [SDOI2010] 粟粟的书架
题意给出一个矩阵 ,要求回答 个以下询问: x1,y1,x2,y2,h 在以 为左上角,以 为右下角的子矩阵中找出 数使得这些数的和大于等于 . 要求最小化
2019.01.24
  目录