//题意：询问一段区间的最大子序列的值。 //做法：维护四个值：包含当前区间左端点的最大子区间LM，包含当前区间右端点的最大子区间RM、当前区间的最大子区间M, 当前区间的区间和S //tree[root].maxn=max(tree[root<<1].maxn,max(tree[root<<1|1].maxn,tree[root<<1].rmaxn+tree[root<<1|1].lmaxn));// tree[root].lmaxn=max(tree[root<<1].lmaxn,tree[root<<1].sum+tree[root<<1|1].lmaxn);// tree[root].rmaxn=max(tree[root<<1|1].rmaxn,tree[root<<1|1].sum+tree[root<<1].rmaxn);// tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;#include#include #include #include #include using namespace std;const int N=5e4+5;int n,m,l,r;int L,R,M,S;struct Tree{ int l,r,mid; int sum,lmaxn,rmaxn,maxn;}tree[N<<2];int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}void pushup(int root){ tree[root].maxn=max(tree[root<<1].maxn,max(tree[root<<1|1].maxn,tree[root<<1].rmaxn+tree[root<<1|1].lmaxn)); tree[root].lmaxn=max(tree[root<<1].lmaxn,tree[root<<1].sum+tree[root<<1|1].lmaxn); tree[root].rmaxn=max(tree[root<<1|1].rmaxn,tree[root<<1|1].sum+tree[root<<1].rmaxn); tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;}void build(int root,int l,int r){ tree[root].l=l,tree[root].r=r,tree[root].mid=l+r>>1; if(l==r) { tree[root].sum=tree[root].maxn=tree[root].rmaxn=tree[root].lmaxn=read(); return; } build(root<<1,l,tree[root].mid); build(root<<1|1,tree[root].mid+1,r); pushup(root);}void query(int root,int l,int r,int &L,int &R,int &M,int &S){ if(l<=tree[root].l&&tree[root].r<=r) { L=tree[root].lmaxn, R=tree[root].rmaxn, M=tree[root].maxn, S=tree[root].sum; return; } if(tree[root].mid>=r) { query(root<<1,l,r,L,R,M,S); } else if(tree[root].mid