BZOJ3289 Mato的文件管理 <莫队+树状数组>

Problem

Mato的文件管理

Description

同学从各路神犇以各种方式收集了许多资料，这些资料一共有份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用自己写的程序才能访问。每天随机选一个区间，他今天就看编号在此区间内的这些资料。有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在单位时间内交换个相邻的文件（因为加密需要，不能随机访问）。想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？

Input

第一行一个正整数，表示的资料份数。
第二行由空格隔开的个正整数，第个表示编号为的资料的大小。
第三行一个正整数，表示会看几天资料。
之后行每行两个正整数，表示这天看区间的文件。

Output

行，每行一个正整数，表示这天需要交换的次数。

Sample Input

Sample Output

1
2

0
2

Hint

样例解释
第一天，不需要交换
第二天，可以把号交换次移到最后。
数据规模和约定

Source

By taorunz

标签：莫队 树状数组

Solution

因此此问题等价于求区间逆序对数，傻逼莫队水过。
离线下所有询问，每次加入或删除一个数用树状数组维护，计算会增加或减少多少对逆序对，更新答案即可。

Code

#include <bits/stdc++.h>
#define MAX_N 50000
using namespace std;
const int MAGIC = 230;
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, q, a[MAX_N+5], b[MAX_N+5], c[MAX_N+5], tr[MAX_N+5];
struct query {int l, r, lb, rb, id;} Q[MAX_N+5]; int ans[MAX_N+5];
bool cmpn (const int &x, const int &y) {return c[x] < c[y];}
bool cmpq (const query &x, const query &y) {return x.lb == y.lb ? x.rb < y.rb : x.lb < y.lb;}
void inc(int p) {for (; p <= m; p += (p&-p)) tr[p]++;}
void dec(int p) {for (; p <= m; p += (p&-p)) tr[p]--;}
int sum(int p) {int s = 0; for (; p; p -= (p&-p)) s += tr[p]; return s;}
int get_bef(int p) {return sum(p-1);}
int get_aft(int p) {return sum(m)-sum(p);}
int main() {
    read(n);
    for (int i = 1; i <= n; i++)
        read(c[i]), b[i] = i;
    sort(b+1, b+n+1, cmpn);
    for (int i = 1; i <= n; a[b[i++]] = m)
        if (c[b[i]]^c[b[i-1]]) m++;
    read(q);
    for (int i = 1; i <= q; i++)
        read(Q[i].l), read(Q[i].r), Q[i].id = i, 
        Q[i].lb = Q[i].l/MAGIC, Q[i].rb = Q[i].r/MAGIC;
    sort(Q+1, Q+q+1, cmpq);	int tot = 0;
    for (int i = 1, l = 1, r = 0; i <= q; i++) {
        for (; l > Q[i].l; l--) tot += get_bef(a[l-1]), inc(a[l-1]);
        for (; r < Q[i].r; r++) tot += get_aft(a[r+1]), inc(a[r+1]);
        for (; l < Q[i].l; l++) tot -= get_bef(a[l]), dec(a[l]);
        for (; r > Q[i].r; r--) tot -= get_aft(a[r]), dec(a[r]);
        ans[Q[i].id] = tot;
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0;
}