ACM模板

---

目錄

• • • 區間取最值

區間取最值

Gorgeous Sequence

區間最值操作往往采用以下辦法

線段樹維護：

• 區間最大值$\text{mx}$
• 區間嚴格次大值$\text{smx}$
• 區間和$\text{sum}$
• 區間最大值個數$\text{cnt}$
• 區間最值懶標記$\text{lazy}$

實現區間最小值操作，考慮u節點維護的區間，進行如下處理

• 當$\text{mx}\le x$，顯然這次修改不會對這個節點維護的區間產生影響，直接退出。
• 當$\text{smx}<x<\text{mx}$，顯然這次修改只會影響到這個區間所有的最大值，由此直接根據最大值個數更新區間和并且更新區間最大值并打上懶標記然后退出即可。
• 當$\text{x}\le \text{smx}$，無法直接更新于是遞歸左右子樹。

時間復雜度請直接查閱吉老師2016年國家集訓隊論文（不太會~

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=998244353; const int N=1000010; // 快讀 template <class T> inline void read(T &res) {res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);if (bo) res = ~res + 1; } struct node {int l,r;ll mx,smx,sum;int cnt;ll lazy; }tree[N<<2]; int n,m; ll a[N]; void pushup(int u) {tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;if(tree[u<<1].mx>tree[u<<1|1].mx){tree[u].mx=tree[u<<1].mx;tree[u].smx=max(tree[u<<1].smx,tree[u<<1|1].mx);tree[u].cnt=tree[u<<1].cnt;}else if(tree[u<<1].mx<tree[u<<1|1].mx){tree[u].mx=tree[u<<1|1].mx;tree[u].smx=max(tree[u<<1|1].smx,tree[u<<1].mx);tree[u].cnt=tree[u<<1|1].cnt;}else {tree[u].mx=tree[u<<1|1].mx;tree[u].smx=max(tree[u<<1].smx,tree[u<<1|1].smx);tree[u].cnt=tree[u<<1].cnt+tree[u<<1|1].cnt;} } void pushlazy(int u,ll x) {if(tree[u].mx<=x) return; tree[u].sum+=(x-tree[u].mx)*tree[u].cnt;tree[u].mx=tree[u].lazy=x; } void pushdown(int u) {if(tree[u].lazy==-1) return;pushlazy(u<<1,tree[u].lazy),pushlazy(u<<1|1,tree[u].lazy);tree[u].lazy=-1; } void build(int u,int l,int r) {tree[u]={l,r,0,-1,0,0,-1};if(l==r) {tree[u].mx=tree[u].sum=a[l];tree[u].cnt=1;return;}int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u); } void modify(int u,int l,int r,ll x) {if(x>=tree[u].mx) return;if(tree[u].l>=l&&tree[u].r<=r&&tree[u].smx<x){pushlazy(u,x);return;}pushdown(u);int mid=tree[u].l+tree[u].r>>1;if(l<=mid) modify(u<<1,l,r,x);if(r>mid) modify(u<<1|1,l,r,x);pushup(u);} ll qmax(int u,int l,int r) {if(tree[u].l>=l&&tree[u].r<=r) return tree[u].mx;int mid=tree[u].r+tree[u].l>>1;pushdown(u);ll v=-1;if(l<=mid) v=max(v,qmax(u<<1,l,r));if(r>mid) v=max(v,qmax(u<<1|1,l,r));pushup(u);return v; } ll qsum(int u,int l,int r) {if(tree[u].l>=l&&tree[u].r<=r) return tree[u].sum;int mid=tree[u].r+tree[u].l>>1;pushdown(u);ll v=0;if(l<=mid) v+=qsum(u<<1,l,r);if(r>mid) v+=qsum(u<<1|1,l,r);pushup(u);return v; } int main() {//IO;int T=1;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);build(1,1,n);while(m--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==0){ll v;scanf("%lld",&v);modify(1,l,r,v);}else if(op==1)printf("%lld\n",qmax(1,l,r));elseprintf("%lld\n",qsum(1,l,r));}}return 0; }

總結

以上是生活随笔為你收集整理的【模板】吉老师线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。