【莫队】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]);
}