「bzoj3787」Gty的文艺妹子序列 - 分块+树状数组+重构

题目大意

    给定一个正整数序列$a(1\le a_i\le n)$，支持单点修改，对于每次询问，输出$a_l\ldots a_r$中的逆序对数，强制在线。

---

题目分析

和上题一样，我们可以分块+树状数组预处理。

若此时我们再维护主席树的话，就要套一个树状数组，时间复杂度$O(n\sqrt n\log^2 n)\approx O(n^2)$，不能接受，故考虑使用上题的另一种思路。

每次我们更新点$a_i$时，要对对应的块信息进行维护，需要维护所有$R\ge Belong[i],L\le Belong[i]$的$f[L,R]$和$small,big$的前缀和，时间复杂度无法接受，似乎陷入僵局。

不妨修改状态定义，设$f[L,R]$表示仅计算$L$和$R$块产生的逆序对（不包括$L,R$本身产生的逆序对，$f[i,i]$无意义），$g[B,v]$表示前$B$个块，值为$v$的个数，$ans[B]$表示第$B$个块产生的逆序对数。

那么整块妹子$[L+1,R-1]$产生的答案就是：

$$\sum_{i=L+1}^{R-1}(Ans[i]+\sum_{j=i+1}^{R-1}f[i,j])$$

前缀和优化后得到：

$$\sum_{i=L+1}^{R-1}(Ans[i]+sum[i,R-1])$$

而$small,big$均可以表示为$g$的前缀和。

对$f[L,R]$的修改，枚举$L$，利用$g[]$修改掉对左边的影响，对右边的同理。

那么我们需要一个支持单点修改求前缀和的数据结构，它就是：树状数组！

用struct封装一下写起来可读性更高。

---

代码

#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],Ans[maxb],Belong[maxn],Left[maxb],Right[maxb],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;

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


struct BIT3 {
	int c[maxb];
#define lowbit(x) x&(-x)
	void add(int x,int v) {
		for(int i=x; i<=BCC; i+=lowbit(i))c[i]+=v;
	}
	int sum(int x) {
		int sum=0;
		for(int i=x; i>=1; i-=lowbit(i))sum+=c[i];
		return sum;
	}
} f[maxb];

void change(int pos,int v) {
	int block=Belong[pos];
	for(int i=block+1; i<=BCC; i++) {
		int tmp=-(num[i].sum(a[pos]-1)-num[i-1].sum(a[pos]-1));
		tmp+=num[i].sum(v-1)-num[i-1].sum(v-1);
		f[block].add(i,tmp);
	}
	for(int i=1; i<block; i++) {
		int tmp=-((num[i].sum(n)-num[i].sum(a[pos]))-(num[i-1].sum(n)-num[i-1].sum(a[pos])));
		tmp+=(num[i].sum(n)-num[i].sum(v))-(num[i-1].sum(n)-num[i-1].sum(v));
		f[i].add(block,tmp);
	}
	for(int i=block; i<=BCC; i++) {
		num[i].add(a[pos],-1);
		num[i].add(v,1);
	}
	a[pos]=v;
	Ans[block]=0;
	for(int i=Left[block]; i<=Right[block]; i++) {
		Ans[block]+=bit.sum(a[i]+1);
		bit.add(a[i],1);
	}
	for(int i=Left[block]; i<=Right[block]; i++)bit.clear(a[i]);
}

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(a[i]+1);
			bit.add(a[i],1);
		}
		for(int i=left; i<=right; i++)bit.clear(a[i]);
		return ans;
	}
	for(int i=L+1; i<=R-1; i++)ans+=Ans[i]+f[i].sum(R-1);
	for(int i=left; i<=Right[L]; i++) {
		ans+=num[R-1].sum(a[i]-1)-num[L].sum(a[i]-1);
		ans+=bit.sum(a[i]+1);
		bit.add(a[i],1);
	}
	for(int i=Left[R]; i<=right; i++) {
		ans+=num[R-1].sum(n)-num[R-1].sum(a[i])-(num[L].sum(n)-num[L].sum(a[i]));
		ans+=bit.sum(a[i]+1);
		bit.add(a[i],1);
	}
	for(int i=left; i<=Right[L]; i++)bit.clear(a[i]);
	for(int i=Left[R]; i<=right; i++)bit.clear(a[i]);
	return ans;
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	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++) {
		num[i]=num[i-1];
		for(int j=Left[i]; j<=Right[i]; j++)num[i].add(a[j],1);
	}
	for(int i=1; i<=BCC; i++) {
		for(int k=Left[i]; k<=Right[i]; k++) {
			Ans[i]+=bit.sum(a[k]+1);
			bit.add(a[k],1);
		}
		for(int j=i+1; j<=BCC; j++)
			for(int k=Left[j]; k<=Right[j]; k++)
				f[i].add(j,bit.sum(a[k]+1));
		for(int k=Left[i]; k<=Right[i]; k++)bit.clear(a[k]);
	}
	q=Get_Int();
	for(int i=1; i<=q; i++) {
		int opt=Get_Int(),left=Get_Int()^lastans,right=Get_Int()^lastans;
		if(opt==0)lastans=query(left,right),printf("%d\n",lastans);
		else change(left,right);
	}
	return 0;
}