2141: 排队
Time Limit: 4 Sec Memory Limit: 259 MB
Submit: 1169 Solved: 465
[Submit][Status][Discuss]
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
3
130 150 140
2
2 3
1 3
Sample Output
1
0
3
0
3
每次交换两个数， 求交换之后的逆序对的个数。
思路： 我们分块来做， 如果要交换的两个数x, y在同一块里， 那么就暴力计算。 否则的话， 暴力计算x+1到x这个块的最右边， 和y-1到y这个块的最左边， 两个块中间的块用二分查找来计算。
弱智错误查了一个小时...
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 2e4+;
int a[maxn], b[maxn], c[maxn], sum[maxn], l[maxn], r[maxn], belong[maxn];
int block, cnt, n, ans;
int lowbit(int x) {
return x&(-x);
}
void update(int x) {
for(int i = x; i<=n; i+=lowbit(i)) {
sum[i]++;
}
}
int query(int x) {
int ret = ;
for(int i = x; i>; i-=lowbit(i)) {
ret += sum[i];
}
return ret;
}
void rebuild(int x) {
for(int i = l[x]; i<=r[x]; i++)
b[i] = a[i];
sort(b+l[x], b+r[x]+);
}
void pre() {
for(int i = n; i>; i--) {
ans += query(a[i]-);
update(a[i]);
}
for(int i = ; i<=cnt; i++) {
rebuild(i);
}
}
void cmp(int x, int y) {
if(x>y)
ans++;
if(x<y) //不要写else...可能相等
ans--;
}
void solve(int x, int y) {
if(a[x]>a[y])
ans--;
if(a[x]<a[y]) //不要写else！！
ans++;
if(belong[x] == belong[y]) {
for(int i = x+; i<y; i++) {
cmp(a[i], a[x]);
cmp(a[y], a[i]);
}
} else {
for(int i = x+; i<=r[belong[x]]; i++) {
cmp(a[i], a[x]);
cmp(a[y], a[i]);
}
for(int i = l[belong[y]]; i<y; i++) {
cmp(a[i], a[x]);
cmp(a[y], a[i]);
}
for(int i = belong[x]+; i<belong[y]; i++) {
ans -= lower_bound(b+l[i], b+r[i]+, a[x])-b--l[i];
ans += lower_bound(b+l[i], b+r[i]+, a[y])-b--l[i];
ans -= r[i] - (upper_bound(b+l[i], b+r[i]+, a[y])-b-l[i]);
ans += r[i] - (upper_bound(b+l[i], b+r[i]+, a[x])-b-l[i]);
}
}
swap(a[x], a[y]);
rebuild(belong[x]);
rebuild(belong[y]);
}
int main()
{
int m;
cin>>n;
block = sqrt(1.0*n);
if(n%block)
cnt = n/block+;
else
cnt = n/block;
for(int i = ; i<=cnt; i++) {
l[i] = (i-)*block+;
r[i] = i*block;
}
r[cnt] = n;
for(int i = ; i<=n; i++) {
scanf("%d", &a[i]);
c[i-] = a[i];
belong[i] = (i-)/block+;
}
sort(c, c+n);
int tmp = unique(c, c+n)-c;
for(int i = ; i<=n; i++) {
a[i] = b[i] = lower_bound(c, c+tmp, a[i])-c+;
}
pre();
cout<<ans<<endl;
cin>>m;
while(m--) {
int x, y;
scanf("%d%d", &x, &y);
if(x>y)
swap(x, y);
solve(x, y);
printf("%d\n", ans);
}
return ;
}