前言

这次的题思维上倒不是很难，就是代码量比较大。

一、开关

洛谷的这种板子题写起来比cf顺多了（）

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;const int MAXN=1e5+5;//开着的灯数
vector<int>cnts(MAXN<<2);
//懒信息 -> 是否反转
vector<bool>info(MAXN<<2);//懒更新
void lazy(int i,int n)
{cnts[i]=n-cnts[i];info[i]=!info[i];
}//下发
void down(int i,int ln,int rn)
{if(info[i]){lazy(i<<1,ln);lazy(i<<1|1,rn);info[i]=false;}
}//汇总
void up(int i)
{cnts[i]=cnts[i<<1]+cnts[i<<1|1];
}void build(int l,int r,int i)
{if(l==r){cnts[i]=0;}else{int m=(l+r)>>1;build(l,m,i<<1);build(m+1,r,i<<1|1);up(i);}info[i]=false;
}//范围反转
void reverse(int jobl,int jobr,int l,int r,int i)
{if(jobl<=l&&r<=jobr){lazy(i,r-l+1);}else{int m=(l+r)>>1;down(i,m-l+1,r-m);if(jobl<=m){reverse(jobl,jobr,l,m,i<<1);}if(m+1<=jobr){reverse(jobl,jobr,m+1,r,i<<1|1);}up(i);}
}//范围查询
int query(int jobl,int jobr,int l,int r,int i)
{if(jobl<=l&&r<=jobr){return cnts[i];}int m=(l+r)>>1;down(i,m-l+1,r-m);int ans=0;if(jobl<=m){ans+=query(jobl,jobr,l,m,i<<1);}if(m+1<=jobr){ans+=query(jobl,jobr,m+1,r,i<<1|1);}return ans;
}void solve()
{int n,m;cin>>n>>m;build(1,n,1);int l,r;int type;while(m--){cin>>type>>l>>r;if(type==0){reverse(l,r,1,n,1);}else{cout<<query(l,r,1,n,1)<<endl;}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

这个题的思路其实就很好想了，如果用1代表开，0代表关，那么范围内开着的灯的数量其实就可以表示为范围内的累加和。而对于改变灯的状态的这个操作，那么每次只需要将范围内的累加和更新为范围上的总数减去之前的累加和即可。所以代码只需要对懒更新的函数lazy稍微修改一下即可。

二、贪婪大陆

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;const int MAXN=1e5+5;//维护范围内放地雷的开头个数和结尾个数
//如果要求查询[l,r]上的地雷种数
//就是[1,r]范围上的开头个数减去[1,l-1]上的结尾个数//放地雷的开头位置的个数
int bg[MAXN<<2];
//放地雷的结尾位置的个数
int ed[MAXN<<2];//汇总
void up(int i)
{bg[i]=bg[i<<1]+bg[i<<1|1];ed[i]=ed[i<<1]+ed[i<<1|1];
}void build(int l,int r,int i)
{if(l<r){int m=(l+r)>>1;build(l,m,i<<1);build(m+1,r,i<<1|1);up(i);}bg[i]=0;ed[i]=0;
}//范围放置
//jobt==0:在添加开头
//jobt==1:在添加结尾
void put(int jobt,int jobi,int l,int r,int i)
{if(l==r){if(jobt==0){bg[i]++;}else{ed[i]++;}}else{int m=(l+r)>>1;if(jobi<=m){put(jobt,jobi,l,m,i<<1);}else{put(jobt,jobi,m+1,r,i<<1|1);}up(i);}}//范围查询
int query(int jobt,int jobl,int jobr,int l,int r,int i)
{if(jobl<=l&&r<=jobr){return jobt==0?bg[i]:ed[i];}int m=(l+r)>>1;int ans=0;if(jobl<=m){ans+=query(jobt,jobl,jobr,l,m,i<<1);}if(m+1<=jobr){ans+=query(jobt,jobl,jobr,m+1,r,i<<1|1);}return ans;
}void solve()
{int n,m;cin>>n>>m;build(1,n,1);int q,l,r;while(m--){cin>>q>>l>>r;if(q==1){put(0,l,1,n,1);put(1,r,1,n,1);}else{int b=query(0,1,r,1,n,1);//等于1的话就没左侧了int e=l==1?0:query(1,1,l-1,1,n,1);cout<<b-e<<endl;}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

这个题就需要一点转化了。由于要求查询的是范围内放置的地雷种数，而线段树是不能直接用来维护这个信息的。所以可以考虑使用前缀和的思想，用线段树维护范围内每次放置地雷的开头个数和结尾个数，那么这个范围[l,r]内的地雷种数就是[1,r]上地雷的开头个数减去[1,l-1]上地雷的结尾个数。那么这两个信息汇总时就是和累加和一样处理即可，每次放地雷时就是分别去开头位置和结尾位置进行单点修改即可，所以put函数还要带着jobt参数表示这次修改的是开头还是结尾。同理，query函数也要带着jobt表示查询的类型。

三、无聊的数列

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;const int MAXN=1e5+5;//对于在[l,r]上加等差数列
//差分数组中可以在[l]加首项，之后每个位置都加公差，最后[r+1]减末项//原数组
vector<int>a(MAXN);
//差分数组
vector<int>diff(MAXN);
//差分数组累加和
vector<ll>sum(MAXN<<2);
//懒信息
vector<ll>info(MAXN<<2);//懒更新
void lazy(int i,int v,int n)
{sum[i]+=v*n;info[i]+=v;
}//下发
void down(int i,int ln,int rn)
{if(info[i]!=0){lazy(i<<1,info[i],ln);lazy(i<<1|1,info[i],rn);info[i]=0;}
}//汇总
void up(int i)
{sum[i]=sum[i<<1]+sum[i<<1|1];
}void build(int l,int r,int i)
{if(l==r){sum[i]=diff[l];}else{int m=(l+r)>>1;build(l,m,i<<1);build(m+1,r,i<<1|1);up(i);}info[i]=0;
}//范围修改
void add(int jobl,int jobr,ll jobv,int l,int r,int i)
{if(jobl<=l&&r<=jobr){lazy(i,jobv,r-l+1);}else{int m=(l+r)>>1;down(i,m-l+1,r-m);if(jobl<=m){add(jobl,jobr,jobv,l,m,i<<1);}if(m+1<=jobr){add(jobl,jobr,jobv,m+1,r,i<<1|1);}up(i);}
}//范围查询
ll query(int jobl,int jobr,int l,int r,int i)
{if(jobl<=l&&r<=jobr){return sum[i];}int m=(l+r)>>1;down(i,m-l+1,r-m);ll ans=0;if(jobl<=m){ans+=query(jobl,jobr,l,m,i<<1);}if(m+1<=jobr){ans+=query(jobl,jobr,m+1,r,i<<1|1);}return ans;
}void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){diff[i]=a[i]-a[i-1];}build(1,n,1);int op;while(m--){cin>>op;if(op==1){ll l,r,k,d;cin>>l>>r>>k>>d;//开头加首项add(l,l,k,1,n,1);//中间加公差if(l+1<=r){add(l+1,r,d,1,n,1);   }//后一项减末项if(r+1<=n){add(r+1,r+1,-(k+d*(r-l)),1,n,1);}}else{int q;cin>>q;cout<<query(1,q,1,n,1)<<endl;}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

这个题因为只涉及单点查询，又因为每次范围增加是增加一个等差数列，所以可以考虑用线段树去维护差分数组的累加和，那么单点查询时只需要查[1,q]上的累加和即可。而对于在差分数组中增加等差数列的操作，通过观察等差数列的差分数组可以想到，方法就是在l位置加上首项，之后的每个位置都加公差，最后在r+1的位置减去末项即可。这里记得等差数列末项的公式是首项加项数减一乘公差即可。

四、方差

死去的高中数学还在追我（）

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;const int MAXN=1e5+5;//原数组
vector<double>a(MAXN);
//累加和
vector<double>sum(MAXN<<2);
//平方和
vector<double>square(MAXN<<2);
//懒信息
vector<double>info(MAXN<<2);//懒更新
void lazy(int i,double v,int n)
{square[i]+=n*v*v+2*v*sum[i];sum[i]+=v*n;info[i]+=v;
}//下发
void down(int i,int ln,int rn)
{if(info[i]!=0){lazy(i<<1,info[i],ln);lazy(i<<1|1,info[i],rn);info[i]=0;}
}//汇总
void up(int i)
{sum[i]=sum[i<<1]+sum[i<<1|1];square[i]=square[i<<1]+square[i<<1|1];
}void build(int l,int r,int i)
{if(l==r){sum[i]=a[l];square[i]=a[l]*a[l];}else{int m=(l+r)>>1;build(l,m,i<<1);build(m+1,r,i<<1|1);up(i);}info[i]=0;
}//范围增加
void add(int jobl,int jobr,double jobv,int l,int r,int i)
{if(jobl<=l&&r<=jobr){lazy(i,jobv,r-l+1);}else{int m=(l+r)>>1;down(i,m-l+1,r-m);if(jobl<=m){add(jobl,jobr,jobv,l,m,i<<1);}if(m+1<=jobr){add(jobl,jobr,jobv,m+1,r,i<<1|1);}up(i);}
}//范围查询
double query(int jobl,int jobr,int l,int r,int i,vector<double>&sum)
{if(jobl<=l&&r<=jobr){return sum[i];}int m=(l+r)>>1;down(i,m-l+1,r-m);double ans=0;if(jobl<=m){ans+=query(jobl,jobr,l,m,i<<1,sum);}if(m+1<=jobr){ans+=query(jobl,jobr,m+1,r,i<<1|1,sum);}return ans;
}void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}build(1,n,1);int op;int x,y;double k;while(m--){cin>>op>>x>>y;;if(op==1){cin>>k;add(x,y,k,1,n,1);}else if(op==2){cout<<fixed<<setprecision(4)<<query(x,y,1,n,1,sum)/(y-x+1)<<endl;}else{double sq=query(x,y,1,n,1,square)/(y-x+1);double avg=query(x,y,1,n,1,sum)/(y-x+1);cout<<fixed<<setprecision(4)<<sq-avg*avg<<endl;}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

首先，平均数这个信息好办，就是用线段树维护累加和信息，每次查询范围累加和除以范围个数即可。但方差这个信息肯定是没办法直接用线段树维护的，那么就可以考虑对方差公式进行一下转化。具体的转化就是：

$\frac{\sum (x-\bar{x})^{2}}{n}=\frac{\sum x^{2}-2\bar{x}\sum x+n\bar{x}}{n}=\frac{\sum x^{2}}{n}-2\bar{x}^{2}+\bar{x}^{2}=\frac{\sum x^{2}}{n}-\bar{x}^{2}$