題目鏈接：點(diǎn)擊查看

題目大意：給出 1 ~ n 的區(qū)間以及?m 次操作，每次操作分為三種形式：

0 l r val：對于區(qū)間 [ l , r ] ，a[ i ] = min ( a[ i ] , val )

1 l r：輸出區(qū)間 [ l , r ] 的最大值

2 l r：輸出區(qū)間 [ l , r ] 的區(qū)間和

題目分析：吉司機(jī)線段樹的模板題，挺冷門的一個數(shù)據(jù)結(jié)構(gòu)好像，但是鑒于比較簡單就學(xué)了一波，可以實現(xiàn)線段樹區(qū)間內(nèi)滿足條件的部分修改，時間復(fù)雜度為 m * logn * logn，具體實現(xiàn)是線段樹的每個節(jié)點(diǎn)除了維護(hù)最大值外額外再維護(hù)一個次大值，對于每次更新，分為三種情況：

val >= 最大值：無需更新

最大值 >= val > 次大值：將所有的最大值改為次大值

次大值 >= val：向下繼續(xù)遞歸

證明我也不太會，光知道這樣的時間復(fù)雜度很低就好了，具體代碼實現(xiàn)也主要是pushup和pushdown的定義

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;struct Node {int l,r,num,mmax,se_mmax;//num:最大值的個數(shù),mmax:區(qū)間最大值,se_mmax:次大值 LL sum;//區(qū)間和 }tree[N<<2];void pushup(int k) {tree[k].num=0;tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);tree[k].se_mmax=max(tree[k<<1].se_mmax,tree[k<<1|1].se_mmax);if(tree[k].mmax==tree[k<<1].mmax)tree[k].num+=tree[k<<1].num;elsetree[k].se_mmax=max(tree[k].se_mmax,tree[k<<1].mmax);if(tree[k].mmax==tree[k<<1|1].mmax)tree[k].num+=tree[k<<1|1].num;elsetree[k].se_mmax=max(tree[k].se_mmax,tree[k<<1|1].mmax); }void pushdown(int k) {if(tree[k].mmax<tree[k<<1].mmax){tree[k<<1].sum-=1LL*tree[k<<1].num*(tree[k<<1].mmax-tree[k].mmax);tree[k<<1].mmax=tree[k].mmax;}if(tree[k].mmax<tree[k<<1|1].mmax){tree[k<<1|1].sum-=1LL*tree[k<<1|1].num*(tree[k<<1|1].mmax-tree[k].mmax);tree[k<<1|1].mmax=tree[k].mmax;} }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){scanf("%d",&tree[k].mmax);tree[k].sum=tree[k].mmax;tree[k].se_mmax=-1;tree[k].num=1;return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int l,int r,int val) {if(tree[k].mmax<=val)return;if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r&&val>tree[k].se_mmax){tree[k].sum-=1LL*tree[k].num*(tree[k].mmax-val);tree[k].mmax=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }int query_max(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l)return -inf;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].mmax;pushdown(k);return max(query_max(k<<1,l,r),query_max(k<<1|1,l,r)); }LL query_sum(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].sum;pushdown(k);return query_sum(k<<1,l,r)+query_sum(k<<1|1,l,r); }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,m;scanf("%d%d",&n,&m);build(1,1,n);while(m--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==0){int val;scanf("%d",&val);update(1,l,r,val);}else if(op==1)printf("%d\n",query_max(1,l,r));elseprintf("%lld\n",query_sum(1,l,r));}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 5306 Gorgeous Sequence(吉司机线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。