數據結構與算法：線段樹（三）：維護更多信息

前言

這次的題思維上倒不是很難，就是代碼量比較大。

一、開關

洛谷的這種板子題寫起來比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}$