本文主要是介绍Ray, Pass me the dishes! UVA - 1400，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4146
线段树区间合并 要求字典序最小的下标是真的恶心
分别维护左端点向右 右端点向左 整个区间的最大值 以及区间权值和 然后pushup就是套路写法了
在UVAlive上死活过不了 搞了一晚上 对拍了1e7的数据都没问题 很烦
我就CTM的UVAlive 舍友交了遍以前AC的代码也是WA 找了很多网上AC的代码交上全是WA 并且这个OJ上还有很多题都有问题 要么空数据要么题面错误 维护这个OJ的人就是个JB
#include <bits/stdc++.h>
using namespace std;
#define ll long longstruct node
{int l;int r;ll sum;ll left;ll right;ll all;int pl;int pr;int al;int ar;
};struct node0
{int l;int r;ll val;
};node tree[2000010];
int n,q;ll getmax(ll a,ll b)
{if(a>b) return a;else return b;
}bool cmp(node0 n1,node0 n2)
{if(n1.val==n2.val){if(n1.l==n2.l) return n1.r<n2.r;else return n1.l<n2.l;}else return n1.val>n2.val;
}node0 solve(int l1,int r1,ll val1,int l2,int r2,ll val2,int l3,int r3,ll val3)
{node0 tmp[3];tmp[0].l=l1,tmp[0].r=r1,tmp[0].val=val1;tmp[1].l=l2,tmp[1].r=r2,tmp[1].val=val2;tmp[2].l=l3,tmp[2].r=r3,tmp[2].val=val3;sort(tmp,tmp+3,cmp);return tmp[0];
}void pushup(int cur)
{node0 res;tree[cur].sum=tree[2*cur].sum+tree[2*cur+1].sum;if(tree[2*cur].left>=tree[2*cur].sum+tree[2*cur+1].left){tree[cur].left=tree[2*cur].left;tree[cur].pl=tree[2*cur].pl;}else{tree[cur].left=tree[2*cur].sum+tree[2*cur+1].left;tree[cur].pl=tree[2*cur+1].pl;}if(tree[2*cur+1].sum+tree[2*cur].right>=tree[2*cur+1].right){tree[cur].right=tree[2*cur+1].sum+tree[2*cur].right;tree[cur].pr=tree[2*cur].pr;}else{tree[cur].right=tree[2*cur+1].right;tree[cur].pr=tree[2*cur+1].pr;}res=solve(tree[2*cur].al,tree[2*cur].ar,tree[2*cur].all,tree[2*cur].pr,tree[2*cur+1].pl,tree[2*cur].right+tree[2*cur+1].left,tree[2*cur+1].al,tree[2*cur+1].ar,tree[2*cur+1].all);tree[cur].all=res.val;tree[cur].al=res.l;tree[cur].ar=res.r;
}void build(int l,int r,int cur)
{int m;tree[cur].l=l;tree[cur].r=r;if(l==r){scanf("%lld",&tree[cur].sum);tree[cur].left=tree[cur].right=tree[cur].all=tree[cur].sum;tree[cur].pl=tree[cur].pr=tree[cur].al=tree[cur].ar=l;return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}void query(int ppl,int ppr,ll &sum,ll &left,ll &right,ll &all,int &pl,int &pr,int &al,int &ar,int cur)
{node0 res;ll sum1,left1,right1,all1;ll sum2,left2,right2,all2;int pl1,pr1,al1,ar1;int pl2,pr2,al2,ar2;if(ppl<=tree[cur].l&&tree[cur].r<=ppr){sum=tree[cur].sum;left=tree[cur].left;right=tree[cur].right;all=tree[cur].all;pl=tree[cur].pl;pr=tree[cur].pr;al=tree[cur].al;ar=tree[cur].ar;return;}if(ppr<=tree[2*cur].r) query(ppl,ppr,sum,left,right,all,pl,pr,al,ar,2*cur);else if(ppl>=tree[2*cur+1].l) query(ppl,ppr,sum,left,right,all,pl,pr,al,ar,2*cur+1);else{query(ppl,ppr,sum1,left1,right1,all1,pl1,pr1,al1,ar1,2*cur);query(ppl,ppr,sum2,left2,right2,all2,pl2,pr2,al2,ar2,2*cur+1);sum=sum1+sum2;if(left1>=sum1+left2){left=left1;pl=pl1;}else{left=sum1+left2;pl=pl2;}if(sum2+right1>=right2){right=sum2+right1;pr=pr1;}else{right=right2;pr=pr2;}res=solve(al1,ar1,all1,pr1,pl2,right1+left2,al2,ar2,all2);all=res.val;al=res.l;ar=res.r;}
}void show(int cur)
{printf("*%d %d %lld %lld %lld %lld %d %d %d %d*\n",tree[cur].l,tree[cur].r,tree[cur].sum,tree[cur].left,tree[cur].right,tree[cur].all,tree[cur].pl,tree[cur].pr,tree[cur].al,tree[cur].ar);if(tree[cur].l==tree[cur].r) return;show(2*cur);show(2*cur+1);
}int main()
{ll sum,left,right,all;int cas,l,r,pl,pr,al,ar;//freopen("in.txt","r",stdin);//freopen("gou.txt","w",stdout);cas=1;while(scanf("%d%d",&n,&q)!=EOF){memset(tree,0,sizeof(tree));build(1,n,1);//show(1);printf("Case %d:\n",cas++);while(q--){scanf("%d%d",&l,&r);sum=0,left=0,right=0,all=0,pl=0,pr=0,al=0,ar=0;query(l,r,sum,left,right,all,pl,pr,al,ar,1);printf("%d %d\n",al,ar);}}return 0;
}/*
6 100
1 -1 2 -100 1000 1
2 36 100
1 -1 1 -1 1 1
1 54 100
4 5 -7 6
2 4
3 4
1 48 100
4 3 2 -5 4 6 9 8
2 58 100
1 -1 2 1 -2 2 3 -1
1 58 100
-1 -1 -1 3 4 -3 -4 7*/
这篇关于Ray, Pass me the dishes! UVA - 1400的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
