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

Problem

Mato的文件管理

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

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

Input

第一行一个正整数$n$，表示$\mathrm{Mato}$的资料份数。
第二行由空格隔开的$n$个正整数，第$i$个表示编号为$i$的资料的大小。
第三行一个正整数$q$，表示$\mathrm{Mato}$会看几天资料。
之后$q$行每行两个正整数$l,r$，表示$\mathrm{Mato}$这天看$[l,r]$区间的文件。

Output

$q$行，每行一个正整数，表示$\mathrm{Mato}$这天需要交换的次数。

Sample Input

4
1 4 2 3
2
1 2
2 4

Sample Output

0
2

Hint

样例解释
第一天，$\mathrm{Mato}$不需要交换
第二天，$\mathrm{Mato}$可以把$2$号交换$2$次移到最后。
数据规模和约定
$n,q\le5\times10^4$

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;
}