题解 P1975 【[国家集训队]排队】

Dzhao · 2020-01-27 13:00:54 · 题解

题解P1975

Blog

我们先理解一下题意。（好吧其实~~没什么需要理解的~~）

我们需要一个在线修改并查询逆序对个数的数据结构。

逆序对大家都会，归并排序，离散化+线段树or树状数组都可以。但是，在线修改的逆序对问题，就有点困难了。

我们先感性分析一下这个玩意儿怎么求。

当我们交换a[l]和a[r]时，我们发现，这一个交换，与[1,l]和[r,n]这两个区间内的逆序对个数是没什么关系的，唯一相关的只有[l+1,r-1]这个区间内的逆序对个数有关。

原本能组成逆序对的只有：a[r]和[l+1,r-1]中比他大的，a[l]和[l+1,r-1]区间中比他小的。

我们类比一下，新添的逆序对个数就一定是：a[r]和[l+1,r-1]中比他小的，a[l]和[l+1,r-1]区间中比他大的。

最后，再特判一下：

如果a[l]<a[r],那么ans++

如果a[l]>a[r],那么ans--

问题解决了，下面问题来了，怎样解决上述的问题呢？

我们想一下，既要记录一个区间，有要记录其中比他小的数的个数，要实现一个双重功能，于是，一种数据结构跃入我们的脑中：树套树。（虽然分块大法也很棒，但是，我们尽量用在大数据下也依然不倒的数据结构。）

我们用树状数组的修改方式来套带权值的线段树,在带上一个动态开点就好了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=20009;
int a[N],n,q,root[N],tot;
struct Segtree
{
    int lc,rc,v; //lc为左儿子节点号，rc为右儿子节点号 
}tree[N<<8];
inline void swap(int &x,int &y) {int tmp=x;x=y;y=tmp;}
inline int read()
{
    int flag=1,x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') flag=-1;ch=getchar();}
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*flag;
}
inline int build() //动态开点，开一个点，假设他没有任何孩子且无权值 
{
    tot++;
    tree[tot].lc=tree[tot].rc=tree[tot].v=0;
    return tot;
}
void update(int &k,int l,int r,int x,int z) //修改操作 
{
    if(!k) k=build();
    if(l==r)
    {
        tree[k].v+=z;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(tree[k].lc,l,mid,x,z);
    else update(tree[k].rc,mid+1,r,x,z);
    tree[k].v=tree[tree[k].lc].v+tree[tree[k].rc].v;
}
int query(int k,int l,int r,int x,int y) //查询操作 
{
    if(!k) return 0; 
    if(l>y || r<x) return 0;
    if(l>=x && r<=y) return tree[k].v;
    int mid=(l+r)>>1;
    return query(tree[k].lc,l,mid,x,y)+query(tree[k].rc,mid+1,r,x,y);
}
inline void insert(int x,int y,int z) //用树状数组的方法插入 
{
    for(;x<=n;x+=x&-x) update(root[x],1,n,y,z);
}
inline int sum(int x,int y,int l,int r) //树状数组方式查询 
{
    int res=0;
    for(;y;y-=y&-y) res+=query(root[y],1,n,l,r);
    for(x--;x;x-=x&-x) res-=query(root[x],1,n,l,r);
    return res;
}
int b[N];

int main()
{
    int ans=0;
    n=read();
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    /*-------------------------离散化-------------------------*/
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
    /*-------------------------将该序列按树状数组方式插入线段树-------------------------*/
    for(int i=1;i<=n;i++) insert(i,a[i],1);
    for(int i=2;i<=n;i++) ans+=sum(1,i-1,a[i]+1,m);
    q=read(); 
    printf("%d\n",ans);
    while(q--)
    {
        int l=read(),r=read();
        if(l>r) swap(l,r);
        /*-------------------------计算变化后的逆序对个数-------------------------*/
        ans-=sum(l+1,r-1,1,a[l]-1);
        ans+=sum(l+1,r-1,a[l]+1,m);
        ans-=sum(l+1,r-1,a[r]+1,m);
        ans+=sum(l+1,r-1,1,a[r]-1);
        if(a[l]<a[r]) ans++;
        if(a[l]>a[r]) ans--;
        /*-------------------------修改-------------------------*/
        insert(l,a[l],-1);
        insert(l,a[r],1);
        insert(r,a[l],1);
        insert(r,a[r],-1);
        swap(a[l],a[r]);
        printf("%d\n",ans);
    }
    return 0;
}

如果有任何问题，私信问我或评论区下问我都行。

Thanks$ $for$ $watching