「vijos-bashu」序列杀手 / 「CodeChef FNCS」Chef and Churu - 分块套分块

题目大意

传送门

---

题目分析

对$f$数组拆分成$\sqrt n$个块，每个块预处理这个块中每一个$a_i$出现了多少次，以及初始状态下每个块$f_i$的和，用差分可以在$O(n\sqrt n)$时间内完成预处理。

对于修改操作，直接将每一段的$f_i$的和更新一下，因为预处理了每个数的出现次数所以很方便实现，时间复杂度$O(\sqrt n)$。

对于询问操作，将询问区间分为整块和零散的点。
整块已经维护出和，故$O(\sqrt n)$即可完成整块的询问，剩下的$O(\sqrt n)$个单点可以使用树状数组求和，但时间复杂度是$O(\sqrt n \log n)$，本题可过。
我们可以对$a$数组再分块，对$a$中每个块作前缀和，修改的时候重构对应块的前缀和并重构块与块之间的前缀和，这样我们对于每个零碎的点就可以$O(1)$得到其值。
询问时间复杂度降为$O(\sqrt n)$，但常数有所上升。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL 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=100005;
int n,m,Belong[maxn],l[maxn],r[maxn],Left[maxn],Right[maxn],BCC=0;
LL a[maxn],f[maxn],cnt[325][maxn],sum[maxn],sum_block[maxn];
void Modify(int pos,LL v) {
	for(int i=1; i<=BCC; i++)f[i]+=(v-a[pos])*cnt[i][pos];
	a[pos]=v;
	for(int i=pos; i<=Right[Belong[pos]]; i++) {
		if(i==Left[Belong[pos]])sum[i]=a[i];
		else sum[i]=sum[i-1]+a[i];
	}
	for(int i=Belong[pos]; i<=BCC; i++)sum_block[i]=sum_block[i-1]+sum[Right[i]];
}
LL Sum(int x,int y) {
	int L=Belong[x],R=Belong[y];
	LL ans=0;
	if(L==R) {
		if(x==Left[L])return sum[y];
		else return sum[y]-sum[x-1];
	} else if(L+1==R) {
		if(x==Left[L])return sum[Right[L]]+sum[y];
		else return sum[Right[L]]-sum[x-1]+sum[y];
	} else {
		if(x==Left[L])return sum_block[R-1]-sum_block[L-1]+sum[y];
		else return sum[Right[L]]-sum[x-1]+sum_block[R-1]-sum_block[L]+sum[y];
	}
}
LL Query(int x,int y) {
	int L=Belong[x],R=Belong[y];
	LL ans=0;
	if(L==R)for(int i=x; i<=y; i++)ans+=Sum(l[i],r[i]);
	else {
		for(int i=L+1; i<=R-1; i++)ans+=f[i];
		for(int i=x; i<=Right[L]; i++)ans+=Sum(l[i],r[i]);
		for(int i=Left[R]; i<=y; i++)ans+=Sum(l[i],r[i]); 
	}
	return ans;
}
int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	for(int i=1; i<=n; i++) {
		l[i]=Get_Int();
		r[i]=Get_Int();
	}
	int size=sqrt(n);
	for(int i=1; i<=n; i++) {
		Belong[i]=(i-1)/size+1;
		if(!Left[Belong[i]])Left[Belong[i]]=i,BCC++;
		Right[Belong[i]]=i;
		if(i==Left[Belong[i]])sum[i]=a[i];
		else sum[i]=sum[i-1]+a[i];
	}
	for(int i=1; i<=BCC; i++) {
		for(int j=Left[i]; j<=Right[i]; j++) { //差分 
			cnt[i][l[j]]++;
			cnt[i][r[j]+1]--;
		}
		for(int j=1; j<=n; j++) { //统计 
			cnt[i][j]+=cnt[i][j-1];
			f[i]+=cnt[i][j]*a[j];
		}
	}
	for(int i=1; i<=BCC; i++)sum_block[i]=sum_block[i-1]+sum[Right[i]];
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		int opt=Get_Int(),x=Get_Int();
		LL y=Get_Int();
		if(opt==1)Modify(x,y);
		else printf("%lld\n",Query(x,y));
	}
	return 0;
}