题目链接：Magician
题面：
MagicianTime Limit: 18000/9000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1911Accepted Submission(s): 549
Problem Description
Fantasy magicians usually gain their ability through one of three usual methods: possessing it as an innate talent, gaining it through study and practice, or receiving it from another being, often a god, spirit, or demon of some sort. Some wizards are depicted as having a special gift which sets them apart from the vast majority of characters in fantasy worlds who are unable to learn magic.Magicians, sorcerers, wizards, magi, and practitioners of magic by other titles have appeared in myths, folktales, and literature throughout recorded history, with fantasy works drawing from this background.In medieval chivalric romance, the wizard often appears as a wise old man and acts as a mentor, with Merlin from the King Arthur stories representing a prime example. Other magicians can appear as villains, hostile to the hero.
Mr. Zstu is a magician, he has many elves like dobby, each of which has a magic power (maybe negative). One day, Mr. Zstu want to test his ability of doing some magic. He made the elves stand in a straight line, from position 1 to position n, and he used two kinds of magic, Change magic and Query Magic, the first is to change an elf’s power, the second is get the maximum sum of beautiful subsequence of a given interval. A beautiful subsequence is a subsequence that all the adjacent pairs of elves in the sequence have a different parity of position. Can you do the same thing as Mr. Zstu ?
Input
The first line is an integer T represent the number of test cases.Each of the test case begins with two integers n, m represent the number of elves and the number of time that Mr. Zstu used his magic.(n,m <= 100000)The next line has n integers represent elves’ magic power, magic power is between -1000000000 and 1000000000.Followed m lines, each line has three integers like type a b describe a magic.If type equals 0, you should output the maximum sum of beautiful subsequence of interval [a,b].(1 <= a <= b <= n)If type equals 1, you should change the magic power of the elf at position a to b.(1 <= a <= n, 1 <= b <= 1e9)
Output
For each 0 type query, output the corresponding answer.
Sample Input
11 110 1 1
Sample Output
1
Author
ZSTU
Source
2015 Multi-University Training Contest 3
解题：
算是比较基础的线段树吧，需要维护的值为，区间不同奇偶性起止的数列的最大值。慢慢练吧，还不是很熟练。
代码：
#include <iostream>#include <cstdio>#include <cstring>#define INF 1e9#define minn -1e18#define LL long longusing namespace std;//节点分别存储其左边界，右边界，奇偶/偶偶/偶奇/奇奇最大值struct node{int l,r;LL OE,EE,EO,OO;}Maxn[400010];int p,v;//存储原数据LL store[100010];LL max(LL a,LL b){return a>b?a:b;}LL min(LL a,LL b){return a<b?a:b;}//向上更新void Pushup(int k){//每个点的值分别为左下区间的相应最值和右下区间最值相加的最大值Maxn[k].EO=max(minn,max(Maxn[k<<1].EO+Maxn[(k<<1)+1].EO,Maxn[k<<1].EE+Maxn[(k<<1)+1].OO));Maxn[k].EO=max(Maxn[k].EO,Maxn[k<<1].EO);Maxn[k].EO=max(Maxn[k].EO,Maxn[(k<<1)+1].EO);Maxn[k].OE=max(minn,max(Maxn[k<<1].OE+Maxn[(k<<1)+1].OE,Maxn[k<<1].OO+Maxn[(k<<1)+1].EE));Maxn[k].OE=max(Maxn[k].OE,Maxn[k<<1].OE);Maxn[k].OE=max(Maxn[k].OE,Maxn[(k<<1)+1].OE);Maxn[k].EE=max(minn,max(Maxn[k<<1].EO+Maxn[(k<<1)+1].EE,Maxn[k<<1].EE+Maxn[(k<<1)+1].OE));Maxn[k].EE=max(Maxn[k].EE,Maxn[k<<1].EE);Maxn[k].EE=max(Maxn[k].EE,Maxn[(k<<1)+1].EE);Maxn[k].OO=max(minn,max(Maxn[k<<1].OE+Maxn[(k<<1)+1].OO,Maxn[k<<1].OO+Maxn[(k<<1)+1].EO));Maxn[k].OO=max(Maxn[k].OO,Maxn[k<<1].OO);Maxn[k].OO=max(Maxn[k].OO,Maxn[(k<<1)+1].OO);}//建树void build(int l,int r,int k){int M;Maxn[k].l=l;Maxn[k].r=r;//为叶子节点if(l==r){//该位置为奇if(l%2){Maxn[k].OO=store[l];Maxn[k].OE=Maxn[k].EE=Maxn[k].EO=minn;}else{Maxn[k].EE=store[l];Maxn[k].OE=Maxn[k].EO=Maxn[k].OO=minn;}return;}//分别向左下区间，和右下区间建树M=(l+r)>>1;build(l,M,k<<1);build(M+1,r,(k<<1)+1);//初始化区间最值Pushup(k);}//询问node query(int l,int r,int k) {node temp,t1,t2;int M; //刚好为该区间，返回该区间最值if (Maxn[k].l==l && Maxn[k].r==r)return Maxn[k]; //否则取该节点对应的中点，，细分M=(Maxn[k].l+Maxn[k].r)>>1; //完全包含在左区间if (r<=M) return query(l,r,k<<1); //完全包含在右区间else if (l>M) return query(l,r,(k<<1)+1); //落在左区间和右区间，取两边相加的最大值else{t1=query(l,M,k<<1);t2=query(M+1,r,(k<<1)+1);temp.EE=max(max(max(t1.EE+t2.OE,t1.EO+t2.EE),t1.EE),t2.EE);temp.EO=max(max(max(t1.EO+t2.EO,t1.EE+t2.OO),t1.EO),t2.EO);temp.OO=max(max(max(t1.OO+t2.EO,t1.OE+t2.OO),t1.OO),t2.OO);temp.OE=max(max(max(t1.OO+t2.EE,t1.OE+t2.OE),t1.OE),t2.OE);return temp;} } //更新操作void update(int o,int L,int R){ int M=L+(R-L)/2; //叶子节点 if(L==R) { if(L%2)Maxn[o].OO=v; elseMaxn[o].EE=v; return; } //继续细分 else { if(p<=M)update(o*2,L,M); elseupdate(o*2+1,M+1,R); //维护区间最值Pushup(o); }}int main(){int t,n,m,a,oper;scanf("%d",&t);while(t–){//读入scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&store[i]);build(1,n,1);for(int i=0;i<m;i++){scanf("%d%d%d",&oper,&a,&v);//查询操作if(oper==0){node temp=query(a,v,1);LL ans=minn;ans=max(ans,temp.OO);ans=max(ans,temp.OE);ans=max(ans,temp.EE);ans=max(ans,temp.EO);printf("%lld\n",ans);}//更新操作，v设置为全局了else{p=a;update(1,1,n);}}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
阳光总在风雨后。只有坚强的忍耐顽强的奋斗，
