目录
线段树例题
线段树注意事项：
在访问子树之前，一定、一定、一定要pushdown()!!!!!!!!!!。来自一天白干的教训
调试的时候，先确定其他地方都对了！！！线段树查起来时间很长！别花了一下午调试线段树结果线段树是对的
P3372 【模板】线段树 1
题目描述
区间修改、区间查询
解题思路
这题很显然是线段树模板。
线段树是一种能在 \(O(\log n)\) 的时间内进行区间修改与区间查询的数据结构。
他的本质是二叉树，将数列划分为一个一个的区间。
若一个节点表示区间 \((l,r)\) ，则他的左孩子表示区间 \((1,(l+r)/2)\) ，右孩子表示区间 \(((l+r)/2+1,r)\) 。
若是把区间想象成线段，那么一个节点的两个子节点就是对这条线段一分为二变成了两条，这也是线段树这个名字的由来。
但是如果我们对于每一次修改都递归到叶子节点的话，复杂度就变成了 \(O(n \log n)\) ，这甚至还不如暴力的 \(O(n)\) 呢。
由此，我们引出了线段树的一个重要操作： lazy tag 懒标记。
如果我们现在递归到了一个节点，而这个节点完全被操作节点覆盖，我们就可以停在这里，不再往下递归，并打上一个 tag ，表示这个节点代表的区间的所有数都进行了 tag 操作。
此时，这个节点往下的子树里的信息就都是过时的了，因为他们没有进行 tag 的操作。
所以，在之后的操作过程中，如果我们要越过这个节点去访问子树，就一定要将懒标记下推一层！否则访问到的就是过时信息，会 WA 的很惨。
思想就这么多，但代码很繁琐。光模板就80行左右
Code
// Problem:
// P3372 【模板】线段树 1
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3372
// Memory Limit: 125 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{//节点结构体，你也可以开这么多数组，按习惯来
int lef,rit;
ll sum,tag;
}tree[400005];
int n,m;
ll a[100005];
void pushup(int now){
//操作0，合并子树，这个题只需要维护一个区间和，可以不写，但如果合并操作过于复杂还是写一下吧
tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;
}
void pushdown(int k){//操作1，标记下推
tree[k*2].tag+=tree[k].tag;
tree[k*2+1].tag+=tree[k].tag;
tree[k*2].sum+=tree[k].tag*(tree[k*2].rit-tree[k*2].lef+1);
tree[k*2+1].sum+=tree[k].tag*(tree[k*2+1].rit-tree[k*2+1].lef+1);
tree[k].tag=0;
}
void build(int now,int l,int r){//操作2，建树/初始化
tree[now].lef=l,tree[now].rit=r;
//可以记录区间左右边界，也可以不记录，因为递归到这个区间时可以算出左右边界
if(l==r){//如果到了叶子
tree[now].sum=a[l];//区间只有一个点，和就是这个点的值
return;
}
int mid=(l+r)>>1;// >>1就相当于整除2
build(now*2,l,mid);//构建左子树
build(now*2+1,mid+1,r);//构建右子树
pushup(now);//合并
}
void update(int now,int l,int r,int k){//操作3，区间修改
if(l==tree[now].lef&&r==tree[now].rit){//如果完全被包含
tree[now].tag+=k;//犯懒~
tree[now].sum+=(r-l+1)*k;
//别忘了修改节点保存的信息，不然这个节点保存的信息也没有时效性了
return;
}
pushdown(now);//如果要访问他的子树，一定一定一定要下推标记
int mid=(tree[now].lef+tree[now].rit)>>1;
if(mid>=l)update(l,min(mid,r),k,now*2);//画几个线段数，理解理解为什么这么写
if(mid+1<=r)update(max(l,mid+1),r,k,now*2+1);
//这里可以取min/max，也可以直接把操作区间原封不动的往下传，还是习惯问题。如果原封不动的传刚刚判断完全包含的判断记得改，这几个判断条件也得改
pushup(now);//这里也要合并
}
ll query(int now,int l,int r){
node sol=tree[now];//我也不知道当时为啥要写这个，就当他不存在吧
if(sol.lef==l&&sol.rit==r)
return sol.sum;
pushdown(now);//如果要访问他的子树，一定一定一定要下推标记
ll ret=0;
int mid=(tree[now].lef+tree[now].rit)>>1;
if(mid>=l)ret+=query(l,min(mid,r),now*2);
if(mid+1<=r)ret+=query(max(l,mid+1),r,now*2+1);
return ret;//基本同上
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);//千万别忘了建树
for(int i=1;i<=m;i++){//模板
int op;cin>>op;
if(op==1){
int x,y,k;cin>>x>>y>>k;
update(1,x,y,k);
}else{
int x,y;cin>>x>>y;
cout<<query(1,x,y)<<endl;
}
}
return 0;
}
P3373 【模板】线段树 2
题目描述
还是区间修改、区间查询，但区别是这题的修改不光是加法，还混有乘法！
解题思路
没思路？
这个时候，就该伟大的数学出马了！
设原数为 \(num\) 假设现在有一个操作序列：\(+a,\times b,+c,\times d\) 让我们来展开他：
\[\begin{align}
num&=(((num + a) \times b) + c) \times d\\
&=(num \times b + a \times b + c) \times d\\
&=num \times b \times d +a \times b \times d + c \times d
\end{align}
\]
然后我们就发现：原数该乘的数还是得乘，加上的数就是每个加数乘上在他之后新的要乘的数。
那么我们就可以打两个标记，一个表示改成的数，一个表示该加的数，每加一个数就把数加到“加标记”里，每乘一个数就把乘的数乘到“乘标记”和“加标记”里。
Code
// Problem:
// P3373 【模板】线段树 2
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3373
// Memory Limit: 125 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
ll lef,rit;
ll sum;
ll tagc,tagj;
node(){//结构体同名的函数表示初始化
tagc=1;
}
}mp[400005];
ll n,m,q,a[100005];
ll build(ll i,ll lef,ll rit){
//建树，题目里模数的平方超int了，所以我全用ll了
mp[i].lef=lef,mp[i].rit=rit;
if(lef==rit)
return mp[i].sum=a[lef]%m;
ll mid=(lef+rit)>>1;
return mp[i].sum=(build(i*2,lef,mid)+build(i*2+1,mid+1,rit))%m;
//我也不知道我当时为啥要这么写（可能是懒）
}
void pushdown(ll i){//繁琐的标记下推
mp[i*2].sum=(mp[i*2].sum*mp[i].tagc+((mp[i*2].rit-mp[i*2].lef+1)*mp[i].tagj))%m;
mp[i*2+1].sum=(mp[i*2+1].sum*mp[i].tagc+((mp[i*2+1].rit-mp[i*2+1].lef+1)*mp[i].tagj))%m;
//对两个子节点的区间和进行修改（单个数字的乘法反应在区间上也是乘，单个数字的加法反映在区间上别忘了乘个数）
mp[i*2].tagj=(mp[i].tagj+mp[i*2].tagj*mp[i].tagc)%m;
mp[i*2].tagc=(mp[i].tagc*mp[i*2].tagc)%m;
mp[i*2+1].tagj=(mp[i].tagj+mp[i*2+1].tagj*mp[i].tagc)%m;
mp[i*2+1].tagc=(mp[i].tagc*mp[i*2+1].tagc)%m;
//对两个子节点的加标记和乘标记修改
mp[i].tagc=1;//乘法如果初值为0那乘以任何数都是0了
mp[i].tagj=0;
}
void updateadd(ll l,ll r,ll k,ll i/*脑残操作，别管*/){//加和乘的操作可以合并，但没必要
if(l==mp[i].lef&&r==mp[i].rit){//正常懒标记，只不过别忘了模
mp[i].tagj+=k;
mp[i].sum+=(r-l+1)*k;
mp[i].tagj%=m;
mp[i].sum%=m;
return;
}
pushdown(i);//下推标记
ll mid=(mp[i].lef+mp[i].rit)>>1;
if(mid>=l)updateadd(l,min(mid,r),k,i*2);
if(mid+1<=r)updateadd(max(l,mid+1),r,k,i*2+1);
mp[i].sum=mp[i*2].sum+mp[i*2+1].sum;//pushup，操作太简单懒得写了
}
void updateche(ll l,ll r,ll k,ll i=1){//几乎和加一样
if(l==mp[i].lef&&r==mp[i].rit){
mp[i].tagj=(mp[i].tagj*k)%m;
mp[i].tagc=(mp[i].tagc*k)%m;
mp[i].sum=(mp[i].sum*k)%m;
return;
}
pushdown(i);
ll mid=(mp[i].lef+mp[i].rit)>>1;
if(mid>=l)updateche(l,min(mid,r),k,i*2);
if(mid+1<=r)updateche(max(l,mid+1),r,k,i*2+1);
mp[i].sum=mp[i*2].sum+mp[i*2+1].sum;
}
ll query(ll i,ll lef,ll rit){//模板查找
if(mp[i].lef==lef&&mp[i].rit==rit)
return mp[i].sum%=m;
pushdown(i);
ll mid=(mp[i].lef+mp[i].rit)>>1;
ll ret=0;
if(mid>=lef)ret+=query(i*2,lef,min(mid,rit));
if(mid+1<=rit)ret+=query(i*2+1,max(mid+1,lef),rit);
return ret%m;
}
int main(){
cin>>n>>q>>m;
for(ll i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
for(ll i=1;i<=q;i++){
ll op;cin>>op;
if(op==1){
ll x,y,k;cin>>x>>y>>k;
updateche(x,y,k);
}else if(op==2){
ll x,y,k;cin>>x>>y>>k;
updateadd(x,y,k);
}else{
ll x,y;cin>>x>>y;
cout<<query(1,x,y)<<endl;
}
}
return 0;
}
P6492 [COCI2010-2011#6] STEP
题目描述
给定一个长度为 \(n\) 的字符序列 \(a\)，初始时序列中全部都是字符 L。
有 \(q\) 次修改，每次给定一个 \(x\)，若 \(a_x\) 为 L，则将 \(a_x\) 修改成 R，否则将 \(a_x\) 修改成 L。
对于一个只含字符 L，R 的字符串 \(s\)，若其中不存在连续的 L 和 R，则称 \(s\) 满足要求。
每次修改后，请输出当前序列 \(a\) 中最长的满足要求的连续子串的长度。
解题思路
（这题属实是给我脆弱的心灵带来了一些小小的线段树震撼）
思路还是很好想的。
之前做的题都是维护一些区间和啊，区间最大值啊之类的，而这道题是要我们维护一个区间中符合要求的子串长度。
怎么写呢？
按照之前的思路，一个区间中最长的，可以在他的左右孩子中取一个 \(\max\) 。
但这道题还有一种情况！左右孩子所代表的区间中间可能会拼起来反而更长！
蓝色表示取max的最大值，红色表示中间拼起来的最大值。
那么我们为了维护这种邪恶的情况需要保存什么数据呢？
-
首先，因为要先确认他们能不能拼起来，所以我们要记录一下他们两端点是什么，不一样才存在拼起来的情况。
-
其次，要计算他们拼起来的长度，就要知道他们各自前面和后面符合的长度有多长（也就是前缀和后缀）。
前缀和后缀又怎么维护呢？
- 前缀我们可以直接继承左子节点，后缀我们可以继承右子节点。
完了？
- 注意！如果一个节点他的左（右）子节点是一个完全的 01 串，并且两个子节点中间还可以合并，那么在此时，我们的前（后）缀就会变成左（右）子节点代表的区间长度加上右（左）子节点的前（后）缀
完了？终于完了。
Code
// Problem:
// P6492 [COCI2010-2011#6] STEP
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6492
// Memory Limit: 128 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//我也不知道当时为啥要这样写
int lef[800005];//左边界
int rit[800005];//右边界
int f[800005];//左端字符
int b[800005];//右端字符
int pre[800005];//前缀
int suf[800005];//后缀
int len[800005];//最长的、符合要求的长度
int n,m;
bool a[200005];
//这题只会是单点修改，不会有区间修改，所以
void pushup(int rt){//繁琐的合并
int lc=rt*2,rc=rt*2+1;
pre[rt]=pre[lc];//先把没有特殊情况的保证好
suf[rt]=suf[rc];
f[rt]=f[lc],b[rt]=b[rc];
len[rt]=max(len[lc],len[rc]);
if(b[lc]!=f[rc]){//特殊情况成立
len[rt]=max(len[rt],suf[lc]+pre[rc]);//喂，别忘了取max，别直接赋值了。
if(len[lc]==rit[lc]-lef[lc]+1)//特殊情况下前缀的维护
pre[rt]=rit[lc]-lef[lc]+1+pre[rc];
if(len[rc]==rit[rc]-lef[rc]+1)//特殊情况下后缀的维护
suf[rt]=rit[rc]-lef[rc]+1+suf[lc];
}
}
void build(int rt,int l,int r){//建树
f[rt]=a[l],b[rt]=a[r],lef[rt]=l,rit[rt]=r;//初始化
if(l==r){
f[rt]=b[rt]=a[l];
len[rt]=suf[rt]=pre[rt]=1;//只有一个值显然这些都是1
return;
}
int mid=(l+r)>>1;
build(rt*2,l,mid);
build(rt*2+1,mid+1,r);
pushup(rt);//合并
}
void update(int rt,int x){//单点更新
if(lef[rt]!=rit[rt]){//如果长度不为1
int mid=(lef[rt]+rit[rt])>>1;
if(x<=mid)//由于是单点所以也不存在横跨两子节点的情况
update(rt*2,x);
else
update(rt*2+1,x);
pushup(rt);//合并不能丢
}else
f[rt]=b[rt]=a[lef[rt]];//递归到底了，该回溯了
}
int main(){
cin>>n>>m;
build(1,1,n);
for(int i=1;i<=m;i++){//跟前面相比看起来极为简陋的main
int x;
cin>>x;
a[x]=!a[x];
update(1,x);
cout<<len[1]<<endl;
}
return 0;
}
P2184 贪婪大陆
题目描述
小 FF 最后一道防线是一条长度为 \(n\) 的战壕，小 FF 拥有无数多种地雷，而 SCV 每次可以在 \([L, R]\) 区间埋放同一种不同于之前已经埋放的地雷。由于情况已经十万火急，小 FF 在某些时候可能会询问你在 \([L',R']\) 区间内有多少种不同的地雷，他希望你能尽快的给予答复。
解题思路
这其实就是一道不会覆盖的染色问题。
每次埋雷都可以视为加入一段区间，其实很容易理解就是询问一段区间内有多少段不同的区间。
仔细思考我们就可以得到以下结论：
- 如果一个区间的开头在 \(i\) 左边，那么他一定在 \(1\sim i\) 这一段。
- 如果一个区间的末尾在 \(j\) 右边，那么他一定不在 \(j \sim n\) 这一段。
基于以上两个结论，我们就可以得出一个结论。
一段区间内不同的区间数就是用询问区间结束点之前的所有起点的数量减去在询问区间起点之前就已经结束的区间的数量。
然后我们就会发现：这样做只需要进行单点修改和区间查询。
树状数组其实就能解决啊！用什么线段树。
Code
// Problem:
// P2184 贪婪大陆
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2184
// Memory Limit: 125 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int tl[100005],tr[100005];//两个树状数组，一个记录区间左端点，一个记录区间右端点。
int lowbit(int x){return x & (-x);}
void update(int *c,int x,int v){//把数组地址传进来,这样就不用写两遍了。
while(x<=n){
c[x]+=v;
x+=lowbit(x);
}
}
int query(int *c,int x){
int ret=0;
while(x>0){
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int op,x,y;cin>>op>>x>>y;
if(op==1){
update(tl,x,1);
update(tr,y,1);//单点修改
}else{
cout<<query(tl,y)-query(tr,x-1)<<endl;//输出，因为两端点也包含在内所以用x-1
}
}
return 0;
}
P4588 [TJOI2018] 数学计算
题目描述
小豆现在有一个数 \(x\)，初始值为 \(1\)。小豆有 \(Q\) 次操作，操作有两种类型：
1 m：将 \(x\) 变为 \(x \times m\)，并输出 \(x \bmod M\)
2 pos：将 \(x\) 变为 \(x\) 除以第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 \(x \bmod M\)。
解题思路
刚看这道题的时候我还觉得这不就是暴力模拟吗，然后写到一半才发现问题。如果直接做的话取模之后就没法在做除法，除非直接写高精度（貌似直接写高精空间要炸的样子）。
知道这题要用线段树之后这题就很简单了。
我们可以认为这里有一个数列，他们最开始都是 \(1\) ,而每次 1 操作都是将其中一个 \(1\) 修改成 \(m\)。
2 操作就是把一个数再修改成 \(1\)。
虽然都是单点修改和区间查询，但是树状数组如果要将一个数变回 \(1\) 的话就涉及到了分数，有一个精度的问题，所以还是老老实实用线段树吧。
Code
// Problem:
// P4588 [TJOI2018] 数学计算
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4588
// Memory Limit: 250 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,m;
ll sum[400005];
int lef[400005];
int rit[400005];
void build(int i,int l,int r){
sum[i]=1;
lef[i]=l,rit[i]=r;
if(l!=r){
int mid=(l+r)>>1;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
}
}
void update(int i,int x,int v){
if(lef[i]!=rit[i]){
int mid=(lef[i]+rit[i])>>1;
if(mid>=x)
update(i*2,x,v);
if(mid+1<=x)
update(i*2+1,x,v);
sum[i]=(sum[i*2]*sum[i*2+1])%m;
}else{
sum[i]=v;
}
}
int main(){
cin>>t;
for(int ss=1;ss<=t;ss++){
int q;cin>>q>>m;
build(1,1,q);
for(int i=1;i<=q;i++){
int op,x;cin>>op>>x;
if(op==1)
update(1,i,x);
else
update(1,x,1);
cout<<sum[1]<<endl;
}
}
return 0;
}
P2161 [SHOI2009] 会场预约
题目描述
你需要维护一个在数轴上的线段的集合 \(S\)，支持两种操作：
A l r 表示将 \(S\) 中所有与线段 \([l,r]\) 相交的线段删去，并将 \([l,r]\) 加入 \(S\) 中。
B 查询 \(S\) 中的元素数量。
对于 A 操作，每次还需输出删掉的元素个数。
解题思路
这也是染色题的一种。
为了方便理解，以下把线段看成颜色。
A 操作其实就是查询这一段内一共有多少种颜色，把他们全部删除然后新加入一个。
B 操作就是查询还剩几种颜色。
对于 A 操作，我们可以加一个数组 del 记录某个颜色是否已经被删除。
B 操作只需要在加入和删除的时候用变量记录就好了。（说的轻松，也不知道是谁在这个题卡了一天）
Code
// Problem:
// P2161 [SHOI2009] 会场预约
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2161
// Memory Limit: 125 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
using namespace std;
// typedef long long ll;
const int maxn=200005;
struct node{
int lef,rit;//左右边界
int col;//颜色
bool tag;//0表示不同，1表示相同
}tree[4*maxn];//空间记得开四倍
int n;
int ans,cnt;
int ll[maxn],rr[maxn];
int mind=INT_MAX,maxd=INT_MIN;
bool del[maxn];
bool ops[maxn];
void build(int i,int l,int r){
tree[i].tag=1;//同为无色
tree[i].col=0;//表示无色或不同
tree[i].lef=l,tree[i].rit=r;
if(l==r)
return;
int mid=(l+r)>>1;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
}
void pushdown(int i){
tree[i].tag=0;//标记不同色
if(tree[i].col!=0){
int lc=i*2,rc=i*2+1;
tree[lc].col=tree[rc].col=tree[i].col;
tree[i].col=0;
}
}
void find(int i,int k){
if(tree[i].tag){
if(!del[tree[i].col]&&tree[i].col!=0)
ans--,cnt++;
del[tree[i].col]=1;
tree[i].col=k;
return;
}
find(i*2,k);
find(i*2+1,k);
tree[i].tag=1,tree[i].col=k;
}
void update(int i,int l,int r,int k){
if(tree[i].lef>=l&&tree[i].rit<=r){
find(i,k);//由于还要统计颜色，所以这里展开在另外的函数(还不能停在这，只有同色区间才能停)
return;
}
pushdown(i);//下推标记
int mid=(tree[i].lef+tree[i].rit)>>1;
if(l<=mid)
update(i*2,l,r,k);//我这里写的就是不裁剪操作边界
if(r>mid)
update(i*2+1,l,r,k);
//不需要合并操作，下推的时候已经顺手标记了颜色不同
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
char op;cin>>op;
if(op=='A'){
cin>>ll[i];
cin>>rr[i];//这里也可以不离线，在线，可是那就得防爆把树开到最大，有点浪费
mind=min(mind,ll[i]);
maxd=max(maxd,rr[i]);//记录左右边界
ops[i]=1;
}
}
//ans记录还剩几个颜色，cnt记录这次删了几个
build(1,mind,maxd);
for(int i=1;i<=n;i++){
if(ops[i]){
ans++;//新加入一个
cnt=0;//清空
update(1,ll[i],rr[i],i);
cout<<cnt<<endl;//输出
}else{
cout<<ans<<endl;
}
}
return 0;
}
P1471 方差
题目描述
第一行包含两个正整数 \(N,M\)，分别表示数列中实数的个数和操作的个数。
第二行包含 \(N\) 个实数，其中第 \(i\) 个实数表示数列的第 \(i\) 项。
接下来 \(M\) 行，每行为一条操作，格式为以下三种之一：
操作 \(1\)：1 x y k ，表示将第 \(x\) 到第 \(y\) 项每项加上 \(k\)，\(k\) 为一实数。
操作 \(2\)：2 x y ，表示求出第 \(x\) 到第 \(y\) 项这一子数列的平均数。
操作 \(3\)：3 x y ，表示求出第 \(x\) 到第 \(y\) 项这一子数列的方差。
（所有结果四舍五入保留 \(4\) 位小数）。
解题思路
这题完全就是数学题，把公式展开一下就出来了
先展开一下方差公式 （\(\bar x\) 表示平均值）：
\[\begin{align}
S^2 &= \frac 1 n \cdot [(x_1 - \bar x)^2+(x_2 - \bar x)^2 + \cdots + (x_n - \bar x)^2]\\
&=\frac 1 n \cdot (x_1^2 + \bar x ^ 2 - 2 \cdot x_1 \cdot \bar x + x_2^2 + \bar x ^ 2 - 2 \cdot x_2 \cdot \bar x + \cdots + x_n^2 + \bar x ^ 2 - 2 \cdot x_n \cdot \bar x)\\
&=\frac 1 n \cdot [(x_1^2+x_2^2+\cdots +x_n^2)+n \cdot \bar x - 2\cdot \bar x \cdot(x_1+x_2+\cdots+x_n)]\\
&=\frac {x_1^2+x_2^2+\cdots +x_n^2} {n} + \bar x - 2\cdot \bar x \cdot \frac {x_1+x_2+\cdots+x_n} {n}\\
&=\frac {x_1^2+x_2^2+\cdots +x_n^2} {n} + \bar x - 2\cdot \bar x^2
\end{align}
\]
这样一来就明了了，对于每个节点，我们保存区间和以及区间平方和即可。
新区间平方和（设为 \(sum\) ）又怎么维护呢？
再展开一下（式子中的 \(x\) 为原序列）：
\[\begin{align}
sum &= （x_1+k)^2+（x_1+k)^2+\cdots+（x_n+k)^2\\
&=x_1^2+k^2+2\cdot x_1 \cdot k+x^2_2+k^2+2\cdot x_2 \cdot k+x_3^2+k^2+2\cdot x_3 \cdot k+\cdots +x_n^2+k^2+2\cdot x_n\cdot k\\
&=(x_1^2+x_2^2+\cdots+x_n^2)+n\cdot k^2+2\cdot k\cdot (x_1+x_2+x_3+\cdots+x_n)\\
\end{align}
\]
结果已经很明显了，就这么维护就好了。
Code
// Problem:
// P1471 方差
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1471
// Memory Limit: 125 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;//记得开double，不然会WA的很惨
struct node{
int lef,rit;
dou sqsum,sum;//维护区间平方和和区间和
dou tag;
}tree[4000005];//记得开四倍
int n,m;
dou a[1000005];
void pushup(int i){//合并操作，维护的都是和，所以直接加就行
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
tree[i].sqsum=tree[i*2].sqsum+tree[i*2+1].sqsum;
}
void pushdown(int i){//恐怖的pushdown
int lc=i*2,rc=i*2+1;
tree[lc].tag+=tree[i].tag;
tree[rc].tag+=tree[i].tag;//先搞定tag标记
tree[lc].sqsum+=(tree[lc].rit-tree[lc].lef+1)*tree[i].tag*tree[i].tag+2*tree[i].tag*tree[lc].sum;//按照推导出来的公式维护平方和，要注意，因为公式里的区间和是旧区间和，所以要先更新平方和
tree[lc].sum+=(tree[lc].rit-tree[lc].lef+1)*tree[i].tag;
tree[rc].sqsum+=(tree[rc].rit-tree[rc].lef+1)*tree[i].tag*tree[i].tag+2*tree[i].tag*tree[rc].sum;
tree[rc].sum+=(tree[rc].rit-tree[rc].lef+1)*tree[i].tag;
tree[i].tag=0;//已经下推了，标记清零
}
void build(int i,int l,int r){//建树
tree[i].lef=l,tree[i].rit=r;
if(l==r){//简单赋值
tree[i].sum=a[l];
tree[i].sqsum=a[l]*a[l];
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
pushup(i);//合并
}
void update(int i,int l,int r,dou k){//区间修改
if(tree[i].lef==l&&tree[i].rit==r){//懒标记
tree[i].tag+=k;
tree[i].sqsum+=(tree[i].rit-tree[i].lef+1)*k*k+2*k*tree[i].sum;
tree[i].sum+=(tree[i].rit-tree[i].lef+1)*k;
return;
}
pushdown(i);//别忘了
int mid=(tree[i].lef+tree[i].rit)>>1;
if(mid>=l)
update(i*2,l,min(mid,r),k);
if(mid+1<=r)
update(i*2+1,max(mid+1,l),r,k);
pushup(i);//别忘了
}
pair<dou,dou> query(int i,int l,int r){//pair做返回值，这样一次就可以返回两个值，就不用写两遍了，也可以手写一个结构体
if(tree[i].lef==l&&tree[i].rit==r)
return make_pair(tree[i].sum,tree[i].sqsum);
pushdown(i);//别忘了
pair <dou,dou> ret(0,0);
int mid=(tree[i].lef+tree[i].rit)>>1;
pair <dou,dou> a(0,0);
if(mid>=l){
a=query(i*2,l,min(mid,r));
ret.first+=a.first,ret.second+=a.second;
}
if(mid+1<=r){
a=query(i*2+1,max(mid+1,l),r);
ret.first+=a.first,ret.second+=a.second;
}
return ret;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);//记得建树
for(int i=1;i<=m;i++){
dou op;int x,y;cin>>op>>x>>y;
if(op==1){
dou k;cin>>k;
update(1,x,y,k);
}else if(op==2){
pair <dou,dou> a=query(1,x,y);
dou ans=a.first*1.0/(y-x+1);
printf("%.4lf\n",ans);//printf本身是会四舍五入的，但我有话说！！！！
}else{
pair <dou,dou> a=query(1,x,y);
dou bar=a.first*1.0/((y-x+1)*1.0);
dou ans=a.second*1.0/((y-x+1)*1.0)-pow(bar,2);
printf("%.4lf\n",ans);
}
}
return 0;
}
最开始我不知道 printf 会四舍五入，然后手写了一个舍入，结果 WA 了，注释掉又好了。
但是！我发现了一个神奇的事情：
先看代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
double a;cin>>a;
printf("%.4lf",a);
return 0;
}
我反复试了很多组数据，都没问题，直到输入了：
0.55995
然后他神奇的输出了：
0.5599
啊？？就很神奇
于是我就手写了一个四舍五入
如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
double a;cin>>a;
a*=10000;
a+=0.5;
a=(int)a;
a/=10000;
printf("%.4lf",a);
return 0;
}
但他还是败倒在了 0.55995 之下
我又加了几个调试输出：
#include <bits/stdc++.h>
using namespace std;
int main(){
double a;cin>>a;
printf("0 %.5lf\n",a);
a*=10000;
printf("1 %.5lf\n",a);
a+=0.5;
printf("2 %.5lf\n",a);
a=(int)a;
printf("3 %.5lf\n",a);
a/=10000;
printf("4 %.5lf\n",a);
return 0;
}
他输出了
0 0.55995
1 5599.50000
2 5600.00000
3 5599.00000
4 0.55990
????好魔幻，我又试了几次，过程不重要，总之结论就是
double a=5600;
a=int(a);
(a==5600)
but
double a=0.55995;
a*=10000;
a+=0.5;
a=int(a);
(a==5599);
就在这个点卡了一天
P1438 无聊的数列
题目描述
维护一个数列 \(a_i\)，支持两种操作：
-
1 l r K D：给出一个长度等于 \(r-l+1\) 的等差数列，首项为 \(K\)，公差为 \(D\)，并将它对应加到 \([l,r]\) 范围中的每一个数上。即：令 \(a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D\)。 -
2 p：询问序列的第 \(p\) 个数的值 \(a_p\)。
解题思路
很明显，加上一个等差数列，就相当于给这个数列的差分中间这一段加上了这个数列的公差，这样我们就把区间加上一个不同的数变成了一个正常的区间加法，线段树维护就好了。不过细节还是很多的，要加几个判断。
Code
// Problem:
// P1438 无聊的数列
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1438
// Memory Limit: 128 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
using namespace std;
struct node{
long long lef,rit,tag;
long long sum;
}tree[50000005];//线段树都是模板
long long n,m;
long long a[1000005],d[1000005];
void pushup(long long i){
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
void pushdown(long long i){
tree[i*2].tag+=tree[i].tag,tree[i*2+1].tag+=tree[i].tag;
tree[i*2].sum+=(tree[i*2].rit-tree[i*2].lef+1)*tree[i].tag;
tree[i*2+1].sum+=(tree[i*2+1].rit-tree[i*2+1].lef+1)*tree[i].tag;
tree[i].tag=0;
}
void build(long long i,long long l,long long r){
tree[i].lef=l,tree[i].rit=r;
if(l==r){
tree[i].sum=d[l];//在差分数组的基础上建树
return;
}
long long mid=(l+r)>>1;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
pushup(i);
}
void update(long long i,long long l,long long r,long long k){
if(tree[i].lef==l&&tree[i].rit==r){
tree[i].tag+=k;
tree[i].sum+=(r-l+1)*k;
return;
}
pushdown(i);//别忘了
long long mid=(tree[i].lef+tree[i].rit)>>1;
if(mid>=l)
update(i*2,l,min(r,mid),k);
if(mid+1<=r)
update(i*2+1,max(l,mid+1),r,k);
pushup(i);//别忘了
}
long long query(long long i,long long l,long long r){
if(tree[i].lef==l&&tree[i].rit==r)
return tree[i].sum;
pushdown(i);//别忘了
long long mid=(tree[i].lef+tree[i].rit)>>1;
long long ret=0;
if(mid>=l)
ret+=query(i*2,l,min(mid,r));
if(mid+1<=r)
ret+=query(i*2+1,max(l,mid+1),r);
return ret;
}
int main(){
cin>>n>>m;
for(long long i=1;i<=n;i++){
cin>>a[i];
d[i]=a[i]-a[i-1];//构建差分数组
}
build(1,1,n);//建树
for(long long i=1;i<=m;i++){
long long op;cin>>op;
if(op==1){
long long l,r,k,d;cin>>l>>r>>k>>d;
update(1,l,l,k);
if(l+1<=r)//判断条件自己想为啥这么写
update(1,l+1,r,d);
if(r+1<=n)
update(1,r+1,r+1,-(k+d*(r-l)));
}else{
long long p;cin>>p;
cout<<query(1,1,p)<<endl;
}
}
return 0;
}