https://www.luogu.org/problemnew/show/P1198

要問區間最大值，肯定是要用線段樹的，不能用樹狀數組。（因為沒有逆元？但是題目求的是最后一段，可以改成類似前綴和啊。不行！插入新元素之后更新的復雜度太高了！）

所以我們就弄一個初始元素是負數的最大值線段樹，每次插入就是把末尾的元素 $update$ ，查詢就是查詢末尾的區間最大值，這樣每次修改/查詢的復雜度是 $O(nlogn)$ 的，非常給力。

所以說我又要到哪里抄一個線段樹模板。

注意這個線段樹是從1開始計數的。

#include<bits/stdc++.h> using namespace std; #define ll long longconst int MAXM=200000; int a[MAXM+5],st[(MAXM<<2)+5];void build(int o,int l,int r){if(l==r) st[o]=a[l];else{int m=l+((r-l)>>1);build(o<<1,l,m);build(o<<1|1,m+1,r);st[o]=max(st[o<<1],st[o<<1|1]);} }void update(int o,int l,int r,int id,int v){if(l==r) st[o]=v;else{int m=l+((r-l)>>1);if(id<=m) update(o<<1,l,m,id,v);else update(o<<1|1,m+1,r,id,v);st[o]=max(st[o<<1],st[o<<1|1]);} }int query(int o,int l,int r,int a,int b){if(r<a||l>b) return -1;if(a<=l&&r<=b) return st[o];int m=l+((r-l)>>1);int p1=query(o<<1,l,m,a,b),p2=query(o<<1|1,m+1,r,a,b);return max(p1,p2); }int M; ll D; int t;char s[5]; int ins;int cntA=0;int main(){t=0;scanf("%d%lld",&M,&D);for(int i=1;i<=M;i++){a[i]=-1;}build(1,1,M);for(int i=1;i<=M;i++){scanf("%s%d",s,&ins);if(s[0]=='Q'){t=query(1,1,M,cntA-ins+1,cntA);printf("%d\n",t);}else{update(1,1,M,cntA+1,((1ll*ins)+t)%D);cntA++;}} }

轉載于:https://www.cnblogs.com/Yinku/p/10318840.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的洛谷 - P1198 - 最大数 - 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

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