【莫队】Mato的文件管理

莫队

传送门：BZOJ3289

思路：交换次数等于区间中逆序对个数，直接莫队即可。

注意：元素的权值范围（似乎不用离散化）。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1200000
#define block(x) x/300
int n,m,ans,a[N],bit[N],ANS[N];
struct query{
	int x,y,ID;
	bool operator < (const query t) const{return block(x)<block(t.x) || (block(x)==block(t.x) && y<t.y);}
}qry[N];
void add(int x,int y){for (int i=x;i<N;i+=i&(-i)) bit[i]+=y;}
int Qry(int x){int sum=0; for (int i=x;i;i-=i&(-i)) sum+=bit[i]; return sum;}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;i++){scanf("%d%d",&qry[i].x,&qry[i].y); qry[i].ID=i;}
	sort(qry+1,qry+m+1);
	for (int i=1,j=0,k=1;k<=m;k++){
		while (i>qry[k].x){ans+=Qry(a[--i]-1); add(a[i],1);}
		while (j<qry[k].y){ans+=j-i+1-Qry(a[j+1]); add(a[++j],1);}
		while (i<qry[k].x){ans-=Qry(a[i]-1); add(a[i++],-1);}
		while (j>qry[k].y){ans-=j-i+1-Qry(a[j]); add(a[j--],-1);}
		ANS[qry[k].ID]=ans;
	}
	for (int i=1;i<=m;i++) printf("%d\n",ANS[i]);
}