bzoj3289 Mato的文件管理 莫队+树状数组

求逆序对个数，莫队套树状数组

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 50005
using namespace std;
int n,m,nn,a[N],c[5000005],be[N],maxn;
struct Query{
	int l,r,id,ans;
}qr[N];
bool cmp1(Query a,Query b){
	if(be[a.l]==be[b.l])
		return a.r<b.r;
	return be[a.l]<be[b.l];
}
bool cmp2(Query a,Query b){
	return a.id<b.id;
}
int lowbit(int x){
	return x&(-x);
}
void add(int x,int y){
	while(x<=maxn)
	{c[x]+=y;x+=lowbit(x);}
}
int query(int x){
	int ans=0;
	while(x)
	{ans+=c[x];x-=lowbit(x);}
	return ans;
}
void work(){
	int l=1,r=0,tot=0;
	for(int i=1;i<=m;i++){
		while(l<qr[i].l){
			tot-=query(a[l]-1);
			add(a[l++],-1);
		}
		while(l>qr[i].l){
			add(a[--l],1);
			tot+=query(a[l]-1);
		}
		while(r<qr[i].r){
			add(a[++r],1);
			tot+=r-l+1-query(a[r]);
			//printf("%d  %d
",query(a[r]),tot);
		}
		while(r>qr[i].r){
			tot-=r-l+1-query(a[r]);
			add(a[r--],-1);
		}
		qr[i].ans=tot;
	}
}
int main()
{
	scanf("%d",&n); nn=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		maxn=max(maxn,a[i]);
		be[i]=(i-1)/nn+1;
	}
	scanf("%d",&m);
	int l,r;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		qr[i].l=l; qr[i].r=r;
		qr[i].id=i;
	}
	sort(qr+1,qr+m+1,cmp1);
	work();
	sort(qr+1,qr+m+1,cmp2);
	for(int i=1;i<=m;i++)
		printf("%d
",qr[i].ans);
	return 0;
}