BZOJ2141 排队 <分块+树状数组>

Problem

排队

$\mathrm{Time\;Limit:\;4\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

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

Input

第一行为一个正整数$n$，表示小朋友的数量。
第二行包含$n$个由空格分隔的正整数$h_1,h_2,\cdots,h_n$，依次表示初始队列中小朋友的身高。
第三行为一个正整数$m$，表示交换操作的次数。
以下$m$行每行包含两个正整数$a_i$和$b_i$，表示交换位置$a_i$与位置$b_i$的小朋友。

Output

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

Sample Input

3
130 150 140
2
2 3
1 3

Sample Output

1
0
3

Hint

样例说明
未进行任何操作时，$(2,3)$满足条件；
操作$1$结束后，序列为$\lbrace130,140,150\rbrace$，不存在满足条件的$(i,j)$；
操作$2$结束后，序列为$\lbrace150,140,130\rbrace$，有$(1,2)$,$(1,3)$,$(2,3)$共$3$对满足条件的$(i,j)$
数据规模
$1\le m\le2\times10^3$，$1\le n\le2\times10^4$，$1\le h_i\le10^9$，$a_i\ne b_i$，$1\le a_i,b_i\le n$。

标签：分块 树状数组

Solution

分块基础应用之带交换逆序对。

将原序列分为$\sqrt{n}$个大小为$\sqrt{n}$的块，每块内维护一个值域树状数组，记录每个值的个数。
一开始增量计算总逆序对对数，随后对每个操作计算会增加/减少多少对逆序对。
当交换$a[x],a[y]\;(x<y)$时，对于$i\in[x,y]$，

• 若$a[i]<a[x]$，则$ans- -$
• 若$a[i]>a[x]$，则$ans++$
• 若$a[i]<a[y]$，则$ans++$
• 若$a[i]>a[y]$，则$ans- -$

整块直接用树状数组统计，剩余部分暴力即可。

Code

#include <bits/stdc++.h>
#define MAX_N 20000
#define MAGIC ((int)sqrt(n))
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, cnt, tot, a[MAX_N+5], b[MAX_N+5];
int BIT[150][MAX_N+5]; map <int, int> h;
int id(int p) {return (p-1)/MAGIC+1;}
void inc(int tr[], int p) {for (; p <= n; p += (p&-p)) tr[p]++;}
void dec(int tr[], int p) {for (; p <= n; p += (p&-p)) tr[p]--;}
int sum(int tr[], int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[p]; return ret;}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i]; sort(b+1, b+n+1);
    for (int i = 1; i <= n; i++) if (!i || (b[i]^b[i-1])) h[b[i]] = ++cnt;
    for (int i = 1; i <= n; i++) inc(BIT[0], a[i] = h[a[i]]), tot += i-sum(BIT[0], a[i]);
    for (int i = 1; i <= n; i++) inc(BIT[id(i)], a[i]); printf("%d\n", tot); read(m);
    while (m--) {
        int x, y; read(x), read(y); if (x > y) swap(x, y);
        if (id(x) < id(y)) {
            for (int i = id(x)+1; i <= id(y)-1; i++)
                tot -= sum(BIT[i], a[x]-1), tot += sum(BIT[i], n)-sum(BIT[i], a[x]), 
                tot += sum(BIT[i], a[y]-1), tot -= sum(BIT[i], n)-sum(BIT[i], a[y]);
            for (int i = x+1; i <= id(x)*MAGIC; i++)
                tot -= (a[i] < a[x]), tot += (a[i] > a[x]), 
                tot += (a[i] < a[y]), tot -= (a[i] > a[y]);
            for (int i = y-1; i >= (id(y)-1)*MAGIC+1; i--)
                tot -= (a[i] < a[x]), tot += (a[i] > a[x]), 
                tot += (a[i] < a[y]), tot -= (a[i] > a[y]);
        } else
            for (int i = x+1; i <= y-1; i++)
                tot -= (a[i] < a[x]), tot += (a[i] > a[x]), 
                tot += (a[i] < a[y]), tot -= (a[i] > a[y]);
        tot += (a[x] < a[y]), tot -= (a[x] > a[y]);
        dec(BIT[id(x)], a[x]), dec(BIT[id(y)], a[y]);
        inc(BIT[id(x)], a[y]), inc(BIT[id(y)], a[x]);
        swap(a[x], a[y]), printf("%d\n", tot);
    }
    return 0;
}