題目大意：給你一個序列a，你有三個操作，0: x y t將a[x,y]和t取min；1：x y求a[x,y]的最大值；2：x y求a[x,y]的sum

題解：首先很明顯就是線段樹裸題，那么考慮如何維護

區間最大值和區間sum很好維護，0操作不好做，那么考慮怎么快速解決0操作

很容易想到維護區間最大值和區間是否全部相同，這是一個做法，但是時間復雜度上卻不正確，但也給了我們一個思路，可以通過維護最大值之類的數來加快操作

一個不行就兩個，于是考慮維護次大值，那么每次0操作就有三種情況，一：比區間最大值還大，那么直接返回；二：大于區間次大值小于區間最大值，那么可以直接修改區間；三：小于區間次大值，那么繼續遞歸下去；

這么做是可行的，在更新區間時因為要維護sum值，于是多維護一個區間max有多少個即可

證明略，時間復雜度o(nlog^2n)——來源：吉老師

代碼：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #define ll long long using namespace std; int T,n,m; ll a[1000001]; class Segtree { public:ll sum[1000001*5],mx[1000001*5],smx[1000001*5],cnt[1000001*5],fl[1000001*5];void pushup(int pos){sum[pos]=sum[pos<<1]+sum[pos<<1|1];if(mx[pos<<1]>mx[pos<<1|1]){mx[pos]=mx[pos<<1];cnt[pos]=cnt[pos<<1];if(mx[pos<<1|1]>smx[pos<<1])smx[pos]=mx[pos<<1|1];else smx[pos]=smx[pos<<1];}if(mx[pos<<1]<mx[pos<<1|1]){mx[pos]=mx[pos<<1|1];cnt[pos]=cnt[pos<<1|1];if(mx[pos<<1]>smx[pos<<1|1])smx[pos]=mx[pos<<1];else smx[pos]=smx[pos<<1|1];}if(mx[pos<<1]==mx[pos<<1|1]){mx[pos]=mx[pos<<1];cnt[pos]=cnt[pos<<1]+cnt[pos<<1|1];if(smx[pos<<1]>smx[pos<<1|1])smx[pos]=smx[pos<<1];else smx[pos]=smx[pos<<1|1];}}void pushdown(int pos){if(fl[pos]>=0){if(mx[pos<<1]>fl[pos]){sum[pos<<1]-=(mx[pos<<1]-fl[pos])*cnt[pos<<1];fl[pos<<1]=mx[pos<<1]=fl[pos];}if(mx[pos<<1|1]>fl[pos]){sum[pos<<1|1]-=(mx[pos<<1|1]-fl[pos])*cnt[pos<<1|1];fl[pos<<1|1]=mx[pos<<1|1]=fl[pos];}fl[pos]=-1;}}void build(int l,int r,int pos){if(l==r){sum[pos]=mx[pos]=a[l];cnt[pos]=1;fl[pos]=smx[pos]=-1;return;}int mid=l+r>>1;build(l,mid,pos<<1);build(mid+1,r,pos<<1|1);pushup(pos);fl[pos]=-1;}void change(int l,int r,int al,int ar,ll v,int pos){int mid=l+r>>1;if(l==al && r==ar){if(v>=mx[pos])return;if(smx[pos]<v && v<mx[pos]){sum[pos]-=(mx[pos]-v)*cnt[pos];fl[pos]=mx[pos]=v;return;}change(l,mid,al,mid,v,pos<<1);change(mid+1,r,mid+1,ar,v,pos<<1|1);pushup(pos);return;}pushdown(pos);if(ar<=mid)change(l,mid,al,ar,v,pos<<1);if(al>mid)change(mid+1,r,al,ar,v,pos<<1|1);if(al<=mid && ar>mid){change(l,mid,al,mid,v,pos<<1);change(mid+1,r,mid+1,ar,v,pos<<1|1);}pushup(pos);}ll askmax(int l,int r,int al,int ar,int pos){if(l==al && r==ar)return mx[pos];int mid=l+r>>1;pushdown(pos);if(ar<=mid)return askmax(l,mid,al,ar,pos<<1);if(al>mid)return askmax(mid+1,r,al,ar,pos<<1|1);if(al<=mid && ar>mid){ll t1=askmax(l,mid,al,mid,pos<<1),t2=askmax(mid+1,r,mid+1,ar,pos<<1|1);return t1>t2?t1:t2;}}ll asksum(int l,int r,int al,int ar,int pos){if(l==al && r==ar)return sum[pos];int mid=l+r>>1;pushdown(pos);if(ar<=mid)return asksum(l,mid,al,ar,pos<<1);if(al>mid)return asksum(mid+1,r,al,ar,pos<<1|1);if(al<=mid && ar>mid)return asksum(l,mid,al,mid,pos<<1)+asksum(mid+1,r,mid+1,ar,pos<<1|1);} }segtree; int main() {scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);segtree.build(1,n,1);int mod,x,y;ll t;while(m--){scanf("%d",&mod);if(mod==0){scanf("%d%d%lld",&x,&y,&t);segtree.change(1,n,x,y,t,1);}if(mod==1){scanf("%d%d",&x,&y);printf("%lld\n",segtree.askmax(1,n,x,y,1));}if(mod==2){scanf("%d%d",&x,&y);printf("%lld\n",segtree.asksum(1,n,x,y,1));}}}return 0; }

?心得：有時候多維護一個次大值能解決很多問題，更多時候在不知道如何證明時間復雜度的情況下往往維護次大值是正確的

轉載于:https://www.cnblogs.com/worcher/p/11561073.html

總結

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

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