Description

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足ihj的(i,j)数量。幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。
Input

第一行为一个正整数n，表示小朋友的数量；第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；第三行为一个正整数m，表示交换操作的次数；以下m行每行包含两个正整数ai和bi¬，表示交换位置ai与位置bi的小朋友。
Output

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

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)。

【数据规模和约定】

对于100%的数据，1≤m≤2*103，1≤n≤2*104，1≤hi≤109，ai≠bi，1≤ai,bi≤n。

解法：

应一位OI小朋友的要求，写一个这个题目的详细题解。

首先说一下逆序数，所谓逆序数就是满足i小于j,并且满足a[i]>a[j]的数的对数。显然求逆序数对数，可以直接暴

力，但是这样的复杂度是O（n^2）的，另外一种是用树状数组求，我们可以把数一个个插入到树状数组中，

每插入一个数， 统计比他小的数的个数，对应的逆序为 i- getsum( data[i] )，其中 i 为当前已经插入的数的

个数， getsum( data[i] ）为比 data[i] 小的数的个数，i- getsum( data[i] ) 即比 data[i] 大的个数， 即逆序

的个数。最后需要把所有逆序数求和，就是在插入的过程中边插入边求和。可以自己在纸上模拟一下这个过

程，这里就不过于纠结了。然后一般求逆序数的题目，数会比较大，所以在之前加一个离散化就好了，离散化之后在做树状数组就好了，这个算法的复杂度是O(nlogn)的。

这个题， 显然 首先离散化，然后分块，对于每块建立一个树状数组，保存这个块中的所有元素

然后对于每个询问(x,y) (x小于y) 两侧的数是没有影响的，区间(x,y)的数a[i]讨论如下：

a[i]小于a[x] –ans

a[i]大于a[x] ++ans

a[i]小于a[y] ++ans

a[i]大于a[y] –ans

然后对于块中的树状数组处理，块外的暴力

然后注意有重复元素

复杂度O(sqrt(n)*log(n))

其实这个题树套树的复杂度是O(logn*logn)理论上是比分块快的，但是实际上这个题分块比树套树快到不知道

哪里去了。

//BZOJ 2141

#include <bits/stdc++.h>
using namespace std;

/// a[i] < a[x] --ans /// a[i] > a[x] ++ans
/// a[i] < a[y] ++ans /// a[i] > a[y] --ans

struct node{
    int h, id;//h代表高度，id代表在原来数组的值
    node(){}
    node(int h, int id):h(h),id(id){}
}a[20010];

int v[20010], top, tree[150][20010];
//v和top是用来离散化的，tree[i][j]代表的是第i块的树状数组，由于最多分到sqrt(n)块，150够了
int n, m, block;

bool cmp1(node a, node b){//先按高度排序，离散化
    return a.h < b.h;
}

bool cmp2(node a, node b){//再按照id排序，变回原来数组的位置
    return a.id < b.id;
}

void update(int p, int x, int a){//代表更新第p块的树状数组的值
    for(int i=x; i<=top;i+=i&-i){
        tree[p][i] += a;
    }
}

int query(int p,int x){//查询第p块的树状数组里面比x小的数的和
    int ans=0;
    for(int i=x;i;i-=i&-i){
        ans+=tree[p][i];
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    block = sqrt(n);
    for(int i=0;i<n;i++) scanf("%d",&a[i].h), a[i].id=i;
    //离散化
    sort(a,a+n,cmp1);
    for(int i=0;i<n;i++){
        if(a[i].h!=v[top]) v[++top]=a[i].h;
        a[i].h=top;
    }
    //按照id排序，但是现在高度变小了，可以把这个高度做成树状数组
    sort(a,a+n,cmp2);
    int ans = 0;
    //存答案
    for(int i=0;i<n;i++){
        //扫一遍数组
        for(int j=0;j<=i/block;j++) ans-= query(j,a[i].h);
        ans+=i;
        //参考上面树状数组求逆序数的过程
        update(i/block,a[i].h,1);
        把a[i]插入到i对应的块里面
    }
    printf("%d\n",ans);
    scanf("%d",&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        x--,y--;
        //下标我从0开始，所以先减1
        if(x>y) swap(x,y);
        //注意区间大小不一定是左边比右边小
        if(x/block==y/block)//在同一块里面，我们按照上面的统计贡献的方法，直接暴力扫这一块，计算答案，块大小sqrt(n)所以复杂度不超过sqrt(n)
            for(int i=x+1;i<y;i++)
                ans += (a[i].h > a[x].h) + (a[i].h < a[y].h) - (a[i].h < a[x].h) - (a[i].h > a[y].h);
        else{
            //要是不在同一块，那么中间的整块，也就是块大小等于sqrt(n)的我们直接BIT求,端点不完整的两块， 仍然暴力扫描就可以了。
            for(int i=x/block+1;i<y/block;i++) ans += (block-query(i,a[x].h))+query(i,a[y].h-1)-query(i,a[x].h-1)-(block-query(i,a[y].h)); //这个统计贡献还是看上面
            for(int i=x+1; i<(x/block+1)*block;i++ )
                ans += (a[i].h>a[x].h)+(a[i].h<a[y].h)-(a[i].h<a[x].h)-(a[i].h>a[y].h);
            for(int i=y/block*block;i<y;i++) ans += (a[i].h>a[x].h) + (a[i].h<a[y].h)-(a[i].h < a[x].h)-(a[i].h > a[y].h);//同理
        }
        ans+=(a[x].h<a[y].h)-(a[x].h>a[y].h);
        //然后考虑本身两个数能否形成逆序数
        update(x/block,a[x].h,-1),update(y/block,a[y].h,-1); //要交换两个数，那么对这两个数所在块里的逆序数会产生影响，我们在这两个数的块里面去更新
        swap(a[x].h,a[y].h);
        //交换
        update(x/block,a[x].h,1),update(y/block,a[y].h,1); //和上面同理
        printf("%d\n",ans);
        //输出这次的答案
    }
    return 0;
}