LA3938 :"Ray, Pass me the dishes!" (线段树区间查询)

先呈上原题链接"Ray, Pass me the dishes!" (vjudge)

（大白书刷题笔记）
又是一道比较练代码能力的题目，开始的时候常数写太大了还写成了 $O(n\ast \log n\ast \log n)$O(n∗logn∗logn)，数据范围又是 $5e5$5e5 且多组数据，所以 TLE 了。。。后来全部改写过了。

还有就是里面有许多细节加之平时用结构体少，历时3天 边玩边写 :） 还是学到了不少。

题意：

给出长度为 $n$n 的整数序列，然后 $m$m 次询问，对于每次询问，要求找到区间内的两个下标 $x,y$x,y 使得区间和尽量大，如果有多解， $x$x 尽量小，还有多解，那么 $y$y 也尽量小

思路：

注意区间合并分三种情况：

• 起点和终点都在左子树，所以直接等于左子树的参数
• 起点和终点都在右子树，所以直接等于右子树的参数
• 起点在左子树，终点在右子树，所以用左子树的最大后缀加右子树的最大前缀。

坑点：

无，慢慢磨吧。

good luck and have fun!!!

附上代码：

#include<bits/stdc++.h>
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define test(flag,value) cout<<flag<<":"<<(value)<<endl
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const int MAXN=5e5+5;
const double PI=acos(-1);

int n,m;
struct node
{
    LL sum,max,pre,suf;
    int x,y,px,py,sx,sy;
}sub[MAXN<<2];
void push_up(int rt)
{
    sub[rt].sum=sub[rt<<1].sum+sub[rt<<1|1].sum;

    int nrt;
    if(sub[rt<<1].max>=sub[rt<<1|1].max) nrt=rt<<1;
    else nrt=rt<<1|1;

    sub[rt].max=sub[rt<<1].suf+sub[rt<<1|1].pre;
    sub[rt].x=sub[rt<<1].sx;
    sub[rt].y=sub[rt<<1|1].py;
    if( (sub[rt].max<sub[nrt].max) || (sub[rt].max==sub[nrt].max&&sub[rt].x>sub[nrt].x) || (sub[rt].max==sub[nrt].max&&sub[rt].x==sub[nrt].x&&sub[rt].y>sub[nrt].y) )
    {
        sub[rt].max=sub[nrt].max;
        sub[rt].x=sub[nrt].x;
        sub[rt].y=sub[nrt].y;
    }

    sub[rt].pre=sub[rt<<1].sum+sub[rt<<1|1].pre;
    sub[rt].px=sub[rt<<1].px;
    sub[rt].py=sub[rt<<1|1].py;
    if(sub[rt].pre<=sub[rt<<1].pre)
    {
        sub[rt].pre=sub[rt<<1].pre;
        sub[rt].px=sub[rt<<1].px;
        sub[rt].py=sub[rt<<1].py;
    }

    sub[rt].suf=sub[rt<<1].suf+sub[rt<<1|1].sum;
    sub[rt].sx=sub[rt<<1].sx;
    sub[rt].sy=sub[rt<<1|1].sy;
    if(sub[rt].suf<sub[rt<<1|1].suf)
    {
        sub[rt].suf=sub[rt<<1|1].suf;
        sub[rt].sx=sub[rt<<1|1].sx;
        sub[rt].sy=sub[rt<<1|1].sy;
    }    
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%lld",&sub[rt].sum);
        sub[rt].max=sub[rt].pre=sub[rt].suf=sub[rt].sum;
        sub[rt].x=sub[rt].y=sub[rt].px=sub[rt].py=sub[rt].sx=sub[rt].sy=l;
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    push_up(rt);
}
node query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return sub[rt];
    int m=(l+r)>>1;
    if(m>=R) return query(L,R,l,m,rt<<1);
    if(m<L) return query(L,R,m+1,r,rt<<1|1);
    
    node subl=query(L,R,l,m,rt<<1);
    node subr=query(L,R,m+1,r,rt<<1|1);
    node msub;
    if(subl.max>=subr.max) msub=subl;
    else msub=subr;

    node ret;
    ret.sum=subl.sum+subr.sum;

    ret.max=subl.suf+subr.pre;
    ret.x=subl.sx;
    ret.y=subr.py;

    if((ret.max<msub.max) || (ret.max==msub.max&&ret.x>msub.x) ||(ret.max==msub.max&&ret.x==msub.x&&ret.y>msub.y))
    {
        ret.max=msub.max;
        ret.x=msub.x;
        ret.y=msub.y;
    }

    ret.pre=subl.sum+subr.pre;
    ret.px=subl.px;
    ret.py=subr.py;
    if(ret.pre<=subl.pre)
    {
        ret.pre=subl.pre;
        ret.px=subl.px;
        ret.py=subl.py;
    }

    ret.suf=subl.suf+subr.sum;
    ret.sx=subl.sx;
    ret.sy=subr.sy;
    if(ret.suf<subr.suf)
    {
        ret.suf=subr.suf;
        ret.sx=subr.sx;
        ret.sy=subr.sy;
    }

    return ret;
}
int main(void)
{
    int kase=1;
    while(scanf("%d%d",&n,&m)==2)
    {
        build(1,n,1);
        printf("Case %d:\n", kase++);
        while(m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            node ans=query(l,r,1,n,1);
            printf("%d %d\n", ans.x,ans.y);
        }
    }
}