BZOJ2141 || 洛谷P1975 [国家集训队]排队【线段树套treap】

Time Limit: 4 Sec

Memory Limit: 259 MB

Description

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。

红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足 i<j i < j 且 hi>hj h i > h j 的 (i,j) ( i , j ) 数量。

幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。

Input

第一行为一个正整数n，表示小朋友的数量；

第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；

第三行为一个正整数m，表示交换操作的次数；

以下m行每行包含两个正整数ai和bi，表示交换位置ai与位置bi的小朋友。

1≤m≤2∗103，1≤n≤2∗104，1≤hi≤109，ai≠bi，1≤ai,bi≤n。 1 ≤ m ≤ 2 ∗ 10 3 ， 1 ≤ n ≤ 2 ∗ 10 4 ， 1 ≤ h i ≤ 10 9 ， a i ≠ b i ， 1 ≤ a i , b i ≤ n 。

Output

输出文件共m行，第i行一个正整数表示交换操作i结束后，序列的杂乱程度。

题目分析

本质就是动态逆序对

一开始先求出初始序列的逆序对数

对于每个 1<=i<n 1 <= i < n 求出 i 到 n区间内比 hi h i 小的数的个数总和

记为ans

每次交换了x和y位置的人

ans+= x+1到y区间内比 hy h y 小的数的个数

ans+= x到y-1区间内比 hx h x 大的数的个数

ans-= x+1到y区间内比 hy h y 大的数的个数

ans-= x到y-1区间内比 hx h x 小的数的个数

最后单独比较 hx h x 和 hy h y

若 hx>hy h x > h y ，则令ans–

反之ans++

最后再分别修改x和y位置的值

特别的

如果 hx==hy h x == h y ，那么可以直接输出答案并跳过更新

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define update(p) sum[p]=cnt[p]+sum[ch[p][0]]+sum[ch[p][1]];
typedef long long lt;

int read()
{
    int f=,x=;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=;
int n,m;
int a[maxn],rt[maxn],val[maxn],tot;
int ch[maxn][],rnd[maxn],sum[maxn],cnt[maxn];
lt ans;

void rotate(int &p,int d)
{
    int k=ch[p][d^];
    ch[p][d^]=ch[k][d];
    ch[k][d]=p;
    update(p); update(k);
    p=k;
}

void ins(int &p,int x)
{
    if(!p)
    {
        p=++tot; val[p]=x; rnd[p]=rand();
        sum[p]=cnt[p]=;
        return;
    }
    if(val[p]==x){ ++sum[p]; ++cnt[p]; return;}
    int d=x<val[p] ?:;
    ins(ch[p][d],x);
    if(rnd[ch[p][d]]<rnd[p]) rotate(p,d^);
    update(p);
}

void build(int s,int t,int p)
{
    for(int i=s;i<=t;++i) ins(rt[p],a[i]);
    if(s==t) return;
    int mid=s+t>>;
    build(s,mid,p<<); build(mid+,t,p<<|); 
}

int rank_treap(int p,int x,int d)
{
    if(!p) return ;
    int ss=sum[ch[p][d]];
    if(val[p]==x) return ss;
    else if((x<val[p]&&d==)||(x>val[p]&&d==)) return rank_treap(ch[p][d],x,d);
    else return ss+cnt[p]+rank_treap(ch[p][d^],x,d);
}

int rank_seg(int ll,int rr,int s,int t,int p,int v,int d)
{
    if(ll<=s&&t<=rr) return rank_treap(rt[p],v,d);
    int mid=s+t>>,cnt=;
    if(ll<=mid) cnt+=rank_seg(ll,rr,s,mid,p<<,v,d);
    if(rr>mid) cnt+=rank_seg(ll,rr,mid+,t,p<<|,v,d);
    return cnt;
}

void del(int &p,int x)
{
    if(!p) return;
    if(val[p]==x)
    {
        if(cnt[p]>){ --sum[p]; --cnt[p]; return;}
        else if(ch[p][]*ch[p][]==) p=ch[p][]+ch[p][];
        else
        {
            int dd=rnd[ch[p][]]<rnd[ch[p][]] ?:;
            rotate(p,dd); del(ch[p][dd],x);
        } 
    }
    else if(x<val[p]) del(ch[p][],x);
    else del(ch[p][],x);
    if(p) update(p);
}

void modify(int s,int t,int p,int pos,int v)
{
    del(rt[p],a[pos]); ins(rt[p],v);
    if(s==t) return;
    int mid=s+t>>;
    if(pos<=mid) modify(s,mid,p<<,pos,v);
    else modify(mid+,t,p<<|,pos,v);
}

int main()
{
    n=read();
    for(int i=;i<=n;++i) a[i]=read();
    build(,n,);

    for(int i=;i<n;++i)
    ans+=rank_seg(i,n,,n,,a[i],);//初始逆序对数
    printf("%lld\n",ans);

    m=read();
    while(m--)
    {
        int x=read(),y=read(); if(x>y) swap(x,y);//注意左右大小区间
        if(a[x]==a[y]){ printf("%lld\n",ans); continue;}

        ans+=rank_seg(x+,y,,n,,a[y],)+rank_seg(x,y-,,n,,a[x],);
        ans-=rank_seg(x+,y,,n,,a[y],)+rank_seg(x,y-,,n,,a[x],);
        //0表示查询比该数小的个数，1反之

        modify(,n,,x,a[y]); modify(,n,,y,a[x]);
        swap(a[x],a[y]);
        printf("%lld\n",ans);
    }
    return ;
}