SPOJ 3693 Maximum Sum(水题，记录区间第一大和第二大数)

#include <iostream>

#include <stdio.h>

#include <algorithm>

#define lson rt<<1,L,mid

#define rson rt<<1|1,mid+1,R

/*

AC

水题

题意：给出n个数，两种操作

    U i x  将第i个数改成x

    Q x y  查询[x,y]中两个数的和的最大值，这两个数不能为同一个

    即只要求该区间第一大和第二大的数，他们的和即为答案

*/

using namespace std;

const int INF=0x3f3f3f3f;

const int maxn=;

int n,m;

struct Node{

    long long m1,m2; //存储该区间第一大的数和第二大的数

}tree[maxn<<];

void pushUp(Node &rt,Node &ls,Node &rs){

    if(ls.m1>rs.m1){

        rt.m1=ls.m1;

        if(ls.m2>=rs.m1)

            rt.m2=ls.m2;

        else

            rt.m2=rs.m1;

    }

    else if(ls.m1==rs.m1){

        rt.m1=rt.m2=ls.m1;

    }

    else{

        rt.m1=rs.m1;

        if(rs.m2>=ls.m1)

            rt.m2=rs.m2;

        else

            rt.m2=ls.m1;

    }

}

void build(int rt,int L,int R){

    if(L==R){

        scanf("%lld",&tree[rt].m1);

        tree[rt].m2=-INF;

        return;

    }

    int mid=(L+R)>>;

    build(lson);

    build(rson);

    pushUp(tree[rt],tree[rt<<],tree[rt<<|]);

}

void update(int rt,int L,int R,int x,long long c){

    if(L==R){

        tree[rt].m1=c;

        tree[rt].m2=-INF;

        return;

    }

    int mid=(L+R)>>;

    if(x<=mid)

        update(lson,x,c);

    else

        update(rson,x,c);

    pushUp(tree[rt],tree[rt<<],tree[rt<<|]);

}

Node query(int rt,int L,int R,int l,int r){

    if(l<=L&&R<=r){

        return tree[rt];

    }

    int mid=(L+R)>>;

    Node tmp,r1,r2;

    if(r<=mid)

        tmp=query(lson,l,r);

    else if(l>mid)

        tmp=query(rson,l,r);

    else{

        r1=query(lson,l,mid);

        r2=query(rson,mid+,r);

        pushUp(tmp,r1,r2);

    }

    return tmp;

}

int main()

{

    char str[];

    int x,y;

    long long v;

    scanf("%d",&n);

    build(,,n);

    scanf("%d",&m);

    for(int i=;i<=m;i++){

        scanf("%s",str);

        if(str[]=='U'){

            scanf("%d%lld",&x,&v);

            update(,,n,x,v);

        }

        else{

            scanf("%d%d",&x,&y);

            Node ans=query(,,n,x,y);

//cout<<ans.m1<<" "<<ans.m2<<endl;

            printf("%lld\n",ans.m1+ans.m2);

        }

    }

    return ;

}

SPOJ 3693 Maximum Sum(水题，记录区间第一大和第二大数)的相关教程结束。