题目："Ray, Pass me the dishes!"
思路：线段树。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;#define ll long long
#define maxn 500000struct Pair {int x,y;Pair() {}Pair(int x_,int y_) {x=x_,y=y_;}bool operator <(const Pair& other) const {return x<other.x||(x==other.x&&y<other.y)?true:false;}
};int n,m;
ll a[maxn+5]; //前缀和
Pair maxsub[2*maxn+5]; //最大连续和
int maxpre[2*maxn+5],maxsuf[2*maxn+5]; //最大前缀、后缀
int X,Y;Pair cmp(Pair x1,Pair x2) { //比较x1，x2那段更优 ll y1=a[x1.y]-a[x1.x-1],y2=a[x2.y]-a[x2.x-1];if(y1>y2) return x1; //值的大小 if(y1==y2&&x1<x2) return x1; //坐标的大小 return x2;
}void buildtree(int o,int L,int R) {if(L==R) { //叶子节点 maxsub[o]=Pair(L,R);maxpre[o]=maxsuf[o]=L;return ;}int lson=o*2,rson=o*2+1;int mid=(L+R)/2;buildtree(lson,L,mid);buildtree(rson,mid+1,R);if(a[maxpre[lson]]>=a[maxpre[rson]]) maxpre[o]=maxpre[lson];else maxpre[o]=maxpre[rson];if(a[maxsuf[lson]-1]<=a[maxsuf[rson]-1]) maxsuf[o]=maxsuf[lson]; //即a[R]-a[maxsuf[lson]-1]>=a[R]-a[maxsuf[rson]-1]else maxsuf[o]=maxsuf[rson];maxsub[o]=cmp(Pair(maxsuf[lson],maxpre[rson]),cmp(maxsub[lson],maxsub[rson]));
}Pair qpre(int o,int L,int R) { //前缀最大值 if(maxpre[o]<=Y) return Pair(L,maxpre[o]); //最大前缀被所求区间涵盖 int mid=(L+R)/2;int lson=2*o,rson=2*o+1;if(Y<=mid) return qpre(lson,L,mid); //只在左边 Pair x=qpre(rson,mid+1,R);x.x=L;return cmp(x,Pair(L,maxpre[lson]));
}Pair qsuf(int o,int L,int R) { //后缀最大值 if(maxsuf[o]>=X) return Pair(maxsuf[o],R);int mid=(L+R)/2;int lson=2*o,rson=2*o+1;if(X>mid) return qsuf(rson,mid+1,R);Pair x=qsuf(lson,L,mid);x.y=R;return cmp(x,Pair(maxsuf[rson],R));
}Pair query(int o,int L,int R) {if(X<=L&&Y>=R) return maxsub[o];int lson=o*2,rson=o*2+1;int mid=(L+R)/2;if(Y<=mid) return query(lson,L,mid); //全左 if(X>mid) return query(rson,mid+1,R); //全右 Pair b=Pair(qsuf(lson,L,mid).x,qpre(rson,mid+1,R).y); //左右各一半 Pair c=query(lson,L,mid),d=query(rson,mid+1,R); //有时，完全在一边的一段比左右各一半的一段更大 return cmp(b,cmp(c,d));
}int main() {int T=0;while(~scanf("%d%d",&n,&m)) {for(int i=1; i<=n; i++) {int x;scanf("%d",&x);a[i]=a[i-1]+x;}buildtree(1,1,n);printf("Case %d:\n",++T);for(int i=1; i<=m; i++) {scanf("%d%d",&X,&Y);if(X>Y) swap(X,Y);Pair ans=query(1,1,n);printf("%d %d\n",ans.x,ans.y);}}return 0;
}