After doing Ray a great favor to collect sticks for Ray, Poor Neal becomes very hungry. In return
for Neal’s help, Ray makes a great dinner for Neal. When it is time for dinner, Ray arranges all the
dishes he makes in a single line (actually this line is very long . . ., the dishes are represented by 1, 2, 3
. . .). “You make me work hard and don’t pay me! You refuse to teach me Latin Dance! Now it is time
for you to serve me”, Neal says to himself.
Every dish has its own value represented by an integer whose absolute value is less than 1,000,000,000.
Before having dinner, Neal is wondering about the total value of the dishes he will eat. So he raises
many questions about the values of dishes he would have.
For each question Neal asks, he will first write down an interval [a, b] (inclusive) to represent all
the dishes a, a + 1, . . . , b, where a and b are positive integers, and then asks Ray which sequence of
consecutive dishes in the interval has the most total value. Now Ray needs your help.
Input
The input file contains multiple test cases. For each test case, there are two integers n and m in the
first line (n, m < 500000). n is the number of dishes and m is the number of questions Neal asks.
Then n numbers come in the second line, which are the values of the dishes from left to right. Next
m lines are the questions and each line contains two numbers a, b as described above. Proceed to the
end of the input file.
Output
For each test case, output m lines. Each line contains two numbers, indicating the beginning position
and end position of the sequence. If there are multiple solutions, output the one with the smallest
beginning position. If there are still multiple solutions then, just output the one with the smallest end
position. Please output the result as in the Sample Output.
Sample Input
3 1
1 2 3
1 1
Sample Output
Case 1:
1 1
题意：
给出n个数,m次询问。
每次询问一个区间（x,y），求其中最大子段和对应的区间，保证区间起点尽可能小。
思路：
维护最大区间下标，最大前缀下标，最大后缀下标。
query的时候有3个可能，左区间，右区间，左区间最大后缀加上右区间最大前缀。
务必注意区间顺序，要尽可能靠左。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pa;
const int maxn = 5e5 + 7;
ll sum[maxn];
struct Node
{
int l,r;
int qr,ql;
pa sum;
}t[maxn << 2];
ll get(pa x)
{
return sum[x.second] - sum[x.first - 1];
}
pa Max(pa a,pa b)
{
if(get(a) == get(b)) return a <= b ? a : b;
return get(a) > get(b) ? a : b;
}
void pushup(int i)
{
//sum
t[i].sum = Max(t[i * 2].sum,t[i * 2 + 1].sum);
t[i].sum = Max(t[i].sum,make_pair(t[i * 2].qr,t[i * 2 + 1].ql));
//ql
t[i].ql = t[i * 2].ql;
pa a = make_pair(t[i].l,t[i * 2 + 1].ql);
pa b = make_pair(t[i].l,t[i * 2].ql);
if(get(a) > get(b))
t[i].ql = t[i * 2 + 1].ql;
//qr
t[i].qr = t[i * 2 + 1].qr;
a = make_pair(t[i * 2].qr,t[i].r), b = make_pair(t[i * 2 + 1].qr,t[i].r);
if(get(a) >= get(b))//这里是大于等于，因为开始下标要尽可能小，wa了一天┭┮﹏┭┮
t[i].qr = t[i * 2].qr;
}
void build(int i,int l,int r)
{
t[i].l = l;t[i].r = r;
if(l == r)
{
t[i].ql = l;t[i].qr = r;
t[i].sum = make_pair(l,r);
return;
}
int m = (l + r) >> 1;
build(i * 2,l,m);
build(i * 2 + 1,m + 1,r);
pushup(i);
}
pa query_left(int i,int x,int y)//包含l
{
if(t[i].ql <= y)return make_pair(t[i].l,t[i].ql);
int m = (t[i].l + t[i].r) >> 1;
if(y <= m)return query_left(i * 2,x,y);
pa a = query_left(i * 2 + 1,x,y);
a.first = t[i].l;
pa b = make_pair(t[i].l,t[i * 2].ql);
return Max(a,b);
}
pa query_right(int i,int x,int y)//包含r
{
if(t[i].qr >= x)return make_pair(t[i].qr,t[i].r);
int m = (t[i].l + t[i].r) >> 1;
if(m < x)return query_right(i * 2 + 1,x,y);
pa a = query_right(i * 2,x,y);
a.second = t[i].r;
pa b = make_pair(t[i * 2 + 1].qr,t[i].r);
return Max(a,b);
}
pa query(int i,int x,int y)
{
if(x <= t[i].l && t[i].r <= y)return t[i].sum;
int m = (t[i].l + t[i].r) >> 1;
if(y <= m)return query(i * 2,x,y);
if(x > m)return query(i * 2 + 1,x,y);
ll l = query_right(i * 2,x,y).first;
ll r = query_left(i * 2 + 1,x,y).second;
pa a = make_pair(l,r), b = query(i * 2,x,y), c = query(i * 2 + 1,x,y);
return Max(Max(a,b),c);
}
int main()
{
int n,m;
int kase = 0;
while(~scanf("%d%d",&n,&m) && n && m)
{
for(int i = 1;i <= n;i++)
{
ll x;scanf("%lld",&x);
sum[i] = sum[i - 1] + x;
}
build(1,1,n);
printf("Case %d:\n",++kase);
while(m--)
{
int x,y;scanf("%d%d",&x,&y);
pa ans = query(1,x,y);
printf("%lld %lld\n",ans.first,ans.second);
}
}
return 0;
}