「bzoj3744」Gty的妹子序列 - 分块+树状数组（+主席树）

题目大意

    给定一个正整数序列$a$,对于每次询问,输出$a_l\ldots a_r$中的逆序对数,强制在线。

---

题目分析

逆序对数不好进行处理，一般离线处理，但因为强制在线，不妨考虑暴力算法：分块。

将区间分为$\sqrt n$个块，并统计出$f[L,R]$表示$[L,R]$块内的答案（树状数组），这样我们询问的时候只需要分为整块的（妹子）和零碎的（妹子）。

接下来，我们只需要统计左零碎妹子与右零碎妹子所产生的逆序对 与 零碎妹子与整块妹子产生的逆序对。

第一部分可以树状数组暴力统计，第二部分可以使用主席树（有点卡常）。

当然我们可以不用主席树，我们统计$small[B,v]$表示前$B$个块中比$v$小的个数，$big[B,v]$表示前$B$个块中比$v$大的个数，显然我们均可以使用$O(n\sqrt n)$的时间维护出$small$和$big$，然后我们就可以方便统计第二部分产生的逆序对了。

时间复杂度$O(n\sqrt n\log n)$，常数很小。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=50005,maxb=255;

int n,q,BCC,a[maxn],b[maxn],Belong[maxn],Left[maxb],Right[maxb],f[maxb][maxb],small[maxb][maxn],big[maxb][maxn],lastans;

struct BIT {
	int c[maxn];
#define lowbit(x) x&(-x)
	void add(int x,int v) {
		for(int i=x; i>=1; i-=lowbit(i))c[i]+=v;
	}
	void clear(int x) {
		for(int i=x; i>=1; i-=lowbit(i))c[i]=0;
	}
	int sum(int x) {
		int sum=0;
		for(int i=x; i<=n; i+=lowbit(i))sum+=c[i];
		return sum;
	}
} bit;

int query(int left,int right) {
	int L=Belong[left],R=Belong[right],ans=0;
	if(R-L<=1) {
		for(int i=left; i<=right; i++) {
			ans+=bit.sum(b[i]+1);
			bit.add(b[i],1);
		}
		for(int i=left; i<=right; i++)bit.clear(b[i]);
		return ans;
	}
	ans=f[L+1][R-1];
	for(int i=left; i<=Right[L]; i++) {
		ans+=small[R-1][b[i]-1]-small[L][b[i]-1];
		ans+=bit.sum(b[i]+1);
		bit.add(b[i],1);
	}
	for(int i=Left[R]; i<=right; i++) {
		ans+=big[R-1][b[i]+1]-big[L][b[i]+1];
		ans+=bit.sum(b[i]+1);
		bit.add(b[i],1);
	}
	for(int i=left; i<=Right[L]; i++)bit.clear(b[i]);
	for(int i=Left[R]; i<=right; i++)bit.clear(b[i]);
	return ans;
}

void Discretization() {
	sort(a+1,a+n+1);
	int cnt=unique(a+1,a+n+1)-a-1;
	for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a;
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)b[i]=a[i]=Get_Int();
	Discretization();
	int size=sqrt(n);
	for(int i=1; i<=n; i++) {
		Belong[i]=(i-1)/size+1;
		if(!Left[Belong[i]])BCC++,Left[Belong[i]]=i;
		Right[Belong[i]]=i;
	}
	for(int i=1; i<=BCC; i++) {
		memcpy(small[i],small[i-1],sizeof(small[i-1]));
		memcpy(big[i],big[i-1],sizeof(big[i-1]));
		for(int j=Left[i]; j<=Right[i]; j++)small[i][b[j]]++,big[i][b[j]]++;
	}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=BCC; j++)
			small[j][i]+=small[j][i-1];
	for(int i=n; i>=1; i--)
		for(int j=1; j<=BCC; j++)
			big[j][i]+=big[j][i+1];
	for(int i=1; i<=BCC; i++) {
		for(int j=i; j<=BCC; j++) {
			f[i][j]=f[i][j-1];
			for(int k=Left[j]; k<=Right[j]; k++) {
				f[i][j]+=bit.sum(b[k]+1);
				bit.add(b[k],1);
			}
		}
		memset(bit.c,0,sizeof(bit.c));
	}
	q=Get_Int();
	for(int i=1; i<=q; i++) {
		int left=Get_Int()^lastans,right=Get_Int()^lastans;
		lastans=query(left,right);
		printf("%d\n",lastans);
	}
	return 0;
}