专栏文章

线段树扩展应用

ll1ng21y12026
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingcq5w
此快照首次捕获于
2025/12/02 01:58
3 个月前
此快照最后确认于
2025/12/02 01:58
3 个月前
查看原文

线段树扩展应用

（一）区间最值操作

考虑区间 chkmin，使用 Segment tree beats。算法如下：
维护区间最大值，严格次大值，最大值出现次数。下称 f1,f2,fcf1,f2,fc。
当对区间 chkmin(v)chkmin(v) 时：
  • 若 v≥f1v\ge f1，这个区间不会被修改。直接返回。
  • 若 f2<v<f1f2<v<f1，这个区间内只有最大值被修改。
    我们对最大值单独开一个标记维护。此时相当于对最大值 +(v−f1)+(v-f1)。
  • 若 v≤f2v\le f2，我们递归子区间。
当只有单点修改时，时间复杂度是 O(nlog⁡n)O(n\log n) 的。
考虑只有 v≤f2v\le f2 时递归子区间可能产生多余贡献。此时，该区间的最大值和次大值合并。也就是说，这个区间的不同值的个数 −1-1，然后造成了 11 的贡献。
线段树每层的不同值个数总和是 O(n)O(n) 的，log⁡\log 层合一起总共 O(nlog⁡n)O(n\log n) 个不同值。一次单点修改给整颗树增加 log⁡n\log n 个不同值，总共最多增加 O(mlog⁡n)O(m\log n) 个不同值。故最多多造成 O(nlog⁡n)O(n\log n) 的贡献。
当有区间加时，时间复杂度是 O(nlog⁡2n)O(n\log^2 n) 的。
一次区间加会将它作用的整区间的所有父节点的不同值个数 +1+1，共作用 log⁡\log 个子区间，每个子区间 log⁡\log 个祖先，总共会增加 O(mlog⁡2n)O(m\log^2 n) 个不同值。
那么现在问题变成了：区间加，针对区间最大值加，区间历史最值，区间和。
若没有历史最值，我们可以维护区间内最大值的个数，并单独记录最大值的加标记；另外维护非最大值的加标记，那么区间和的变化量容易求出。
考虑区间历史最值，可以经典地维护最大值加标记的历史最大值，那么区间历史最值可以由之前的 maxmax 加上加标记的历史 maxmax 更新。
需要注意的是，在下传区间最大值加标记时，我们需要知道子区间的 maxmax 是否是父区间的 maxmax。我们不能直接调用值，因为可能有一个还没有被标记修改。
由于实际上只有区间最大值加，所以区间内最大值的分布在 upup 之前都不改变，于是我们记录区间 maxmax 的是否来源于 ls,rsls,rs 即可判断 ls,rsls,rs 的 maxmax 是否是 xx 的 maxmax 即可。
开始实现，我们要维护：
C
ll fs[N<<2];// 区间和
int len[N<<2];// 区间长
int f1[N<<2],f2[N<<2],fc[N<<2];// 区间最大值 , 次大值 , 最大值个数
int fh[N<<2];// 区间历史最大值
bool ml[N<<2],mr[N<<2];// 区间最大值是否是 ls/rs 的最大值（即 up 时是否由 ls/rs 转移 max）
int gs1[N<<2],gh1[N<<2];// 最大值加标记 , gs1的历史最大值
int gs2[N<<2],gh2[N<<2];// 非最大值加标记 , gs2的历史最大值
然后依次考虑 up,dnup,dn 内各个值的转移更新。
C
inline void up(int x)
{
	fs[x]=fs[ls]+fs[rs];
	if(f1[ls]==f1[rs])
	{
		f1[x]=f1[ls];
		f2[x]=max(f2[ls],f2[rs]);
		fc[x]=fc[ls]+fc[rs];
		ml[x]=1,mr[x]=1;
	}
	else if(f1[ls]>f1[rs])
	{
		f1[x]=f1[ls];
		f2[x]=max(f2[ls],f1[rs]);
		fc[x]=fc[ls];
		ml[x]=1,mr[x]=0;
	}else{
		f1[x]=f1[rs];
		f2[x]=max(f2[rs],f1[ls]);
		fc[x]=fc[rs];
		ml[x]=0,mr[x]=1;
	}
	fh[x]=max(fh[ls],fh[rs]);
}
inline void dn(int x)
{
	if(gh1[x]==-inf)return;
	fs[x]+=1ll*gs1[x]*fc[x]+1ll*gs2[x]*(len[x]-fc[x]);
	fh[x]=max(fh[x],f1[x]+gh1[x]);
	f1[x]+=gs1[x];
	f2[x]+=gs2[x];
	if(x<=(n<<1))
	{
		if(ml[x])
		{
			gh1[ls]=max(gh1[ls],gs1[ls]+gh1[x]);
			gs1[ls]+=gs1[x];
		}else{
			gh1[ls]=max(gh1[ls],gs1[ls]+gh2[x]);
			gs1[ls]+=gs2[x];
		}
		gh2[ls]=max(gh2[ls],gs2[ls]+gh2[x]);
		gs2[ls]+=gs2[x];
		if(mr[x])
		{
			gh1[rs]=max(gh1[rs],gs1[rs]+gh1[x]);
			gs1[rs]+=gs1[x];
		}else{
			gh1[rs]=max(gh1[rs],gs1[rs]+gh2[x]);
			gs1[rs]+=gs2[x];
		}
		gh2[rs]=max(gh2[rs],gs2[rs]+gh2[x]);
		gs2[rs]+=gs2[x];
	}
	gs1[x]=gs2[x]=0,gh1[x]=gh2[x]=-inf;
}
void bld(int x=1,int l=1,int r=n)
{
	gs1[x]=gs2[x]=0,gh1[x]=gh2[x]=-inf;
	len[x]=r-l+1;
	if(l==r)fs[x]=a[l],f1[x]=a[l],f2[x]=-inf,fc[x]=1,fh[x]=a[l];
	else bld(ls,l,mid),bld(rs,mid+1,r),up(x);
}
void pls(int le,int ri,int v,int x=1,int l=1,int r=n)
{
	if(le<=l&&r<=ri)
	{
		gs1[x]+=v,gh1[x]=max(gh1[x],gs1[x]);
		gs2[x]+=v,gh2[x]=max(gh2[x],gs2[x]);
		dn(x);
		return;
	}
	dn(ls),dn(rs);
	if(le<=mid)pls(le,ri,v,ls,l,mid);
	if(mid<ri)pls(le,ri,v,rs,mid+1,r);
	up(x);
}
void cmn(int le,int ri,int v,int x=1,int l=1,int r=n)
{
	if(v>=f1[x])return;
	if(le<=l&&r<=ri&&f2[x]<v)
	{
		gs1[x]+=v-f1[x],gh1[x]=max(gh1[x],gs1[x]);
		dn(x);
		return;
	}
	dn(ls),dn(rs);
	if(le<=mid)cmn(le,ri,v,ls,l,mid);
	if(mid<ri)cmn(le,ri,v,rs,mid+1,r);
	up(x);
}
可以看一下 chkmin 的写法。只在满足 sec<v<maxsec<v<max 时针对 maxmax 进行修改。剩下的情况递归或者返回。

例题

P6242 【模板】线段树 3（区间最值操作、区间历史最值）。

（二）历史最值

有的历史最值较为简单，可以直接标记维护，无需矩乘分析。
标记 gs,ghgs,gh。ghgh 记录 gsgs 的最值。
C
tree_history[x]=max(tree_history[x],tree_val[x]+tag_history[x]);
tree_val[x]+=tag_val[x];

tag_history[ls]=max(tag_history[ls],tag_val[ls]+tag_history[x]);
tag_val[ls]+=tag_val[x];
考虑前后合并即可。
像区间 chkmin 区间加这种，可以转化为只有区间加，我们就可以方便地直接维护。
但是有的题目有很多操作（区间加、区间赋值），还要维护历史最值，那我们使用矩乘分析。

例题

P4314 CPU 监控：区间加、区间赋值、历史最值。

使用 (1,v,h)(1,v,h) 表示区间最大值，区间历史最值。
定义广义矩阵乘法 (+,max⁡)(+,\max)。考虑区间加 kk：
[0vh][0−inf−inf−infkk−inf−inf0][0v+kmax⁡(h,v+k)]\begin{bmatrix} 0&v&h \end{bmatrix} \begin{bmatrix} 0&-inf&-inf\\ -inf&k&k\\ -inf&-inf&0 \end{bmatrix} \begin{bmatrix} 0&v+k&\max(h,v+k) \end{bmatrix}
构造时，Ai,jA_{i,j} 表示 i→ji\to j 的贡献，即左边 [1,v,h][1,v,h] 的第 ii 个，对右边 [1,v+k,max⁡(h,v+k)][1,v+k,\max(h,v+k)] 的第 jj 个的贡献系数。
区间赋值 kk：
[0vh][0kk−inf−inf−inf−inf−inf0][0kmax⁡(h,k)]\begin{bmatrix} 0&v&h \end{bmatrix} \begin{bmatrix} 0&k&k\\ -inf&-inf&-inf\\ -inf&-inf&0 \end{bmatrix} \begin{bmatrix} 0&k&\max(h,k) \end{bmatrix}
注意到转移矩形只有右上角四个位置有值，设为 (a,b,c,d)(a,b,c,d)。即四个标记。
可以提取带入得出 ff 与标记的合并式：
[0vh][0ab−infcd−inf−inf0][0max⁡(a,c+v)max⁡(b,d+v,h)]\begin{bmatrix} 0&v&h \end{bmatrix} \begin{bmatrix} 0&a&b\\ -inf&c&d\\ -inf&-inf&0 \end{bmatrix} \begin{bmatrix} 0&\max(a,c+v)&\max(b,d+v,h) \end{bmatrix}
提取得 (v,h)⊙(a,b,c,d)→(max⁡(a,c+v),max⁡(b,d+v,h))(v,h)\odot (a,b,c,d)\to (\max(a,c+v),\max(b,d+v,h))。
同样可以提取标记之间的合并式：
[0ab−infcd−inf−inf0][0xy−infzw−inf−inf0]=[0max⁡(x,a+z)max⁡(y,a+w,b)−infc+zmax⁡(c+w,d)−inf−inf0]\begin{bmatrix} 0&a&b\\ -inf&c&d\\ -inf&-inf&0 \end{bmatrix} \begin{bmatrix} 0&x&y\\ -inf&z&w\\ -inf&-inf&0 \end{bmatrix} = \begin{bmatrix} 0&\max(x,a+z)&\max(y,a+w,b)\\ -inf&c+z&\max(c+w,d)\\ -inf&-inf&0 \end{bmatrix}
提取得 (a,b,c,d)⊙(x,y,z,w)→(max⁡(x,a+z),max⁡(y,a+w,b),c+z,max⁡(c+w,d)(a,b,c,d)\odot (x,y,z,w)\to (\max(x,a+z),\max(y,a+w,b),c+z,\max(c+w,d)。
注意判断 −inf−inf-inf-inf 爆 int。

（三）历史和

历史标记本质上是矩阵，代表了各树上值在操作作用下的互相转移关系，Ai,jA_{i,j} 表示 i→ji\to j 的贡献。
用 (1,v,h)(1,v,h) 表示树上点值 ff 的信息。vv 为点的值，hh 为 vv 的历史和。
考虑修改时 ff 的转移，并用矩阵表示。矩乘为 (×,+)(\times ,+) 矩乘。
赋值 xx：
[1vh][1x0000001][1xh]\begin{bmatrix} 1&v&h \end{bmatrix} \begin{bmatrix} 1&x&0\\ 0&0&0\\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&x&h \end{bmatrix}
由于**Ai,jA_{i,j} 表示 i→ji\to j 的贡献**，我们可以得出 11 对 1,_,_1,\_,\_ 的贡献系数为 1,x,01,x,0，剩下同理。
加 xx：
[1vh][1x0010001][1v+xh]\begin{bmatrix} 1&v&h \end{bmatrix} \begin{bmatrix} 1&x&0\\ 0&1&0\\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&v+x&h \end{bmatrix}
更新 tt 次历史和：同理地考虑 i→ji\to j 的贡献。
[1vh][10001t001][1vh+vt]\begin{bmatrix} 1&v&h \end{bmatrix} \begin{bmatrix} 1&0&0\\ 0&1&t\\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&v&h+vt \end{bmatrix}
不像历史最值，历史和要求所有位置都要更新（不止当前修改的位置）所以每次要对全局打一个更新历史和的标记。
表示信息的位置只有右上角的 44 个，令它们为 (a,b,c,d)(a,b,c,d)（其实它们代表标记）
可以提取 ff 与标记的合并式：
[1vh][1ab0cd001]=[1,a+vc,b+vd+h]\begin{bmatrix} 1&v&h \end{bmatrix} \begin{bmatrix} 1&a&b\\ 0&c&d\\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 1,a+vc,b+vd+h \end{bmatrix}
考虑转移矩阵的合并，有：
[1ab0cd001][1xy0zw001]=[1x+azy+aw+b0czcw+d001]\begin{bmatrix} 1&a&b\\ 0&c&d\\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&x&y\\ 0&z&w\\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 1&x+az&y+aw+b\\ 0&cz&cw+d\\ 0&0&1 \end{bmatrix}
根据上面两条式子，可以提取 ff 与标记，标记与标记之间的合并式。
ff 与标记合并：(1,v,h)×(a,b,c,d)=(1,a+vc,b+vd+h)(1,v,h)\times (a,b,c,d)=(1,a+vc,b+vd+h)。
标记与标记合并： (a,b,c,d)×(x,y,z,w)=(x+az,y+aw+b,cz,cw+d)(a,b,c,d)\times (x,y,z,w)=(x+az,y+aw+b,cz,cw+d)。
可以 struct 维护 (1,v,h),(a,b,c,d)(1,v,h),(a,b,c,d) 并重载 +,×+,\times 运算，代码会很清晰。
优化可以拆掉重载，用 #define 来运算合并。

例题

你、组乐队了吧：转化为“矩形信息”扫描线 + 正难则反 + 维护区间历史 0 个数和。

考虑描述合法区间：枚举 min,maxmin,max 值，可以求出包含 aia_i 且 aia_i 为最小值的极大区间 [al,ar][al,ar]，则当满足 l∈[al,i],r∈[i,ar]l\in[al,i],r\in [i,ar] 时 min⁡a=ai\min_a=a_i；同理，当满足 l∈[bl,i],r∈[i,br]l\in[bl,i],r\in [i,br] 时 min⁡b=bi\min_b =b_i。
可以将上述 l,rl,r 的取值范围表示为矩形 A([al,i],[i,ar])A([al,i],[i,ar])，则当 (l,r)(l,r) 在矩形 AA 内时，min⁡a=ai\min_a=a_i，BB 同理。
则刻画合法区间 [l,r][l,r] 为：当点 (l,r)(l,r) 在矩形 A∩BA\cap B 内时合法。
但是我们还有 max⁡\max 的限制，两个限制不好做，可以正难则反，统计不合法的区间数量：min⁡a≠minb\min_a\not =min_b 或 max⁡a≠max⁡b\max_a\not = \max_b。
那么可以刻画不合法区间 [l,r][l,r] 为：当点 (l,r)(l,r) 在矩形 A∪BA\cup B 内且不在 A∩BA\cap B 内时 [l,r][l,r] 不合法。
由于两种限制满足一种即不合法，于是我们可以将 min⁡\min 时不合法的点“涂黑”，再将 max⁡\max 时不合法的点“涂黑”。则黑点即为不合法点。
相当于先进行若干次矩形加，然后矩形查询值为 00 的点的个数。
于是问题变成了矩形扫描线问题。（因为总点数是 O(n2)O(n^2) 的，不能够直接朴素二维数点）
经典地枚举一维，另一维变成区间加，维护区间历史值为 00 的点的个数。
采用时间戳法：
注意到 00 一定是最小值，于是可以维护最小值的个数，若为 00，则使用 Δtime×cntmin\Delta time\times cnt_{min} 贡献历史和。
思路：通过懒标记先记录一些操作（需要涉及懒标记的合并），下传时贡献给 ff。
使用线段树维护：
树点 ff 维护：s,t,c,ns,t,c,n 表示：历史和、子树中最后一次修改时间、最小值的个数、最小值。
标记 gg 维护：s,t,w,c,ns,t,w,c,n 表示：标记合并时的历史和、标记开始结束的时间、总共的改变量、改变量的最小值。
然后分别考虑 f→f′,g→f,g→g′f\to f',g\to f,g\to g' 中各变量的变化情况即可。
细节错误：
  • 每个点子树中最后修改时间必须统一。如果修改了子树，upup 时需要将多出时间中的贡献算上，并更新父亲时间。
  • 标记必须要有“无标记”状态，若无，会出现不可控情况。
采用矩乘法：
维护历史 00 的个数不能直接表示为矩形。考虑转化。
00 是最小值。类似线段树 3 中的针对最大值标记，我们在全局针对最小值为 00 的区间打上一次更新历史和的标记。
显然若区间最小值不为 00，则不需要更新历史和。否则历史和 hh 加上最小值个数 cc。这样就可以用矩乘法了。
做法：
若全局最小值不为 00，不打历史和标记。
否则，我们只对 ls,rsls,rs 中最小值与父区间的最小值相同的区间进行历史标记下传。
由于转移关系只有 c→hc\to h 且在区间加中，对于 cc 会变的区间（父区间），它的标记已经在修改前完成了。对于 cc 不变的区间（整子区间）cc 不变。
于是我们直接维护一个区间被打历史和标记的次数 dd 即可。并直接 c×d→hc\times d\to h。

P8868 [NOIP2022] 比赛：扫描线 + 覆盖 a,b、a*b 历史和。

考虑对询问扫描线，维护对于每个 ll ，维护 cl=∑r≥lmax⁡l,r(a)max⁡l,r(b)c_l=\sum_{r\ge l}\max_{l,r}(a)\max_{l,r}(b)。
于是每次加入一个位置 ii 时，cc 的变化相当于在 a,ba,b 中找到 ii 前面第一个大于 ai,bia_i,b_i 的位置 pa,pbpa,pb。
然后将 i∈[pa,i]i\in[pa,i] 的 max⁡a\max a 变成 aia_i，将 i∈[pb,i]i\in[pb,i] 的 max⁡b\max b 变成 bib_i，对于所有 cic_i 将当前 max⁡(a)×max⁡(b)\max (a)\times \max (b) 加入。
即，令 xi,yix_i,y_i 为以 ii 开头的区间、以当前扫描位置为尾的 max⁡a,max⁡b\max a,\max b。区间覆盖 xi,yix_i,y_i，维护 ∑xiyi\sum x_i y_i 的历史和。
矩乘法，维护信息 (len,x,y,w,h)(len,x,y,w,h)，可以推导标记。

11.17 T4. 鹿鸣林间：左右边界矩形 chkmax，矩形求和。

规定行为 xx 轴，列为 yy 轴。称左边界矩形 chkmax 为 A 类贡献，右边界矩形 chkmax 为 B 类贡献。
考虑利用左右边界矩形 chkmax 的性质，xx 轴从上往下扫作为时间维。只看 A，发现序列是不增的折线，同样 B 的贡献形如一段不减的折线。那么每个时间的最终贡献就是两条折线上面的部分。
显然存在一条分界线使左右侧分别由 A,B 贡献。考虑求出每个时刻的分界线。即二分 midmid，将 A,B 贡献放在其非边界端点上，比较 midmid 右侧所有 A 的 maxmax 和左侧所有 B 的 maxmax。
考察整个过程即维护：单点加入，单点删除，求区间存在点的 maxmax。可以线段树每个点开一个可删堆，可知能够维每个区间的 maxmax。然后二分就两棵线段树上一起线段树二分即可。O(nlog⁡n)O(n\log n)。
求出了分界线后相当于，把整个矩形锯成两部分，左边只考虑 A 类贡献，右边只考虑 B 类贡献，矩形求和。不妨只考虑 A 类贡献，区间 chkmax 是难以撤销的，但是 A 类贡献全部都贴着左边界。于是按 yy 从右往左扫就不用撤销 chkmax 了，那么就是一个区间 chkmax，区间求历史和。
由于分界线的存在，序列上的每个位置都有一段前缀的时间，强制不贡献历史和。考虑一个解锁操作，当一个点可以贡献时，单点操作解锁这个点。可以维护一个区间的 minmin 中有多少个未解锁的点，可以维护历史和。
由于这里只有单点解锁和区间 chkmax 没有区间加，由 segment beats 势能分析得时间复杂度是 O(nlog⁡n)O(n\log n) 的。

11.24 T4. 比赛：观察刻画 + 历史 max 的历史和。

直接刻画是区间 chkmax 历史 max 的历史和，里面的 chkmax 拆不掉，不太可做。考虑一些比较有性质的刻画方式。
令 sis_i 为 aia_i 的前缀和。对于一个 rr，如果 rr 是最大子段和的右端点，左端点肯定取最小的 sl−1s_{l-1}。但是 ll 要在区间内，那么对于左端点不同的一些区间，会依次取 sl−1s_{l-1} 的后缀最小值。
维护 flf_l 表示区间左端点为 ll 区间内的最大子段和。对于固定的 rr，若 sis_i 是 s[1,r]s_{[1,r]} 的一个后缀最小值，sjs_j 是 sis_i 前的第一个后缀最小值，那么 sis_i 将贡献 l∈[j+2,i+1]l\in[j+2,i+1] 区间内的 flf_l，其贡献为 sr−sis_r-s_i。
考虑操作过程，扫描线，对于当前 rr，先维护出 s[1,r]s_{[1,r]} 的后缀最小值序列，不难发现序列的更改对于 ff 的贡献都是区间加。那么现在就要维护：ff 区间加，ff 区间历史 max 的历史和。
这个是可以维护的，由于 ff 的历史 max 递增，当历史 max 增加时，相当于给后面时间的历史和都加上增量。实际上如果能在每个历史 max 增加时及时修改历史和，那么就可以经典拆成 upd:s1→s1+v×t,s2→s2+vupd:s_1\to s_1+v\times t,s_2\to s_2+v qry:s2(qt+1)−s1qry:s_2(q_t+1)-s_1 的形式来维护历史和。
考虑维护历史 max - 当前值，若差 <0<0 就说明历史 max 增加了。这样可以用一个 chkmax(0)chkmax(0) 操作来找到历史和需要更新的点。
考虑一种另类的 chkmax 方法，维护区间 max,minmax,min。若 min≥0min\ge 0 就不用做了， 否则若 min=maxmin=max 则进行修改，否则继续递归。这样的好处是我们所有的操作将对于一段值相同的操作，这样做是 O(n2)O(n^2) 的。
卡掉它很容易，构造一个锯齿状的序列，每次 chkmax(0)chkmax(0) 再区间 −1-1，这样每次都要递归到最深层。但是由于数据随机或者难以构造锯齿状序列，它过掉了。
正确的方法还是用吉司机线段树，找到 min<0<secminmin<0<secmin 的区间，那么历史和只需要加上 −min×cntmin-min\times cnt_{min}。

T3. 第二个宝石装置：转化矩形扫描线 + 分块 / BIT 维护历史和。

对于一个数 xx，考虑其为区间第 cc 大的贡献。将可能的区间 [l,r][l,r] 找出来，发现可以总共用 O(nc)O(nc) 个对于 l,rl,r 的限制刻画。具体地，找出 xx 前面、后面 cc 个比 xx 大的数，那么限制形如若干个 l∈(pre1,pre2],r∈[suf1,suf2)l\in(pre_1,pre_2],r\in[suf_1,suf_2)。
将 l,rl,r 放在矩形上，xx 的贡献可以看作矩形加，询问即矩形求和。是经典的历史和问题。
  • O(nclog⁡n+Qlog⁡n)O(nc\log n+Q\log n) 做法：本题中会被卡常，可以使用树状数组维护历史和。
    较为巧妙的方法是：考虑时间轴上，一个在时间 tt 的贡献会贡献一个后缀 [t,∞)[t,\infty)，差分一下，变成一个贡献了 [0,t)[0,t)，一个始终有贡献，在 tt 时刻查询时，其贡献即 t×vt\times v。再搭配上树状数组的区间加操作，即可做到超小常数维护区间加、区间历史和。
C
inline void upd(int x,unsigned y,int t)
{
	for(rg i=x;i<=n;i+=lbt(i))
	{
		f1[i]+=y;
		f2[i]+=y*x;
		f3[i]+=y*t;
		f4[i]+=y*x*t;
	}
}
inline unsigned qry(int x,int t)
{
	unsigned ans=0;
	for(rg i=x;i;i-=lbt(i))
	{
		ans+=f1[i]*(x+1)*(t+1)
			-f2[i]*(t+1)
			-f3[i]*(x+1)
			+f4[i];
	}
	return ans;
}
  • O(nc+Qn)O(nc+Q\sqrt n) 做法：由于 ncnc 较大，可以使用分块来进行平衡。可以使用分块来维护历史和。操作跟上面一样，就是 O(1)O(1) 加，O(n)O(\sqrt n) 区间和查询。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...