分块+树状数组(比树套树快)

发布于 2018-05-24  839 次阅读


woc,一下午五六个小时就肝了这一个题,真滴恶心。。

链接:bzoj-2141(排队)

题意:
给你一个序列,求初始化的逆序对个数,然后m次查询,每次换两个位置的数,问你每次变换过后的逆序对个数

【样例输入】
3
130 150 140
2
2 3
1 3
Sample Output
1
0
3
【样例说明】
未进行任何操作时,(2,3)满足条件;
操作1结束后,序列为130 140 150,不存在满足ihj的(i,j)对;
操作2结束后,序列为150 140 130,(1,2),(1,3),(2,3)共3对满足条件的(i,j)

先离散化一下,然后通过树状数组先求出初始化的逆序对个数,接着位置x,y两个位置的数替换,也就转化成求区间【x,y】里面比h[x]小,大,比h[y]小,大的数,然后答案加减一下贡献就行,这里就需要分块一下,对于整块的可以用二分快速求比一个数大,小的数的个数,不完整的块暴力就行。。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <deque>
#include <queue>
#define ri(n) scanf("%d",&n)
#define oi(n) printf("%d\n",n)
#define rl(n) scanf("%lld",&n)
#define ol(n) printf("%lld\n",n)
#define rep(i,l,r) for(i=l;i<=r;i++)
#define rep1(i,l,r) for(i=l;i<r;i++)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int epg=10-8;
const int maxn=2e4+20;
int h[maxn];
int n,c[maxn];
int b[maxn],num[maxn];
int l[maxn],r[maxn];
int a[maxn],d[maxn];
int len,cnt,ans;
int t[maxn];
int sum(int x)
{
    int ans=0;
    while(x)
    {
        ans+=c[x];
        x-=x&-x;
    }
    return ans;
}
void add(int i,int ad)
{
    while(i<=n)
    {
        c[i]+=ad;
        i+=i&-i;
    }
}
int Find(int x)
{
    int l=1,r=n,mid;
    while(l<=r)
    {
        mid=l+r>>1;
        if(d[mid]<x)
            l=mid+1;
        else if(d[mid]>x)
            r=mid-1;
        else
        {
            l=mid;
            break;
        }
    }
    return l;
}

void rebuild(int i)
{
    for(int j=l[i];j<=r[i];j++)
            a[j]=h[j];
        sort(a+l[i],a+r[i]+1);
}
void build()
{
    for(int i=1;i<=cnt;i++)
    {
        rebuild(i);
    }
}

int upper(int l,int r,int x)
{
    int mid,ans=r,num=r+1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(a[mid]>x)
        {
            num=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return ans-num+1;
}

int lower(int l,int r,int x)
{
    int mid,ans=l,num=l-1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(a[mid]<x)
        {
            l=mid+1;
            num=mid;
        }
        else
        r=mid-1;
    }
    return num-ans+1;
}

void solve(int x,int y)
{
    if(x==y)
        return;
    if(h[x]<h[y])
        ans++;
    if(h[x]>h[y])
        ans--;
    //cout<<"ans="<<ans<<endl;
    if(b[x]==b[y])
    {
        for(int i=x+1;i<y;i++)
        {
            if(h[i]>h[x])
                ans++;
            if(h[i]<h[x])
                ans--;
            if(h[i]>h[y])
                ans--;
            if(h[i]<h[y])
                ans++;
        }
    }
    else
    {
        int L=r[b[x]],R=l[b[y]];
        //cout<<"L="<<L<<" R="<<R<<endl;
        for(int i=x+1;i<=L;i++)
        {
            if(h[i]>h[x])
                ans++;
            if(h[i]<h[x])
                ans--;
            if(h[i]>h[y])
                ans--;
            if(h[i]<h[y])
                ans++;
        }
        //cout<<"ans="<<ans<<endl;
        for(int i=R;i<y;i++)
        {
            if(h[i]>h[x])
                ans++;
            if(h[i]<h[x])
                ans--;
            if(h[i]>h[y])
                ans--;
            if(h[i]<h[y])
                ans++;
        }
        //cout<<"ans="<<ans<<endl;
        for(int i=b[x]+1;i<b[y];i++)
        {
            //cout<<"i="<<i<<" l="<<l[i]<<" r="<<r[i]<<endl;
            ans+=upper(l[i],r[i],h[x]);
            //cout<<"ans="<<ans<<endl;
            ans-=lower(l[i],r[i],h[x]);
            //cout<<"ans="<<ans<<endl;
            ans-=upper(l[i],r[i],h[y]);
            //cout<<"ans="<<ans<<endl;
            ans+=lower(l[i],r[i],h[y]);
        }
        //cout<<"ans="<<ans<<endl;
    }
    swap(h[x],h[y]);
    rebuild(b[x]);rebuild(b[y]);
}
int main()
{
    ans=0;
    memset(c,0,sizeof(c));
    memset(b,0,sizeof(b));
    memset(num,0,sizeof(num));
    scanf("%d",&n);
    len=sqrt(n);
    if(n%len==0)
        cnt=n/len;
    else
        cnt=n/len+1;
    //cout<<"cnt="<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
        l[i]=(i-1)*len+1,r[i]=i*len;
    //for(int i=1;i<=cnt;i++)
        //cout<<"i="<<i<<" l="<<l[i]<<" r="<<r[i]<<endl;
    r[cnt]=n;
    for(int i=1;i<=n;i++)
        b[i]=(i-1)/len+1;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&h[i]);
        a[i]=d[i]=h[i];
        t[i]=h[i];
       // cout<<"sum="<<sum(h[i])<<" gx="<<i-1-sum(h[i])<<endl;
        //ans+=i-1-sum(h[i]);
        //num[b[i]]+=ans;
        //add(h[i],1);
    }
    sort(d+1,d+1+n);
    for(int i=1;i<=n;i++)
        a[i]=h[i]=Find(h[i]);
    //for(int i=1;i<=n;i++)
        //cout<<"i="<<i<<" a="<<a[i]<<endl;
    for(int i=1; i<=n; i++)
    {
        ans+=i-1-sum(h[i]);
        add(h[i],1);
    }
    printf("%d\n",ans);
    build();
    int m;
    scanf("%d",&m);
    int x,y;
    while(m--)
    {
        //ans=0;
        int pp=0;
        scanf("%d%d",&x,&y);
        if(x>y)
            swap(x,y);
//        memset(c,0,sizeof(c));
//        swap(t[x],t[y]);
//        for(int i=1; i<=n; i++)
//        {
//            //cout<<"sum="<<sum(h[i])<<" gx="<<i-1-sum(h[i])<<endl;
//            pp+=i-1-sum(t[i]);
//            add(t[i],1);
//        }

//        for(int i=a+1;i<=b-1;i++)
//        {
//            if(h[i]>h[a])
//                ans++;
//            if(h[i]<h[a])
//                ans--;
//            if(h[i]>h[b])
//                ans--;
//            if(h[i]<h[b])
//                ans++;
//        }
//        if(h[a]>h[b])
//            ans--;
//        if(h[a]<h[b])
//            ans++;
//        int t=h[a];
//        h[a]=h[b];
//        h[b]=t;
        solve(x,y);
        //printf("pp=%d\n",pp);
        printf("%d\n",ans);

    }
    return 0;
}
/*
28
1 8 4 15 48 1 5 48 1 6 49 18 4 91 94 1 4 15 4 8 89 88 77 45 79 59 111 111
7
1 20
2 20
3 3
4 8
7 18
6 15
9 19
*/

Comments


愿我如星君如月,夜夜流光相皎洁。