3289: Mato的文件管理
Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 2368 Solved: 971
[Submit][Status][Discuss]
Description
Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内交换2个相邻的文件（因为加密需要，不能随机访问）。Mato想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？
Input
第一行一个正整数n，表示Mato的资料份数。
第二行由空格隔开的n个正整数，第i个表示编号为i的资料的大小。
第三行一个正整数q，表示Mato会看几天资料。
之后q行每行两个正整数l、r，表示Mato这天看[l,r]区间的文件。
Output
q行，每行一个正整数，表示Mato这天需要交换的次数。
Sample Input
4
1 4 2 3
2
1 2
2 4
Sample Output
0
2
HINT
Hint
n,q <= 50000
样例解释：第一天，Mato不需要交换
第二天，Mato可以把2号交换2次移到最后。
Source
小生的第二道莫队算法。易知一段区间内的最小交换次数就是这段区间内的逆序对数，这个可以通过用树状数组动态维护。树状数组是按权值组织的，当在区间右侧新加入一个元素时，新形成的逆序对数就是前面区间中严格大于该元素的元素个数，反之亦然，请客官自行推导吧(ﾉ*･ω･)ﾉ。
#include <bits/stdc++.h> template <class T>
inline void read(T &num) {
register int neg = false;
register int bit = getchar(); while (bit <= '') {
if (bit == '-')
neg ^= neg;
bit = getchar();
} num = ; while (bit >= '') {
num = num*
+ bit - '';
bit = getchar();
} if (neg)num = -num;
} const int siz = ; int n, m, s, num[siz], tmp[siz], bit[siz], answer; struct query {
int l, r, id, ans;
}qry[siz]; inline bool cmp_lr(const query &A, const query &B) {
if (A.l / s != B.l / s)
return A.l < B.l;
else
return A.r < B.r;
} inline bool cmp_id(const query &A, const query &B) {
return A.id < B.id;
} inline void add(int k, int v) {
for (; k <= n; k += k&-k)bit[k] += v;
} inline int ask(int k) {
int ret = ;
for (; k >= ; k -= k&-k)ret += bit[k];
return ret;
} signed main(void) {
read(n); for (int i = ; i <= n; ++i)
read(num[i]); memcpy(tmp, num, sizeof(tmp)); std::sort(tmp + , tmp + + n); int tot = std::unique(tmp + , tmp + + n) - tmp; for (int i = ; i <= n; ++i)
num[i] = std::lower_bound(tmp, tmp + tot, num[i]) - tmp; read(m); for (int i = ; i <= m; ++i)
read(qry[i].l), read(qry[i].r), qry[i].id = i; s = sqrt(n); std::sort(qry + , qry + + m, cmp_lr); for (int i = , x = , y = ; i <= m; ++i) {
while (x < qry[i].l)answer -= ask(num[x] - ), add(num[x], -), ++x;
while (x > qry[i].l)--x, answer += ask(num[x] - ), add(num[x], +);
while (y < qry[i].r)++y, answer += ask(n) - ask(num[y]), add(num[y], +);
while (y > qry[i].r)answer -= ask(n) - ask(num[y]), add(num[y], -), --y;
qry[i].ans = answer;
} std::sort(qry + , qry + + m, cmp_id); for (int i = ; i <= m; ++i)
printf("%d\n", qry[i].ans);
}
@Author: YouSiki
