2023NOIP A层联测32 红楼 ~ Eastern Dream

题目大意

给定一个长度为$n$的序列$a$，有$m$次操作，每次操作有两种类型：

• 1 x y k，对于所有满足$(i-1)\mathrm{mod}x\le y$的$i$，将$a_i$的值加上$k$
• 2 l r，求$\sum _{i=l}^r{a}_i$

数组下标从$1$开始。

$1\le n,m\le 2\times 10^5,1\le x,y\le n,1\le a_i,k\le 10^9$

时间限制$800ms$，空间限制$32MB$。

题解

前置知识：根号分治

考虑根号分治，将每次修改和查询分为$x\le \sqrt{n}$和$x>\sqrt{n}$两种情况来考虑。

当$x\le \sqrt{n}$时，设$v_{i,j}$表示对于所有$(t-1)\mathrm{mod}i=j$的$t$，$a_t$要加上的值，$v{s}_{i,j}$为$v_{i,j}$的前缀和，也就是对于所有$(t-1)\mathrm{mod}i\le j$的$t$，$a_t$要加上的值。那么每次修改是$O(\sqrt{n})$的。对于查询，枚举每个$i$，求在$i$为模数时区间$[l,r]$对答案的贡献，对每个$i$都可以$O(1)$计算贡献，那么时间复杂度为$O(\sqrt{n})$。

当$x>\sqrt{n}$时，要修改的区间数量不超过$\sqrt{n}$个，那么我们可以用线段树来修改和查询，修改的时间复杂度为$O(\sqrt{n}\log n)$，查询的时间复杂度为$O(\log n)$。

这样的总时间复杂度为$O(m\sqrt{n}\log n)$，会$\text{TLE}$，下面考虑优化。

$x\le \sqrt{n}$的部分的时间复杂度是可以接受的，我们只需要优化$x>\sqrt{n}$部分的时间复杂度。

注意到单次修改要修改$O(\sqrt{n})$个区间，而单次查询只需要查询$1$个区间，我们考虑差分。

设$p_i$表示$a_i$经过修改后增加了多少，那么我们可以维护$p$的差分数组$c$。对于每次对区间$[l,r]$的修改，我们只需要修改$c_l$和$c_{r+1}$的值，是$O(1)$的，$O(\sqrt{n})$次单点修改的时间复杂度是$O(\sqrt{n})$的。

对于每次查询$[l,r]$，我们需要得到$\sum _{i=l}^r{p}_i=\sum _{i=l}^r\sum _{j=1}^i{c}_j$，下面来推一下这个式子：

$$\sum _{i=l}^r\sum _{j=1}^i{c}_j=\sum _{i=1}^{l-1}{c}_i\times (r-l+1)+\sum _{i=l}^r{c}_i\times (r-i+1)=(r-l+1)\sum _{i=1}^{l-1}{c}_i+(r+1)\sum _{i=l}^r{c}_i+\sum _{i=l}^{r}i\times c_i$$

我们可以用分块来维护$c_i$和$i\times c_i$，那么每次查询就相当于分块中的区间查询，一次查询的时间复杂度是$O(\sqrt{n})$的。用了分块之后，上面的单点修改操作仍然可以$O(1)$解决。

总时间复杂度为$O(m\sqrt{n})$。

虽然时间复杂度理论可行，但时限只有$800ms$，而且常数比较大，所以还是要卡一下常。

在下面的代码中，因为$c\le \sqrt{n}$的部分的常数比$c>\sqrt{n}$的部分的常数大，所以我们可以将根号分治中分类讨论的决策点调小一点，分为$c\le \frac{\sqrt{n}}{2}$和$c>\frac{\sqrt{n}}{2}$来分类讨论，这样能快一些。当然，这个决策点还是要根据你的代码来定。

code

#include
#define rg register
using namespace std;
const int N=200000,B=1000;
int n,m,bl,a[N+5];
long long ans=0,s[N+5],v[B+5][B+5],sv[B+5][B+5];
long long p1[N+5],w1[B+5],p2[N+5],w2[B+5];
inline int rd(){
	int t=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){
		t=t*10+ch-'0';
		ch=getchar();
	}
	return t;
}
inline int pos(int i){
	return (i-1)/bl+1;
}
inline void pt(int x,int k){
	if(x>n) return;
	p1[x]+=k;
	w1[pos(x)]+=k;
	p2[x]+=1ll*x*k;
	w2[pos(x)]+=1ll*x*k;
}
inline long long gt1(int l,int r){
	long long re=0;
	int vl=pos(l),vr=pos(r);
	if(vl==vr){
		for(rg int i=l;i<=r;i++) re+=p1[i];
		return re;
	}
	for(rg int i=l;i<=vl*bl;i++) re+=p1[i];
	for(rg int i=vl+1;i<=vr-1;i++) re+=w1[i];
	for(rg int i=vr*bl-bl+1;i<=r;i++) re+=p1[i];
	return re;
}
inline long long gt2(int l,int r){
	long long re=0;
	int vl=pos(l),vr=pos(r);
	if(vl==vr){
		for(rg int i=l;i<=r;i++) re+=p2[i];
		return re;
	}
	for(rg int i=l;i<=vl*bl;i++) re+=p2[i];
	for(rg int i=vl+1;i<=vr-1;i++) re+=w2[i];
	for(rg int i=vr*bl-bl+1;i<=r;i++) re+=p2[i];
	return re;
}
int main()
{
//	freopen("scarlet.in","r",stdin);
//	freopen("scarlet.out","w",stdout);
	n=rd();m=rd();
	bl=sqrt(n);
	if(n>=100) bl/=2;
	for(rg int i=1;i<=n;i++){
		a[i]=rd();
		s[i]=s[i-1]+a[i];
	}
	for(rg int o=1,tp,k;o<=m;o++){
		tp=rd();
		if(tp==1){
			int x=rd(),y=rd(),k=rd();
			y=min(y,x-1);
			if(x<=bl){
				for(rg int i=0;i<=y;i++) v[x][i]+=k;
				sv[x][0]=v[x][0];
				for(rg int i=1;i<x;i++) sv[x][i]=sv[x][i-1]+v[x][i];
			}
			else{
				for(rg int l=1;l<=n;l+=x){
					pt(l,k);pt(l+y+1,-k);
				}
			}
		}
		else{
			int l=rd(),r=rd();
			ans=s[r]-s[l-1];
			for(rg int i=1;i<=bl;i++){
				int vl=(l-1)/i,vr=(r-1)/i,ml=(l-1)%i,mr=(r-1)%i;
				ans+=sv[i][mr];
				if(ml>=1) ans-=sv[i][ml-1];
				ans+=(vr-vl)*sv[i][i-1];
			}
			ans+=(r-l+1)*gt1(1,l-1)+(r+1)*gt1(l,r)-gt2(l,r);
			printf("%lld\n",ans);
		}
	}
	return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93