【HDOJ 5316】Magician

分类：HDOJ线段树

线段树

【HDOJ 5316】Magician

水水的一道线段树多校居然没看出来。。(其实也是英文水平的缘故看题太长就反感…… 记一大过！

求一个数加和最大的位置(1~n)奇偶相交的数列可以间断线段树区间更新补题的时候在回溯找最大卡了一发WA 后来队友一提返回值直接返回结构体! 恍然大悟。。。太弱辣

代码如下:

using namespace std;typedef struct LinkTree{LL sum[2][2];//0偶 1奇}LinkTree;LinkTree tr[405005];int n,m;LinkTree Joint(LinkTree a,LinkTree b){int i,j;LL t;LinkTree tmp;for(i = 0; i < 2; ++i){for(j = 0; j < 2; ++j){tmp.sum[i][j] = max(a.sum[i][j],b.sum[i][j]);t = max(a.sum[i][0]+b.sum[1][j],a.sum[i][1]+b.sum[0][j]);tmp.sum[i][j] = max(tmp.sum[i][j],t);}}return tmp;}void SetTree(int site,int l,int r){int i,j,x;if(l == r){scanf(“%d”,&x);for(i = 0; i < 2; ++i)for(j = 0; j < 2; ++j)tr[site].sum[i][j] = -Max;tr[site].sum[l&1][r&1] = x;return;}int m = (l+r)>>1;SetTree(site<<1,l,m);SetTree(site<<1|1,m+1,r);tr[site] = Joint(tr[site<<1],tr[site<<1|1]);}void Change(int site,int l,int r,int k,int data){if(l == k && r == k){tr[site].sum[l&1][l&1] = data;return;}int m = (l+r)>>1;if(m >= k)Change(site<<1,l,m,k,data);elseChange(site<<1|1,m+1,r,k,data);tr[site] = Joint(tr[site<<1],tr[site<<1|1]);}LinkTree MAX(int site,int l,int r,int ll,int rr){int i,j;LinkTree tmp;if(l == ll && r == rr){return tr[site];}int m = (l+r)>>1;if(m >= rr) return MAX(site<<1,l,m,ll,rr);else if(m < ll) return MAX(site<<1|1,m+1,r,ll,rr);else{return Joint(MAX(site<<1,l,m,ll,m),MAX(site<<1|1,m+1,r,m+1,rr));}}int main(){int i,j,t,x,b,a;LL mm;LinkTree tmp;scanf(“%d”,&t);while(t–){scanf(“%d %d”,&n,&m);SetTree(1,1,n);while(m–){scanf(“,&x,&a,&b);if(x) Change(1,1,n,a,b);else{tmp = MAX(1,1,n,a,b);mm = -Max;for(i = 0; i < 2; ++i){for(j = 0; j < 2; ++j){mm = max(mm,tmp.sum[i][j]);}}printf(“%lld\n”,mm);}}}return 0;}

上一篇【HDOJ 1016】Prime Ring Problem下一篇【HDOJ 5326】Work

顶0踩0

我知道有一种爱情，叫做与你白头，有一种幸福，叫做和你相伴。

相关文章：

你感兴趣的文章：

标签云：