LA 3938: "Ray, Pass me the dishes!" (선분 수 구간 조회)

"Ray, Pass me the dishes!" (vjudge)
(큰 백서 필기) 또 코드 연습 능력 을 비교 하 는 문제 입 니 다. 시작 할 때 상수 가 너무 커서 O (n * 8727, log * 8289, n * 8727, log * 8289, n) O (n * \ log n * \ log n) O (n * 8727, logn * 8727, logn) 로 썼 고 데이터 범 위 는 5e 5e 5 5e 5, 5e 5, 5e 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.나중에 전부 고 쳐 썼 습 니 다.
그리고 그 안에 많은 디 테 일이 있 는데 평소에 구조 체 가 적어 서 3 일 동안 놀 면서 썼 다.) 많이 배 웠 다.
제목:
길이 n n n 의 정수 서열 을 제시 한 다음 에 m m m 회 질문 을 한다. 매번 질문 에 대해 구간 안의 두 개의 하 표 x, y x, y x, y 는 구간 과 가능 한 한 크 게 한다. 만약 에 다 분해 가 있 으 면 x x x x 는 가능 한 한 작고 다 분해 가 있 으 면 y y y 도 가능 한 한 작다.
생각:
주의 구간 합병 은 세 가지 상황 으로 나 뉜 다.

출발점 과 종점 은 모두 왼쪽 나무 에 있 기 때문에 왼쪽 나무의 매개 변수

와 직접 같다.

출발점 과 종점 은 모두 오른쪽 나무 에 있 기 때문에 오른쪽 나무의 매개 변수

와 직접 같다.

출발점 은 왼쪽 나무 에 있 고 종점 은 오른쪽 나무 에 있 기 때문에 왼쪽 나무의 최대 접미사 에 오른쪽 나무의 최대 접 두 사 를 추가 합 니 다.

갱 점:
아니, 천천히 갈 아.
good luck and have fun!!!
코드 첨부:

#include
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define test(flag,value) cout<
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:
", kase++);
        while(m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            node ans=query(l,r,1,n,1);
            printf("%d %d
", ans.x,ans.y);
        }
    }
}