Description
排排坐, 吃果果, 生果甜嗦嗦, 大家笑呵呵. 你一个, 我一个, 大的分给你, 小的留给我, 吃完果果唱支歌, 大家乐和和.
红星幼儿园的小朋友们排起了长长地队伍, 准备吃果果. 不过因为小朋友们的身高有所区别, 排成的队伍高低错乱, 极不美观. 设第 \(i\) 个小朋友的身高为 \(h_i\), 我们定义一个序列的杂乱程度为: 满足 \(h_i \gt h_j\) 的 \((i, j)\) 数量. 幼儿园阿姨每次会选出两个小朋友, 交换他们的位置, 请你帮忙计算出每次交换后, 序列的杂乱程度. 为方便幼儿园阿姨统计, 在未进行任何交换操作时, 你也应该输出该序列的杂乱程度.
Input
第一行为一个正整数 \(n\), 表示小朋友的数量;
第二行包含 \(n\) 个由空格分隔的正整数 \(h_1, h_2, \ldots, 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 3Sample Output
1
0
3Data Range
对于 100% 的数据,\(1 \leq m \leq 2000, 1 \leq n \leq 20000, 1 \leq h_i \leq 10^9, a_i \neq b_i, 1 \leq a_i, b_i \leq n\)
Explanation
看一眼发现不会做然后觉得题解明显就是暴力的说......
既然都是分块了还不是暴力那是什么......
注意有可能出现重复的, 所以有大于和小于两种判断方式, 且集合不一定互补.
然后把题号写成 2143 怒调了好久无限 RE......
这样就要把所有元素分成 \(\sqrt{n}\) 块, 在每一块内查询复杂度为 \(O(\log \sqrt{n})\), 在所有块中执行查询操作得到的复杂度为 \(O(\sqrt{n} \log \sqrt{n})\); 然而修改的复杂度较为奇怪, 为 \(O(\sqrt{n} \log \sqrt{n})\) 每次.
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long lli;
const int maxn = 20010;
class BinaryIndexedTree { public:
int n, dat[maxn];
inline int lowbit(int x) {
return x & (-x); }
void change(int x, int val) {
for (; x <= n; x += lowbit(x)) dat[x] += val;
return ; }
int query(int x) { int res = 0;
for (; x > 0; x -= lowbit(x)) res += dat[x];
return res; }
void init(int n) { this->n = n; return ; }
} bit;
int n, m, block, cnt;
int l[maxn], r[maxn]; // Block boundaries
int belong[maxn]; // Item belongings
int disc[maxn], a[maxn], b[maxn]; // Descatterization and height
void rebuild(int x)
{
for (int i = l[x]; i <= r[x]; i++)
a[i] = b[i];
sort(a + l[x], a + r[x] + 1);
return ;
}
int find(bool type, int l, int r, int x)
{
int res = type ? r + 1 : l - 1,
t = type ? r : l;
while (l <= r) {
int mid = (l + r) >> 1;
if ((type && a[mid] > x) || (!type && a[mid] < x))
res = mid, (type ? r : l) = mid + (type ? -1 : 1);
else (type ? l : r) = mid + (type ? 1 : -1);
}
return type ? t - res + 1 : res - t + 1;
}
void solve(int x, int y, int& res)
{
if (x == y) return ;
// Swapping between the two causes differences
if (b[x] < b[y]) res += 1;
if (b[x] > b[y]) res -= 1;
// Determining whether in the same block
if (belong[x] == belong[y]) {
for (int i = x + 1; i < y; i++) {
if (b[i] > b[x]) res += 1;
if (b[i] < b[x]) res -= 1;
if (b[i] > b[y]) res -= 1;
if (b[i] < b[y]) res += 1;
}
} else {
int L = r[belong[x]], R = l[belong[y]];
for (int i = x + 1; i <= L; i++) {
if (b[i] > b[x]) res += 1;
if (b[i] < b[x]) res -= 1;
if (b[i] > b[y]) res -= 1;
if (b[i] < b[y]) res += 1;
}
for (int i = R; i < y; i++) {
if (b[i] > b[x]) res += 1;
if (b[i] < b[x]) res -= 1;
if (b[i] > b[y]) res -= 1;
if (b[i] < b[y]) res += 1;
}
for (int i = belong[x] + 1; i < belong[y]; i++) {
res -= find(false, l[i], r[i], b[x]);
res += find(false, l[i], r[i], b[y]);
res += find(true, l[i], r[i], b[x]);
res -= find(true, l[i], r[i], b[y]);
}
}
swap(b[x], b[y]);
rebuild(belong[x]), rebuild(belong[y]);
return ;
}
int main(int argc, char** argv)
{
scanf("%d", &n);
// Initializing block settings
block = sqrt(n);
cnt = n % block ? n / block + 1 : n / block;
for (int i = 1; i <= cnt; i++)
l[i] = (i-1) * block + 1,
r[i] = i * block;
r[cnt] = n; // Delimitation
for (int i = 1; i <= n; i++)
belong[i] = (i-1) / block + 1;
// De-scatterizing datum
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]),
disc[i] = a[i];
sort(disc + 1, disc + n + 1);
for (int i = 1; i <= n; i++)
a[i] = b[i] = lower_bound(disc + 1, disc + n + 1, a[i]) - disc;
// Getting initial status, stating how many are different
int res = 0;
bit.init(n);
for (int i = n; i >= 1; i--)
res += bit.query(b[i] - 1),
bit.change(b[i], 1);
for (int i = 1; i <= cnt; i++)
rebuild(i);
printf("%d\n", res);
// Getting data for each position
scanf("%d", &m);
for (int i = 1, x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
if (x > y) swap(x, y);
solve(x, y, res);
printf("%d\n", res);
}
return 0;
}