线段树~~~
线段树
- 线段树原理
- 线段树离散化，二分搜索，特别修改
- 离散化例题
- 特别修改
- 开方
- 取模
- 贴海报
- 更多类型信息，势能分析
- 开关
- 地雷
- 范围增加等差数列
- 方差
- 线段树解决区间合并问题
- 最经典例题
- 最长LR交替子串
- 鬼子进村
- hotel
- 区间最值和历史最值
- 最难一题
- 扫描线与线段树
- 扫描线例题1
- 天际线
- 矩形面积并
- 矩形周长并
- 摩尔投票
- 找海王
线段树原理
判->down->子递归->up
经典模版
https://www.luogu.com.cn/problem/P3372
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll add2[N<<2];
ll sm[N<<2];
inline void up(int i){sm[i]=sm[i<<1]+sm[(i<<1)|1];
}
inline void build(int l,int r,int i){if(l==r){sm[i]=a[l];return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);add2[i]=0;
}
inline void lazy(int i,ll v,ll n){sm[i]+=v*n;add2[i]+=v;
}
inline void down(int i,ll ln,ll rn){if(add2[i]!=0){lazy(i<<1,add2[i],ln);lazy((i<<1)|1,add2[i],rn);add2[i]=0;}
}
inline void add1(int jl,int jr,ll w,int l,int r,int i){if(jl<=l && r<=jr){lazy(i,w,r-l+1);}else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)add1(jl,jr,w,l,mid,i<<1);if(jr>mid)add1(jl,jr,w,mid+1,r,(i<<1)|1);up(i);}
}
inline ll query(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll ans=0;if(ql<=mid)ans+=query(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline void solve(){int n,m;cin>>n>>m;build(1,n,1);for(ll i=1,x;i<=n;i++){cin>>x;add1(i,i,x,1,n,1);}int op;ll x,y,k;while(m--){cin>>op;if(op==1){cin>>x>>y>>k;add1(x,y,k,1,n,1);}else{cin>>x>>y;cout<<query(x,y,1,n,1)<<'\n';}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
https://www.luogu.com.cn/problem/P1253
支持区间重置，区间增加，求区间最大值
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 1000004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll add2[N<<2];
ll sm[N<<2];
bool update[N<<2];
ll chg[N<<2];
inline void up(int i){sm[i]=max(sm[i<<1],sm[(i<<1)|1]);
}
inline void build(int l,int r,int i){if(l==r){sm[i]=a[l];return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);add2[i]=0;update[i]=0;chg[i]=0;
}
inline void addlazy(int i,ll v,ll n){sm[i]+=v;add2[i]+=v;
}
inline void chglazy(int i,ll v,ll n){sm[i]=v;add2[i]=0;chg[i]=v;update[i]=1;
}
inline void down(int i,ll ln,ll rn){if(update[i]){chglazy(i<<1,chg[i],ln);chglazy((i<<1)|1,chg[i],rn);update[i]=0;}if(add2[i]){addlazy(i<<1,add2[i],ln);addlazy((i<<1)|1,add2[i],rn);add2[i]=0;}
}
inline void add1(int jl,int jr,ll w,int l,int r,int i){if(jl<=l && r<=jr){addlazy(i,w,r-l+1);}else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)add1(jl,jr,w,l,mid,i<<1);if(jr>mid)add1(jl,jr,w,mid+1,r,(i<<1)|1);up(i);}
}
inline void change1(int jl,int jr,ll w,int l,int r,int i){if(jl<=l && r<=jr){chglazy(i,w,r-l+1);}else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)change1(jl,jr,w,l,mid,i<<1);if(jr>mid)change1(jl,jr,w,mid+1,r,(i<<1)|1);up(i);}
}
inline ll query(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll ans=-1e17;if(ql<=mid)ans=max(ans,query(ql,qr,l,mid,i<<1));if(qr>mid)ans=max(ans,query(ql,qr,mid+1,r,(i<<1)|1));return ans;
}
inline void solve(){int n,m;cin>>n>>m;build(1,n,1);for(ll i=1,x;i<=n;i++){cin>>x;add1(i,i,x,1,n,1);}int op;ll x,y,k;while(m--){cin>>op;if(op==2){cin>>x>>y>>k;add1(x,y,k,1,n,1);}else if(op==1){cin>>x>>y>>k;change1(x,y,k,1,n,1);}else{cin>>x>>y;cout<<query(x,y,1,n,1)<<'\n';}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
线段树离散化，二分搜索，特别修改
离散化例题
https://leetcode.cn/problems/falling-squares/description/
class Solution {
const static int N = 2002;
public:typedef long long ll;ll a[N];ll chg[N<<2];bool update[N<<2];unordered_map<ll,int>my_map;ll sm[N<<2];inline void up(int i){sm[i]=max(sm[i<<1],sm[(i<<1)|1]);}inline void build(int l,int r,int i){if(l==r){sm[i]=a[l];return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);update[i]=0;}inline void lazy(int i,ll v){sm[i]=v;chg[i]=v;update[i]=1;}inline void down(int i){if(update[i]){lazy(i<<1,chg[i]);lazy((i<<1)|1,chg[i]);update[i]=0;}}inline void change1(int jl,int jr,ll w,int l,int r,int i){if(jl<=l && r<=jr){lazy(i,w);}else{int mid=(l+r)>>1;down(i);if(jl<=mid)change1(jl,jr,w,l,mid,i<<1);if(jr>mid)change1(jl,jr,w,mid+1,r,(i<<1)|1);up(i);}}inline ll query(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;down(i);//重要ll ans=0;if(ql<=mid)ans=max(ans,query(ql,qr,l,mid,i<<1));if(qr>mid)ans=max(ans,query(ql,qr,mid+1,r,(i<<1)|1));return ans;}vector<int> fallingSquares(vector<vector<int>>& positions) {vector<int>ans;vector<ll>ls;for(auto &p:positions){ls.emplace_back(p[0]);ls.emplace_back(p[0]+p[1]-1);}sort(ls.begin(),ls.end());ls.erase(unique(ls.begin(),ls.end()),ls.end());int n=ls.size();for(int i=0;i<n;i++)my_map[ls[i]]=i+1;build(1,n,1);for(auto &p:positions){ll l1=p[0],r1=p[0]+p[1]-1;int l2=my_map[l1],r2=my_map[r1];// ll l2=(lower_bound(ls.begin(),ls.end(),l1)-ls.begin()+1);// ll r2=(lower_bound(ls.begin(),ls.end(),r1)-ls.begin()+1);ll mm=query(l2,r2,1,n,1);change1(l2,r2,mm+p[1],1,n,1);ans.push_back(query(1,n,1,n,1));}return ans;}
};
特别修改
开方
https://www.luogu.com.cn/problem/P4145
题目特殊之处：开平方修改
考虑数据范围为1e12,最多开6次就会变成1；
那么考虑剪枝，若所开范围全为1（用mx[i]==1)判断，就不用往下；
那么考虑复杂度，一个叶子节点开方的所均摊的复杂度为树的高度；
故复杂度为6nlogn
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll sm[N<<2];
ll mx[N<<2];
inline void up(int i){sm[i]=sm[i<<1]+sm[(i<<1)|1];mx[i]=max(mx[i<<1],mx[(i<<1)|1]);
}
inline void build(int l,int r,int i){if(l==r){sm[i]=a[l];mx[i]=sm[i];return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);
}
inline void sqrt1(int jl,int jr,int l,int r,int i){if(l==r){sm[i]=floor(sqrt((double)(sm[i])));mx[i]=sm[i];return;}int mid=(l+r)>>1;if(jl<=mid && mx[i<<1]>1)sqrt1(jl,jr,l,mid,i<<1);if(jr>mid && mx[(i<<1)|1]>1)sqrt1(jl,jr,mid+1,r,(i<<1)|1);up(i);
}
inline ll query(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;ll ans=0;if(ql<=mid)ans+=query(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline void solve(){int n,m;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}build(1,n,1);cin>>m;int op;ll x,y;while(m--){cin>>op>>x>>y;if(x>y){int tmp=x;x=y;y=tmp;}if(op==1)cout<<query(x,y,1,n,1)<<'\n';else {// if(!(query(x,y,1,n,1)==(y-x+1)))sqrt1(x,y,1,n,1);sqrt1(x,y,1,n,1);}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
取模
https://vjudge.net/problem/CodeForces-438D
和上题差不多，每个数a最多取模loga次,同上剪枝，若mx[i]<mod,则不用往下；
AC代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll sm[N<<2];
ll mx[N<<2];
inline void up(int i){sm[i]=sm[i<<1]+sm[(i<<1)|1];mx[i]=max(mx[i<<1],mx[(i<<1)|1]);
}
inline void build(int l,int r,int i){if(l==r){sm[i]=a[l];mx[i]=sm[i];return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);
}
inline void mod1(int jl,int jr,ll x,int l,int r,int i){if(l==r){sm[i]=sm[i]%x;mx[i]=sm[i];return;}int mid=(l+r)>>1;if(jl<=mid && mx[i<<1]>=x)mod1(jl,jr,x,l,mid,i<<1);if(jr>mid && mx[(i<<1)|1]>=x)mod1(jl,jr,x,mid+1,r,(i<<1)|1);up(i);
}
inline void change1(ll k,ll x,int l,int r,int i){if(l==r && k==l){sm[i]=x;mx[i]=x;return;}int mid=(l+r)>>1;if(k<=mid)change1(k,x,l,mid,i<<1);else if(k>mid)change1(k,x,mid+1,r,(i<<1)|1);up(i);
}
inline ll query(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;ll ans=0;if(ql<=mid)ans+=query(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}build(1,n,1);int op;ll l,r,x,k;while(m--){cin>>op;if(op==1){cin>>l>>r;cout<<query(l,r,1,n,1)<<'\n';}else if(op==2){cin>>l>>r>>x;mod1(l,r,x,1,n,1);}else{cin>>k>>x;change1(k,x,1,n,1);}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
贴海报
https://www.luogu.com.cn/problem/P3740
维护范围是否统一了一种海报
同时需要离散化，并且每个离散点中间要在插入一个点，否则会出问题
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
struct le{int l;int r;
}a[N];
int t;
ll post[N<<2];//非0代表统一了一种海报
int ans=0;
map<int,int>my_map1;
bool vv[N];
inline void build(int l,int r,int i){if(l==r){return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);post[i]=0;
}
inline void lazy(int i,ll v){post[i]=v;
}
inline void down(int i){if(post[i]){lazy(i<<1,post[i]);lazy((i<<1)|1,post[i]);post[i]=0;}
}
inline void add1(int jl,int jr,ll w,int l,int r,int i){if(jl<=l && r<=jr){lazy(i,w);}else{int mid=(l+r)>>1;down(i);if(jl<=mid)add1(jl,jr,w,l,mid,i<<1);if(jr>mid)add1(jl,jr,w,mid+1,r,(i<<1)|1);}
}
inline void query(int l,int r,int i){if(l==r){if(post[i] && !vv[post[i]])ans++,vv[post[i]]=1;return;}int mid=(l+r)>>1;down(i);//重要query(l,mid,i<<1);query(mid+1,r,(i<<1)|1);
}
inline void solve(){int n,m;cin>>n>>m;//离散化vector<int>b;vector<int>bb;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;a[i].l=x,a[i].r=y;b.push_back(x),b.push_back(y);}sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());int nn=b.size();for(int i=0;i<nn;i++){bb.push_back(b[i]);if(i!=nn-1 && b[i]+1!=b[i+1])bb.push_back((b[i]+b[i+1])>>1);}n=bb.size();for(int i=0;i<n;i++)my_map1[bb[i]]=i+1;for(int i=1;i<=m;i++){int l=my_map1[a[i].l],r=my_map1[a[i].r];add1(l,r,i,1,n,1);}query(1,n,1);cout<<ans<<'\n';
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
更多类型信息，势能分析
开关
https://www.luogu.com.cn/problem/P3870
核心代码
sm[N]范围和，chg[N]是否翻转
inline void lazy(int i,ll n){sm[i]=n-sm[i];chg[i]=1-chg[i];
}
AC代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll chg[N<<2];
ll sm[N<<2];
inline void up(int i){sm[i]=sm[i<<1]+sm[(i<<1)|1];
}
inline void build(int l,int r,int i){if(l==r){sm[i]=0;return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);chg[i]=0;
}
inline void lazy(int i,ll n){sm[i]=n-sm[i];chg[i]=1-chg[i];
}
inline void down(int i,ll ln,ll rn){if(chg[i]){lazy(i<<1,ln);lazy((i<<1)|1,rn);chg[i]=0;}
}
inline void chg1(int jl,int jr,ll w,int l,int r,int i){if(jl<=l && r<=jr){lazy(i,r-l+1);}else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)chg1(jl,jr,w,l,mid,i<<1);if(jr>mid)chg1(jl,jr,w,mid+1,r,(i<<1)|1);up(i);}
}
inline ll query(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll ans=0;if(ql<=mid)ans+=query(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline void solve(){int n,m;cin>>n>>m;build(1,n,1);int op;ll x,y;while(m--){cin>>op>>x>>y;if(op==1){cout<<query(x,y,1,n,1)<<'\n';}else{chg1(x,y,1,1,n,1);}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
地雷
https://www.luogu.com.cn/problem/P2184
记录范围的地雷开头数量sm1[i]，以及地雷结尾数量sm2[i]
那么任意范围(l,r)的地雷种类数为sm1[1-r] - sm2[1-(l-1)]
所以只涉及到单点修改，因此不用懒标记（或者说用树状数组也能做）
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll sm1[N<<2];//开头
ll sm2[N<<2];//结尾
inline void up(int i){sm1[i]=sm1[i<<1]+sm1[(i<<1)|1];sm2[i]=sm2[i<<1]+sm2[(i<<1)|1];
}
inline void build(int l,int r,int i){if(l==r){sm2[i]=0;sm1[i]=0;return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);
}inline void add1(int k,int d,int l,int r,int i){if(l==r){if(d)sm1[i]++;else sm2[i]++;return;}int mid=(l+r)>>1;if(k<=mid)add1(k,d,l,mid,i<<1);else add1(k,d,mid+1,r,(i<<1)|1);up(i);
}
inline ll query1(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm1[i];int mid=(l+r)>>1;ll ans=0;if(ql<=mid)ans+=query1(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query1(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline ll query2(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm2[i];int mid=(l+r)>>1;ll ans=0;if(ql<=mid)ans+=query2(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query2(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline void solve(){int n,m;cin>>n>>m;build(1,n,1);int op;ll x,y;while(m--){cin>>op>>x>>y;if(op==1){add1(x,1,1,n,1);add1(y,0,1,n,1);}else{cout<<(query1(1,y,1,n,1)-query2(1,x-1,1,n,1))<<'\n';}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
范围增加等差数列
学树状数组时写过这道题，这里就只贴出题解
线段树解法
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 1000004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll sm1[N<<2];//开头
ll sm2[N<<2];//结尾
inline void up(int i){sm1[i]=sm1[i<<1]+sm1[(i<<1)|1];sm2[i]=sm2[i<<1]+sm2[(i<<1)|1];
}
inline void build(int l,int r,int i){if(l==r){sm2[i]=0;sm1[i]=0;return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);
}inline void add1(ll k,ll d,int l,int r,int i){if(l==r){sm1[i]+=d;sm2[i]+=d*l;return;}int mid=(l+r)>>1;if(k<=mid)add1(k,d,l,mid,i<<1);else add1(k,d,mid+1,r,(i<<1)|1);up(i);
}
inline ll query1(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm1[i];int mid=(l+r)>>1;ll ans=0;if(ql<=mid)ans+=query1(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query1(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline ll query2(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm2[i];int mid=(l+r)>>1;ll ans=0;if(ql<=mid)ans+=query2(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query2(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];build(1,n,1);int op;ll l,r,s,d;while(m--){cin>>op;if(op==1){cin>>l>>r>>s>>d;ll e=s+(r-l)*d;add1(l,s,1,n,1);if(l+1<=n)add1(l+1,d-s,1,n,1);if(r+1<=n)add1(r+1,-d-e,1,n,1);if(r+2<=n)add1(r+2,e,1,n,1);}else{cin>>l;cout<<(a[l]+(l+1)*query1(1,l,1,n,1)-query2(1,l,1,n,1))<<'\n';}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
方差
https://www.luogu.com.cn/problem/P1471
sm1:范围和，sm2:平方和
lazy模块
inline void lazy(int i,ll v,int n){sm2[i]+=2*v*sm1[i]+n*v*v;sm1[i]+=v*n;add2[i]+=v;
}
#include <bits/stdc++.h>
#define ll double
#define ull unsigned long long
#define N 1000004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll add2[N];
ll sm1[N<<2];//开头
ll sm2[N<<2];//平方和
inline void up(int i){sm1[i]=sm1[i<<1]+sm1[(i<<1)|1];sm2[i]=sm2[i<<1]+sm2[(i<<1)|1];
}
inline void build(int l,int r,int i){if(l==r){sm2[i]=a[l]*a[l];sm1[i]=a[l];return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);
}inline void lazy(int i,ll v,int n){sm2[i]+=2*v*sm1[i]+n*v*v;sm1[i]+=v*n;add2[i]+=v;
}
inline void down(int i,int ln,int rn){if(add2[i]!=0){lazy(i<<1,add2[i],ln);lazy((i<<1)|1,add2[i],rn);add2[i]=0;}
}
inline void add1(int jl,int jr,ll w,int l,int r,int i){if(jl<=l && r<=jr){lazy(i,w,r-l+1);}else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)add1(jl,jr,w,l,mid,i<<1);if(jr>mid)add1(jl,jr,w,mid+1,r,(i<<1)|1);up(i);}
}
inline ll query1(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm1[i];int mid=(l+r)>>1;ll ans=0;down(i,mid-l+1,r-mid);if(ql<=mid)ans+=query1(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query1(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline ll query2(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm2[i];int mid=(l+r)>>1;ll ans=0;down(i,mid-l+1,r-mid);if(ql<=mid)ans+=query2(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query2(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline void solve(){int n,m;scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)scanf("%lf",a+i);build(1,n,1);int op,x,y;double k;while(m--){scanf("%d",&op);if(op==1){scanf("%d %d %lf",&x,&y,&k);add1(x,y,k,1,n,1);}else if(op==2){scanf("%d %d",&x,&y);printf("%.4lf\n",query1(x,y,1,n,1)/(y-x+1));}else{scanf("%d %d",&x,&y);int leng=y-x+1;double av=query1(x,y,1,n,1)/leng;double ans=query2(x,y,1,n,1)/leng-av*av;printf("%.4lf\n",ans);}}
}
int main(){// ios::sync_with_stdio(0);// cin.tie(0);solve();return 0;
}
线段树解决区间合并问题
经典问题：连续1最长子串
我们考虑维护三个信息：
1.最长子串长度 2.最长前缀长度 3.最长后缀长度
三个信息结合起来就满足（小范围推大范围）
最经典例题
https://www.luogu.com.cn/problem/P2572
!!!!!!!!!!!!!!!一开始没对，是因为fan的逻辑写错了！！！！
是fan[i]=1-fan[i]，而不是fan[i]=1!!!!!,因为翻转操作具有叠加性，依赖上一次状态！！！
这两句取max,min也挺重要的，但是我一开始没加却也过了，大概是测试数据不太强
if(ans==mid-max(l,ql)+1)ans+=you;if(ans==min(r,qr)-mid)ans+=zuo;
我的写法：需要三个函数query2,query3,query4
复杂度分析:nlogn*logn
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll a[N];
ll ch0[N<<2],ch1[N<<2],fan[N<<2];
ll sm[N<<2];
ll len1[N<<2],len0[N<<2],left1[N<<2],left0[N<<2],right1[N<<2],right0[N<<2];
inline void up(int i,int ln,int rn){sm[i]=sm[i<<1]+sm[(i<<1)|1];if(left0[i<<1]==ln)left0[i]=ln+left0[(i<<1)|1];else left0[i]=left0[i<<1];if(right0[(i<<1)|1]==rn)right0[i]=rn+right0[i<<1];else right0[i]=right0[(i<<1)|1];len0[i]=max({len0[i<<1],len0[(i<<1)|1],right0[i<<1]+left0[(i<<1)|1]});if(left1[i<<1]==ln)left1[i]=ln+left1[(i<<1)|1];else left1[i]=left1[i<<1];if(right1[(i<<1)|1]==rn)right1[i]=rn+right1[i<<1];else right1[i]=right1[(i<<1)|1];len1[i]=max({len1[i<<1],len1[(i<<1)|1],right1[i<<1]+left1[(i<<1)|1]});
}inline void build(int l,int r,int i){if(l==r){len1[i]=(a[l]==1),left1[i]=(a[l]==1),right1[i]=(a[l]==1);len0[i]=(a[l]==0),left0[i]=(a[l]==0),right0[i]=(a[l]==0);sm[i]=a[l];return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);ch0[i]=0,ch1[i]=0,fan[i]=0;
}
inline void ch0lazy(int i,ll n){len1[i]=left1[i]=right1[i]=0;len0[i]=left0[i]=right0[i]=n;sm[i]=0;ch1[i]=0,fan[i]=0,ch0[i]=1;//这部分逻辑很重要
}
inline void ch1lazy(int i,ll n){len1[i]=left1[i]=right1[i]=n;len0[i]=left0[i]=right0[i]=0;sm[i]=n;ch0[i]=0,fan[i]=0,ch1[i]=1;
}
inline void fanlazy(int i,ll n){int tmp;tmp=len0[i],len0[i]=len1[i],len1[i]=tmp;tmp=left0[i],left0[i]=left1[i],left1[i]=tmp;tmp=right0[i],right0[i]=right1[i],right1[i]=tmp;sm[i]=n-sm[i];fan[i]=1-fan[i];
}
//优先级很重要
inline void down(int i,ll ln,ll rn){if(ch0[i]){ch0lazy(i<<1,ln);ch0lazy((i<<1)|1,rn);ch0[i]=0;}if(ch1[i]){ch1lazy(i<<1,ln);ch1lazy((i<<1)|1,rn);ch1[i]=0;}if(fan[i]){fanlazy(i<<1,ln);fanlazy((i<<1)|1,rn);fan[i]=0;}
}
inline void prog(int jl,int jr,int op,int l,int r,int i){if(jl<=l && r<=jr){if(op==0)ch0lazy(i,r-l+1);else if(op==1)ch1lazy(i,r-l+1);else fanlazy(i,r-l+1);return;}else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)prog(jl,jr,op,l,mid,i<<1);if(jr>mid)prog(jl,jr,op,mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);}
}
inline ll query1(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll ans=0;if(ql<=mid)ans+=query1(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query1(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
//left1
inline ll query3(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return left1[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll zuo=0,you=0;if(ql<=mid)zuo=query3(ql,qr,l,mid,i<<1);if(qr>mid)you=query3(ql,qr,mid+1,r,(i<<1)|1);ll ans=zuo;if(ans==mid-max(l,ql)+1)ans+=you;return ans;
}
//right1
inline ll query4(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return right1[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll zuo=0,you=0;if(ql<=mid)zuo=query4(ql,qr,l,mid,i<<1);if(qr>mid)you=query4(ql,qr,mid+1,r,(i<<1)|1);ll ans=you;if(ans==min(r,qr)-mid)ans+=zuo;return ans;
}
//len1
inline ll query2(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return len1[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll zuo=0,you=0;ll ans=0;if(ql<=mid)zuo=query4(ql,qr,l,mid,i<<1),ans=query2(ql,qr,l,mid,i<<1);if(qr>mid)you=query3(ql,qr,mid+1,r,(i<<1)|1),ans=max(ans,query2(ql,qr,mid+1,r,(i<<1)|1));ans=max(ans,zuo+you);return ans;
}inline void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];build(1,n,1);int op;ll x,y;while(m--){cin>>op>>x>>y;x++,y++;if(op==3){cout<<query1(x,y,1,n,1)<<'\n';}else if(op==4){cout<<query2(x,y,1,n,1)<<'\n';}else{prog(x,y,op,1,n,1);}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
老师的写法：return 结构体
复杂度分析：nlogn3
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
struct le{ll len;ll pre;ll suf;
};
int t;
ll a[N];
ll ch0[N<<2],ch1[N<<2],fan[N<<2];
ll sm[N<<2];
ll len1[N<<2],len0[N<<2],left1[N<<2],left0[N<<2],right1[N<<2],right0[N<<2];
inline void up(int i,int ln,int rn){sm[i]=sm[i<<1]+sm[(i<<1)|1];if(left0[i<<1]==ln)left0[i]=ln+left0[(i<<1)|1];else left0[i]=left0[i<<1];if(right0[(i<<1)|1]==rn)right0[i]=rn+right0[i<<1];else right0[i]=right0[(i<<1)|1];len0[i]=max({len0[i<<1],len0[(i<<1)|1],right0[i<<1]+left0[(i<<1)|1]});if(left1[i<<1]==ln)left1[i]=ln+left1[(i<<1)|1];else left1[i]=left1[i<<1];if(right1[(i<<1)|1]==rn)right1[i]=rn+right1[i<<1];else right1[i]=right1[(i<<1)|1];len1[i]=max({len1[i<<1],len1[(i<<1)|1],right1[i<<1]+left1[(i<<1)|1]});
}inline void build(int l,int r,int i){if(l==r){len1[i]=(a[l]==1),left1[i]=(a[l]==1),right1[i]=(a[l]==1);len0[i]=(a[l]==0),left0[i]=(a[l]==0),right0[i]=(a[l]==0);sm[i]=a[l];return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);ch0[i]=0,ch1[i]=0,fan[i]=0;
}
inline void ch0lazy(int i,ll n){len1[i]=left1[i]=right1[i]=0;len0[i]=left0[i]=right0[i]=n;sm[i]=0;ch1[i]=0,fan[i]=0,ch0[i]=1;//这部分逻辑很重要
}
inline void ch1lazy(int i,ll n){len1[i]=left1[i]=right1[i]=n;len0[i]=left0[i]=right0[i]=0;sm[i]=n;ch0[i]=0,fan[i]=0,ch1[i]=1;
}
inline void fanlazy(int i,ll n){int tmp;tmp=len0[i],len0[i]=len1[i],len1[i]=tmp;tmp=left0[i],left0[i]=left1[i],left1[i]=tmp;tmp=right0[i],right0[i]=right1[i],right1[i]=tmp;sm[i]=n-sm[i];fan[i]=1-fan[i];
}
//优先级很重要
inline void down(int i,ll ln,ll rn){if(ch0[i]){ch0lazy(i<<1,ln);ch0lazy((i<<1)|1,rn);ch0[i]=0;}if(ch1[i]){ch1lazy(i<<1,ln);ch1lazy((i<<1)|1,rn);ch1[i]=0;}if(fan[i]){fanlazy(i<<1,ln);fanlazy((i<<1)|1,rn);fan[i]=0;}
}
inline void prog(int jl,int jr,int op,int l,int r,int i){if(jl<=l && r<=jr){if(op==0)ch0lazy(i,r-l+1);else if(op==1)ch1lazy(i,r-l+1);else fanlazy(i,r-l+1);return;}else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)prog(jl,jr,op,l,mid,i<<1);if(jr>mid)prog(jl,jr,op,mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);}
}
inline ll query1(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll ans=0;if(ql<=mid)ans+=query1(ql,qr,l,mid,i<<1);if(qr>mid)ans+=query1(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
//left1
inline ll query3(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return left1[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll zuo=0,you=0;if(ql<=mid)zuo=query3(ql,qr,l,mid,i<<1);if(qr>mid)you=query3(ql,qr,mid+1,r,(i<<1)|1);ll ans=zuo;if(ans==mid-max(l,ql)+1)ans+=you;return ans;
}
//right1
inline ll query4(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return right1[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);//重要ll zuo=0,you=0;if(ql<=mid)zuo=query4(ql,qr,l,mid,i<<1);if(qr>mid)you=query4(ql,qr,mid+1,r,(i<<1)|1);ll ans=you;if(ans==min(r,qr)-mid)ans+=zuo;return ans;
}
//len1
inline le query2(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return (le){len1[i],left1[i],right1[i]};int mid=(l+r)>>1;le ans;down(i,mid-l+1,r-mid);//重要if(mid>=qr)return query2(ql,qr,l,mid,i<<1);if(mid<ql)return query2(ql,qr,mid+1,r,(i<<1)|1);// zuo=query4(ql,qr,l,mid,i<<1),ans=query2(ql,qr,l,mid,i<<1);// you=query3(ql,qr,mid+1,r,(i<<1)|1),ans=max(ans,query2(ql,qr,mid+1,r,(i<<1)|1));// ans=max(ans,zuo+you);le l3=query2(ql,qr,l,mid,i<<1),r3=query2(ql,qr,mid+1,r,(i<<1)|1);ans.len=max({l3.len,r3.len,l3.suf+r3.pre});ans.pre=l3.pre<mid-max(l,ql)+1 ? l3.pre : l3.pre+r3.pre;ans.suf=r3.suf<min(r,qr)-mid ? r3.suf : r3.suf+l3.suf;return ans;
}inline void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];build(1,n,1);int op;ll x,y;while(m--){cin>>op>>x>>y;x++,y++;if(op==3){cout<<query1(x,y,1,n,1)<<'\n';}else if(op==4){cout<<query2(x,y,1,n,1).len<<'\n';}else{prog(x,y,op,1,n,1);}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
最长LR交替子串
比较简单：单点修改，故不用懒标记，且查询的永远是1~n,故query方法都不需要
难在设置维护的数组
https://www.luogu.com.cn/problem/P6492
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 200004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
ll len1[N<<2],prel[N<<2],prer[N<<2],sufl[N<<2],sufr[N<<2];
inline void up(int i,int ln,int rn){int l=(i<<1),r=(i<<1)|1;len1[i]=max({len1[l],len1[r],sufl[l]+prer[r],sufr[l]+prel[r]});prel[i] = prel[l]<ln ? prel[l] : (ln&1 ? ln+prer[r] : ln+prel[r]);prer[i] = prer[l]<ln ? prer[l] : (ln&1 ? ln+prel[r] : ln+prer[r]);sufl[i] = sufl[r]<rn ? sufl[r] : (rn&1 ? rn+sufr[l] : rn+sufl[l]);sufr[i] = sufr[r]<rn ? sufr[r] : (rn&1 ? rn+sufl[l] : rn+sufr[l]);
}
inline void build(int l,int r,int i){if(l==r){len1[i]=1;prel[i]=sufl[i]=1;prer[i]=sufr[i]=0;return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);
}inline void prog(int k,int l,int r,int i){if(l==r){prel[i]=1-prel[i],sufl[i]=1-sufl[i];prer[i]=1-prer[i],sufr[i]=1-sufr[i];return;}int mid=(l+r)>>1;if(k<=mid)prog(k,l,mid,i<<1);else prog(k,mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);
}
inline void solve(){int n,m;cin>>n>>m;build(1,n,1);ll x;while(m--){cin>>x;prog(x,1,n,1);cout<<len1[1]<<'\n';}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
鬼子进村
https://www.luogu.com.cn/problem/P1503
注意边界
维护最长前缀，后缀
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
int t;
int a[N];
ll pre[N<<2],suf[N<<2];
int sta[N];
int n,m;
int top=-1;
//1摧毁，0没被摧毁
inline void up(int i,int ln,int rn){int l=(i<<1),r=((i<<1)|1);pre[i] = pre[l]<ln ? pre[l] : ln+pre[r];suf[i] = suf[r]<rn ? suf[r] : rn+suf[l];
}
inline void build(int l,int r,int i){if(l==r){pre[i]=suf[i]=1;return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);
}
inline void prog(int k,int l,int r,int i){if(l==r){pre[i]=1-pre[i];suf[i]=1-suf[i];return;}int mid=(l+r)>>1;if(k<=mid)prog(k,l,mid,i<<1);else prog(k,mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);
}
inline ll querypre(int ql,int qr,int l,int r,int i){if(ql>n)return 0;if(qr<1)return 0;if(ql<=l && r<=qr)return pre[i];int mid=(l+r)>>1;if(mid>=qr)return querypre(ql,qr,l,mid,i<<1);if(mid<ql)return querypre(ql,qr,mid+1,r,(i<<1)|1);int l1=querypre(ql,qr,l,mid,i<<1),r1=querypre(ql,qr,mid+1,r,(i<<1)|1);int ans = (l1<mid-max(l,ql)+1) ? l1 : l1+r1;return ans;
}
inline ll querysuf(int ql,int qr,int l,int r,int i){if(ql>n)return 0;if(qr<1)return 0;if(ql<=l && r<=qr)return suf[i];int mid=(l+r)>>1;if(mid>=qr)return querysuf(ql,qr,l,mid,i<<1);if(mid<ql)return querysuf(ql,qr,mid+1,r,(i<<1)|1);int l1=querysuf(ql,qr,l,mid,i<<1),r1=querysuf(ql,qr,mid+1,r,(i<<1)|1);int ans = (r1<min(r,qr)-mid) ? r1 : l1+r1;return ans;
}
inline void solve(){cin>>n>>m;build(1,n,1);char op;int k;while(m--){cin>>op;if(op=='D'){cin>>k;sta[++top]=k;a[k]=1;prog(k,1,n,1);}else if(op=='R'){k=sta[top--];a[k]=0;prog(k,1,n,1);}else{cin>>k;if(a[k])cout<<"0\n";else{cout<<querypre(k+1,n,1,n,1)+querysuf(1,k-1,1,n,1)+1<<'\n';}}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
hotel
https://www.luogu.com.cn/problem/P2894
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 500004
using namespace std;
const ll mod=19930726;
const ll base=499;
struct le{ll len;ll pre;ll suf;
};
int t;
ll a[N];
ll ch0[N<<2],ch1[N<<2];
ll len0[N<<2],left0[N<<2],right0[N<<2];
inline void up(int i,int ln,int rn){if(left0[i<<1]==ln)left0[i]=ln+left0[(i<<1)|1];else left0[i]=left0[i<<1];if(right0[(i<<1)|1]==rn)right0[i]=rn+right0[i<<1];else right0[i]=right0[(i<<1)|1];len0[i]=max({len0[i<<1],len0[(i<<1)|1],right0[i<<1]+left0[(i<<1)|1]});
}inline void build(int l,int r,int i){if(l==r){len0[i]=left0[i]=right0[i]=1;return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);ch0[i]=0,ch1[i]=0;
}
inline void ch0lazy(int i,ll n){len0[i]=left0[i]=right0[i]=n;ch1[i]=0,ch0[i]=1;//这部分逻辑很重要
}
inline void ch1lazy(int i,ll n){len0[i]=left0[i]=right0[i]=0;ch0[i]=0,ch1[i]=1;
}
//优先级很重要
inline void down(int i,ll ln,ll rn){if(ch0[i]){ch0lazy(i<<1,ln);ch0lazy((i<<1)|1,rn);ch0[i]=0;}else if(ch1[i]){ch1lazy(i<<1,ln);ch1lazy((i<<1)|1,rn);ch1[i]=0;}
}
inline void prog(int jl,int jr,int op,int l,int r,int i){if(jl<=l && r<=jr){if(op==0)ch0lazy(i,r-l+1);else ch1lazy(i,r-l+1);return;}else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)prog(jl,jr,op,l,mid,i<<1);if(jr>mid)prog(jl,jr,op,mid+1,r,(i<<1)|1);up(i,mid-l+1,r-mid);}
}
//len1
inline le query2(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return (le){len0[i],left0[i],right0[i]};int mid=(l+r)>>1;le ans;down(i,mid-l+1,r-mid);//重要if(mid>=qr)return query2(ql,qr,l,mid,i<<1);if(mid<ql)return query2(ql,qr,mid+1,r,(i<<1)|1);le l3=query2(ql,qr,l,mid,i<<1),r3=query2(ql,qr,mid+1,r,(i<<1)|1);ans.len=max({l3.len,r3.len,l3.suf+r3.pre});ans.pre=l3.pre<mid-max(l,ql)+1 ? l3.pre : l3.pre+r3.pre;ans.suf=r3.suf<min(r,qr)-mid ? r3.suf : r3.suf+l3.suf;return ans;
}inline void solve(){int n,m;cin>>n>>m;build(1,n,1);int op;ll x,y;while(m--){cin>>op;if(op==1){cin>>x;int mx=query2(1,n,1,n,1).len;if(mx<x){cout<<"0\n";}else{int l=0,r=n;while(l+1<r){int mid=(l+r)>>1;if(query2(1,mid,1,n,1).len<x)l=mid;else r=mid;}cout<<r-x+1<<'\n';// if(l-x+1==93 && cnt==2)cout<<x<<' '<<l<<' '<<query2(1,l,1,n,1).len<<' '<<query2(1,l-1,1,n,1).len<<"sfaf\n";prog(r-x+1,r,1,1,n,1);}}else{cin>>x>>y;prog(x,x+y-1,0,1,n,1);}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
区间最值和历史最值
标签回收和势能分析
若某节点的最大值与父节点的最大值不同，则贴上标签
有一些几个性质：
1.当某节点被遍历，则该节点被回收
2.来到某节点，若还会往下走，说明子树中还有标签未回收
3.某节点子树中还有标签未回收当且仅当此节点还存在严格次大值
题目链接：
https://vjudge.net/problem/HDU-5306
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 1000004
using namespace std;
ll lowest=-1;
ll a[N];
int t;
ll mx[N<<2],cmx[N<<2],cnt[N<<2],sm[N<<2];
inline void up(int i){int l=(i<<1),r=(i<<1)|1;sm[i]=sm[l]+sm[r];mx[i]=max(mx[l],mx[r]);if(mx[l]>mx[r]){cnt[i]=cnt[l],cmx[i]=max(cmx[l],mx[r]);}else if(mx[l]<mx[r]){cnt[i]=cnt[r],cmx[i]=max(cmx[r],mx[l]);}else{cnt[i]=cnt[l]+cnt[r],cmx[i]=max(cmx[l],cmx[r]);}
}
inline void build(int l,int r,int i){if(l==r){sm[i]=mx[i]=a[l];cmx[i]=lowest;cnt[i]=1;return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);
}
inline void lazy(int i,ll v){if(v<mx[i]){sm[i]-=(mx[i]-v)*cnt[i];mx[i]=v;}
}
inline void down(int i){lazy(i<<1,mx[i]);lazy((i<<1)|1,mx[i]);
}
inline void setmin(int jl,int jr,ll v,int l,int r,int i){if(v>=mx[i])return;if(jl<=l && r<=jr && v>cmx[i])lazy(i,v);else{down(i);int mid=(l+r)>>1;if(jl<=mid)setmin(jl,jr,v,l,mid,i<<1);if(jr>mid)setmin(jl,jr,v,mid+1,r,(i<<1)|1);up(i);}
}
inline ll querysm(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;down(i);ll ans=0;if(ql<=mid)ans+=querysm(ql,qr,l,mid,i<<1);if(qr>mid)ans+=querysm(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline ll querymx(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return mx[i];int mid=(l+r)>>1;down(i);ll ans=0;if(ql<=mid)ans=max(ans,querymx(ql,qr,l,mid,i<<1));if(qr>mid)ans=max(ans,querymx(ql,qr,mid+1,r,(i<<1)|1));return ans;
}
inline void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];build(1,n,1);ll op,x,y,w;while(m--){cin>>op;if(op==0){cin>>x>>y>>w;setmin(x,y,w,1,n,1);}else if(op==1){cin>>x>>y;cout<<querymx(x,y,1,n,1)<<'\n';}else{cin>>x>>y;cout<<querysm(x,y,1,n,1)<<'\n';}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>t;while(t--)solve();return 0;
}
最难一题
https://www.luogu.com.cn/problem/P6242
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 500004
using namespace std;
ll lowest=-1e15;
ll a[N];
int t;
ll mx[N<<2],cmx[N<<2],cnt[N<<2],sm[N<<2],mxadd[N<<2],otheradd[N<<2],mxhistory[N<<2],mxaddtop[N<<2],otheraddtop[N<<2];
inline void up(int i){int l=(i<<1),r=(i<<1)|1;sm[i]=sm[l]+sm[r];mxhistory[i]=max(mxhistory[l],mxhistory[r]);mx[i]=max(mx[l],mx[r]);if(mx[l]>mx[r]){cnt[i]=cnt[l],cmx[i]=max(cmx[l],mx[r]);}else if(mx[l]<mx[r]){cnt[i]=cnt[r],cmx[i]=max(cmx[r],mx[l]);}else{cnt[i]=cnt[l]+cnt[r],cmx[i]=max(cmx[l],cmx[r]);}
}
inline void build(int l,int r,int i){if(l==r){sm[i]=mx[i]=mxhistory[i]=a[l];cmx[i]=lowest;cnt[i]=1;return;}int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);up(i);mxadd[i]=0,otheradd[i]=0,mxaddtop[i]=0,otheraddtop[i]=0;
}
inline void lazy(int i,int n,ll mxaddv,ll otheraddv,ll maxupv,ll otherupv){mxhistory[i]=max(mxhistory[i],maxupv+mx[i]);mxaddtop[i]=max(mxaddtop[i],mxadd[i]+maxupv);otheraddtop[i]=max(otheraddtop[i],otheradd[i]+otherupv);sm[i]+=mxaddv*cnt[i]+otheraddv*(n-cnt[i]);mx[i]+=mxaddv;cmx[i]+= cmx[i]==lowest ? 0 : otheraddv;mxadd[i]+=mxaddv;otheradd[i]+=otheraddv;
}
inline void down(int i,int ln,int rn){int l=i<<1,r=(i<<1)|1;ll tmp=max(mx[l],mx[r]);if(mx[l]==tmp){lazy(i<<1,ln,mxadd[i],otheradd[i],mxaddtop[i],otheraddtop[i]);}else{lazy(i<<1,ln,otheradd[i],otheradd[i],otheraddtop[i],otheraddtop[i]);}if(mx[r]==tmp){lazy((i<<1)|1,rn,mxadd[i],otheradd[i],mxaddtop[i],otheraddtop[i]);}else{lazy((i<<1)|1,rn,otheradd[i],otheradd[i],otheraddtop[i],otheraddtop[i]);}mxadd[i]=0,otheradd[i]=0,mxaddtop[i]=0,otheraddtop[i]=0;
}
inline void add1(int jl,int jr,ll v,int l,int r,int i){if(jl<=l && r<=jr){lazy(i,r-l+1,v,v,v,v);return;}int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)add1(jl,jr,v,l,mid,i<<1);if(jr>mid)add1(jl,jr,v,mid+1,r,(i<<1)|1);up(i);
}
inline void setmin(int jl,int jr,ll v,int l,int r,int i){if(v>=mx[i])return;if(jl<=l && r<=jr && v>cmx[i])lazy(i,r-l+1,v-mx[i],0,v-mx[i],0);else{int mid=(l+r)>>1;down(i,mid-l+1,r-mid);if(jl<=mid)setmin(jl,jr,v,l,mid,i<<1);if(jr>mid)setmin(jl,jr,v,mid+1,r,(i<<1)|1);up(i);}
}
inline ll querysm(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return sm[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);ll ans=0;if(ql<=mid)ans+=querysm(ql,qr,l,mid,i<<1);if(qr>mid)ans+=querysm(ql,qr,mid+1,r,(i<<1)|1);return ans;
}
inline ll querymx(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return mx[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);ll ans=-1e15;if(ql<=mid)ans=max(ans,querymx(ql,qr,l,mid,i<<1));if(qr>mid)ans=max(ans,querymx(ql,qr,mid+1,r,(i<<1)|1));return ans;
}
inline ll querymxhistory(int ql,int qr,int l,int r,int i){if(ql<=l && r<=qr)return mxhistory[i];int mid=(l+r)>>1;down(i,mid-l+1,r-mid);ll ans=-1e15;if(ql<=mid)ans=max(ans,querymxhistory(ql,qr,l,mid,i<<1));if(qr>mid)ans=max(ans,querymxhistory(ql,qr,mid+1,r,(i<<1)|1));return ans;
}
inline void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];build(1,n,1);ll op,x,y,w;while(m--){cin>>op;if(op==1){cin>>x>>y>>w;add1(x,y,w,1,n,1);}else if(op==2){cin>>x>>y>>w;setmin(x,y,w,1,n,1);}else if(op==3){cin>>x>>y;cout<<querysm(x,y,1,n,1)<<'\n';}else if(op==4){cin>>x>>y;cout<<querymx(x,y,1,n,1)<<'\n';}else{cin>>x>>y;cout<<querymxhistory(x,y,1,n,1)<<'\n';}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
扫描线与线段树
扫描线例题1
https://leetcode.cn/problems/minimum-interval-to-include-each-query/description/
class Solution {
public:struct le{int d;int x;};struct cmp{bool operator()(const le&a,const le&b){return a.d>b.d;}};priority_queue<le,vector<le>,cmp>dui;vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {vector<le>q;int nq=0;for(auto &c:queries)q.push_back((le){c,nq++});vector<int>ans(nq);sort(q.begin(),q.end(),[](const le&a,const le&b){return a.d<b.d;});sort(intervals.begin(),intervals.end(),[](const auto&a,const auto&b){return a[0]<b[0];});int nn=intervals.size();int j=0;for(auto &p:q){while(j<nn && intervals[j][0]<=p.d){dui.push((le){intervals[j][1]-intervals[j][0]+1,intervals[j][1]});j++;}while(!dui.empty() && dui.top().x<p.d)dui.pop();ans[p.x]= dui.empty() ? -1 : dui.top().d;}return ans;}
};
天际线
https://www.luogu.com.cn/problem/P1904
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 500004
#define PII pair<int,int>
using namespace std;
struct le{int l;int r;int h;
};
vector<le>a;
vector<int>b;
PII ans[N];
priority_queue<PII>hp;
inline void solve(){int l,r,h;while(cin>>l){cin>>h>>r;a.push_back((le){l,r,h});b.push_back(l);b.push_back(r);} // cout<<"#rwa";sort(b.begin(),b.end());sort(a.begin(),a.end(),[](const le&x,const le&y){return x.l<y.l;});int ai=0;int na=a.size();int ansi=1;for(int i=0;i<(int)b.size();i++){while(a[ai].l<=b[i] && ai<na)hp.push({a[ai].h,a[ai].r}),ai++;while(!hp.empty() && hp.top().second<=b[i])hp.pop();if(!hp.empty()){if(hp.top().first!=ans[ansi-1].second)ans[ansi++]={b[i],hp.top().first};}else{ans[ansi++]={b[i],0};}}for(int i=1;i<ansi;i++){cout<<ans[i].first<<' '<<ans[i].second<<' ';}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
矩形面积并
https://www.luogu.com.cn/problem/P5490
线段树实时维护y轴覆盖的范围
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100004
using namespace std;
const ll mod=19930726;
const ll base=499;
struct le{ll x;ll yl,yr;ll d;
}xsort[N<<1];
ll ysort[N<<1];
int t;
int nysort=0,nxsort=0;
ll len[N<<4],cover[N<<4],times[N<<4];
inline int prepare(int ny){sort(ysort+1,ysort+1+ny);int m=1;for(int i=2;i<=ny;i++){if(ysort[m]!=ysort[i])ysort[++m]=ysort[i];}ysort[m+1]=ysort[m];return m;//?
}
inline void build(int l,int r,int i){if(l<r){int mid=(l+r)>>1;build(l,mid,i<<1);build(mid+1,r,(i<<1)|1);}len[i]=ysort[r+1]-ysort[l];cover[i]=0,times[i]=0;
}
inline void up(int i){if(times[i]>0)cover[i]=len[i];else cover[i]=cover[i<<1]+cover[(i<<1)|1];
}
inline int rank1(ll x){int l=1,r=nysort+2;while(l+1<r){int mid=(l+r)>>1;if(ysort[mid]<=x)l=mid;else r=mid;}return l;
}
inline void add1(int ql,int qr,ll d,int l,int r,int i){if(ql<=l && r<=qr){times[i]+=d;}else{int mid=(l+r)>>1;if(ql<=mid)add1(ql,qr,d,l,mid,i<<1);if(qr>mid)add1(ql,qr,d,mid+1,r,(i<<1)|1);}up(i);
}
inline void solve(){int n;cin>>n;ll a,b,c,d;for(int i=1;i<=n;i++){cin>>a>>b>>c>>d;ysort[++nysort]=b,ysort[++nysort]=d;xsort[++nxsort]=(le){a,b,d,1},xsort[++nxsort]=(le){c,b,d,-1};}nysort=prepare(nysort);build(1,nysort,1);sort(xsort+1,xsort+1+nxsort,[](const le&x,const le&y){return x.x<y.x;});ll ans=0;for(int i=1;i<=nxsort;i++){ans+=(cover[1])*(xsort[i].x-xsort[i-1].x);add1(rank1(xsort[i].yl),rank1(xsort[i].yr)-1,xsort[i].d,1,nysort,1);}cout<<ans<<'\n';
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
矩形周长并
x轴y轴方向分开算周长
！！！！！！重要：排序时d为1在前，也就是要先+后-,不然会多算
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 5004
#define PII pair<int,int>
using namespace std;
const ll mod=19930726;
const ll base=499;
struct le{ll now;ll l,r;ll d;
}xarr[N<<1],yarr[N<<1];
ll ysort[N<<1],xsort[N<<1];
int t;
int nysort=0,nxsort=0,nyarr=0,nxarr=0;
ll len[N<<4],cover[N<<4],times[N<<4];
inline void prepare(int ny,int nx){sort(ysort+1,ysort+1+ny);sort(xsort+1,xsort+1+nx);int my=1,mx=1;for(int i=2;i<=ny;i++)if(ysort[my]!=ysort[i])ysort[++my]=ysort[i];ysort[my+1]=ysort[my];for(int i=2;i<=nx;i++)if(xsort[mx]!=xsort[i])xsort[++mx]=xsort[i];xsort[mx+1]=xsort[mx];nxsort=mx,nysort=my;
}
//op0:x,op1:y
inline void build(int l,int r,int i,int op){if(l<r){int mid=(l+r)>>1;build(l,mid,i<<1,op);build(mid+1,r,(i<<1)|1,op);}if(op==1)len[i]=ysort[r+1]-ysort[l];else len[i]=xsort[r+1]-xsort[l];cover[i]=0,times[i]=0;
}
inline void up(int i){if(times[i]>0)cover[i]=len[i];else cover[i]=cover[i<<1]+cover[(i<<1)|1];
}
inline int rank1(ll x){int l=1,r=nysort+1;while(l+1<r){int mid=(l+r)>>1;if(ysort[mid]<=x)l=mid;else r=mid;}return l;
}
inline int rank2(ll x){int l=1,r=nxsort+1;while(l+1<r){int mid=(l+r)>>1;if(xsort[mid]<=x)l=mid;else r=mid;}return l;
}
inline void add1(int ql,int qr,ll d,int l,int r,int i){if(ql<=l && r<=qr){times[i]+=d;}else{int mid=(l+r)>>1;if(ql<=mid)add1(ql,qr,d,l,mid,i<<1);if(qr>mid)add1(ql,qr,d,mid+1,r,(i<<1)|1);}up(i);
}
inline void solve(){// freopen("a.txt","r",stdin);int n;cin>>n;ll a,b,c,d;for(int i=1;i<=n;i++){cin>>a>>b>>c>>d;ysort[++nysort]=b,ysort[++nysort]=d;xsort[++nxsort]=a,xsort[++nxsort]=c;xarr[++nxarr]=(le){a,b,d,1},xarr[++nxarr]=(le){c,b,d,-1};yarr[++nyarr]=(le){b,a,c,1},yarr[++nyarr]=(le){d,a,c,-1};// xsort[++nxsort]=(le){a,b,d,1},xsort[++nxsort]=(le){c,b,d,-1};}prepare(nysort,nxsort);sort(xarr+1,xarr+1+nxarr,[](const le&x,const le&y){return x.now<y.now || (x.now==y.now && x.d>y.d);});sort(yarr+1,yarr+1+nyarr,[](const le&x,const le&y){return x.now<y.now || (x.now==y.now && x.d>y.d);});ll ans1=0,ans2=0;build(1,nysort,1,1);for(ll i=1,pre=0;i<=nxarr;i++){pre=cover[1];add1(rank1(xarr[i].l),rank1(xarr[i].r)-1,xarr[i].d,1,nysort,1);ans1+=abs(cover[1]-pre);}build(1,nxsort,1,0);for(ll i=1,pre=0;i<=nyarr;i++){pre=cover[1];add1(rank2(yarr[i].l),rank2(yarr[i].r)-1,yarr[i].d,1,nxsort,1);ans2+=abs(cover[1]-pre);}cout<<ans1+ans2<<'\n';// cout<<ans1<<'\n';// cout<<ans2<<'\n';// cout<<maxi;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}
摩尔投票
例题：
https://leetcode.cn/problems/majority-element-ii/description/
class Solution {
public:int cands[2][2];//[][2]void update(int x,int k){for(int i=0;i<k;i++){if(x==cands[i][0] && cands[i][1]){cands[i][1]++;return;}}for(int i=0;i<k;i++){if(cands[i][1]==0){cands[i][0]=x;cands[i][1]=1;return;}}for(int i=0;i<k;i++){cands[i][1]--;}}vector<int> majorityElement(vector<int>& nums) {vector<int>ans;int n=nums.size();for(auto num:nums){update(num,2);}int k=2;for(int i=0;i<k;i++){if(cands[i][1]){int cnt=0;for(auto num:nums){cnt+=(num==cands[i][0]);}if(cnt>n/3)ans.push_back(cands[i][0]);}}return ans;}
};
找海王
https://leetcode.cn/problems/online-majority-element-in-subarray/description/
用线段树维护任意范围的伪海王(要判断数量是否>=t来最终确定)
用排序＋二分可以快速获得任意范围的指定数字的数量
class MajorityChecker {
public:const static int N=20003;struct le{int d;int x;}nums[N];int cand[N<<2],blood[N<<2];int n;void buildnum(vector<int>&arr){for(int i=0;i<n;i++)nums[i].d=arr[i],nums[i].x=i;sort(nums,nums+n,[&](const le&a,const le&b){return a.d<b.d || (a.d==b.d && a.x<b.x);});}void up(int i){int lc=cand[i<<1],rc=cand[(i<<1)|1];int lb=blood[i<<1],rb=blood[(i<<1)|1];cand[i]= lc==rc || lb>=rb ? lc : rc;blood[i]= lc==rc ? lb+rb : abs(lb-rb);}void build(vector<int>&arr,int l,int r,int i){if(l==r){cand[i]=arr[l-1];blood[i]=1;}else{int mid=(l+r)>>1;build(arr,l,mid,i<<1);build(arr,mid+1,r,(i<<1)|1);up(i);}}pair<int,int> find1(int jl,int jr,int l,int r,int i){if(jl<=l && r<=jr)return {cand[i],blood[i]};int mid=(l+r)>>1;if(jl>mid)return find1(jl,jr,mid+1,r,(i<<1)|1);if(mid>=jr)return find1(jl,jr,l,mid,i<<1);auto lch=find1(jl,jr,l,mid,i<<1),rch=find1(jl,jr,mid+1,r,(i<<1)|1);int lc=lch.first,rc=rch.first;int lb=lch.second,rb=rch.second;int c= lc==rc || lb>=rb ? lc : rc;int b= lc==rc ? lb+rb : abs(lb-rb);return {c,b};}int cnt1(int cand,int l1,int r1){int tmp1,tmp2;int l=-1,r=n;while(l+1<r){int mid=(l+r)>>1;if(nums[mid].d<cand || (nums[mid].d==cand && nums[mid].x<=l1-1))l=mid;else r=mid;}tmp1=l,l=-1,r=n;while(l+1<r){int mid=(l+r)>>1;if(nums[mid].d<cand || (nums[mid].d==cand && nums[mid].x<=r1))l=mid;else r=mid;}tmp2=l;return tmp2-tmp1;}MajorityChecker(vector<int>& arr) {n=arr.size();buildnum(arr),build(arr,1,n,1);}int query(int left, int right, int threshold) {auto ch=find1(left+1,right+1,1,n,1);int cand=ch.first;return cnt1(cand,left,right)>=threshold ? cand : -1;}
};/*** Your MajorityChecker object will be instantiated and called as such:* MajorityChecker* obj = new MajorityChecker(arr);* int param_1 = obj->query(left,right,threshold);*/