题目描述
排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。
红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足i<j且hi>hj的(i,j)数量。
幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。
输入输出格式
输入格式：
第一行为一个正整数n，表示小朋友的数量；
第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；
第三行为一个正整数m，表示交换操作的次数；
以下m行每行包含两个正整数ai和bi，表示交换位置ai与位置bi的小朋友。
输出格式：
输出文件共m+1行，第i行一个正整数表示交换操作i结束后，序列的杂乱程度。
输入输出样例
3130 150 14022 31 3
103
说明
【样例说明】
未进行任何操作时，(2,3)满足条件；
操作1结束后，序列为130 140 150，不存在满足i<j且hi>hj的(i,j)对；
操作2结束后，序列为150 140 130,(1,2)，(1,3)，(2,3)共3对满足条件的(i,j)。
对于15%的数据， n,m \le 15n,m≤15 ；
对于30%的数据， n,m \le 200n,m≤200 ；
在剩下的70%数据中：
存在15%的数据， h_ihi 各不相同；
存在15%的数据， 1^{10} \le h_i \le 1^{60}110≤hi≤160 ；
以上两类数据不存在交集。
对于100%的数据， 1 \le m \le 2\times 10^31≤m≤2×103 ， 1 \le n \le 2 \times 10^41≤n≤2×104 ， 1 \le h_i \le 10^91≤hi≤109 ， a_i \ne b_iai≠bi ， 1 \le a_i,b_i \le n1≤ai,bi≤n。
代码
直接暴力分块，然后在每一个块内排序。
查询时可以在每一个块内二分。
#include#include #include #include #define M 210#define N 20101 using namespace std; int n, m, t, S, C, ans;int a[N], b[N], c[N], st[M], ed[M], belong[N], sorted[M][M], len[M]; inline int read(){ int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; return x * f;} inline int query(int x){ int ret = 0; for(; x; x -= x & -x) ret += c[x]; return ret;} inline void add(int x){ for(; x <= m; x += x & -x) c[x]++;} inline void init(){ int i, j; S = sqrt(n); for(i = 1; i <= n; i += S) { st[++C] = i; ed[C] = min(i + S - 1, n); len[C] = ed[C] - st[C] + 1; } for(i = 1; i <= C; i++) { for(j = st[i]; j <= ed[i]; j++) belong[j] = i, sorted[i][j - st[i] + 1] = a[j]; sort(sorted[i] + 1, sorted[i] + len[i] + 1); }} inline void solve(int x, int y){ if(x > y) swap(x, y); int i, l = belong[x], r = belong[y], tmp; if(l == r) for(i = x + 1; i < y; i++) { ans -= (a[i] < a[x]); ans += (a[i] > a[x]); ans -= (a[i] > a[y]); ans += (a[i] < a[y]); } else { for(i = l + 1; i < r; i++) { ans -= lower_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[x]) - sorted[i] - 1; ans += len[i] - (upper_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[x]) - sorted[i]) + 1; ans -= len[i] - (upper_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[y]) - sorted[i]) + 1; ans += lower_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[y]) - sorted[i] - 1; } for(i = x + 1; i <= ed[l]; i++) { ans -= (a[i] < a[x]); ans += (a[i] > a[x]); ans -= (a[i] > a[y]); ans += (a[i] < a[y]); } for(i = st[r]; i < y; i++) { ans -= (a[i] < a[x]); ans += (a[i] > a[x]); ans -= (a[i] > a[y]); ans += (a[i] < a[y]); } } if(a[x] > a[y]) ans--; if(a[x] < a[y]) ans++; swap(a[x], a[y]); for(i = st[l]; i <= ed[l]; i++) sorted[l][i - st[l] + 1] = a[i]; for(i = st[r]; i <= ed[r]; i++) sorted[r][i - st[r] + 1] = a[i]; sort(sorted[l] + 1, sorted[l] + len[l] + 1); sort(sorted[r] + 1, sorted[r] + len[r] + 1);} int main(){ int i, x, y; n = read(); for(i = 1; i <= n; i++) a[i] = b[i] = read(); sort(b + 1, b + n + 1); m = unique(b + 1, b + n + 1) - b - 1; for(i = 1; i <= n; i++) { a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b; ans += i - query(a[i]) - 1, add(a[i]); } printf("%d\n", ans); init(); t = read(); while(t--) { x = read(); y = read(); solve(x, y); printf("%d\n", ans); } return 0;}