cdoj 1324 卿学姐与公主 线段树裸题

卿学姐与公主

Time Limit: 2000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

某日，百无聊赖的卿学姐打开了某11区的某魔幻游戏

在这个魔幻的游戏里，生活着一个美丽的公主，但现在公主被关押在了魔王的城堡中。

英勇的卿学姐拔出利刃冲向了拯救公主的道路。

走过了荒野，翻越了高山，跨过了大洋，卿学姐来到了魔王的第一道城关。

在这个城关面前的是魔王的精锐部队，这些士兵成一字排开。

卿学姐的武器每次只能攻击一个士兵，并造成一定伤害，卿学姐想知道某时刻从LL到RR这个区间内，从开始到现在累计受伤最严重的士兵受到的伤害。

最开始每个士兵的受到的伤害都是0

Input

第一行两个整数N,QN,Q表示总共有NN个士兵编号从11到NN，和QQ个操作。

接下来QQ行，每行三个整数，首先输入一个tt，如果tt是11，那么输入p,xp,x，表示卿学姐攻击了pp这个位置的士兵，并造成了xx的伤害。如果tt是22，那么输入L,RL,R，表示卿学姐想知道现在[L,R][L,R]闭区间内，受伤最严重的士兵受到的伤害。

1≤N≤1000001≤N≤100000

1≤Q≤1000001≤Q≤100000

1≤p≤N1≤p≤N

1≤x≤1000001≤x≤100000

1≤L≤R≤N1≤L≤R≤N

Output

对于每个询问，回答相应的值

Sample input and output

5 4 2 1 2 1 2 4 1 3 5 2 3 3

0 5

Hint

注意可能会爆int哦

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000007

#define esp 0.00000000001

const int N=2e5+,M=1e6+,inf=1e9;

ll maxx[N<<];

void buildtree(int l,int r,int pos)

{

    if(l==r)

    {

        maxx[pos]=;

        return;

    }

    int mid=(l+r)>>;

    buildtree(l,mid,pos<<);

    buildtree(mid+,r,pos<<|);

    maxx[pos]=max(maxx[pos<<],maxx[pos<<|]);

}

void update(int p,ll c,int l,int r,int pos)

{

    if(l==p&&r==p)

    {

        maxx[pos]+=c;

        return;

    }

    int mid=(l+r)>>;

    if(p>mid)

    update(p,c,mid+,r,pos<<|);

    else

    update(p,c,l,mid,pos<<);

    maxx[pos]=max(maxx[pos<<],maxx[pos<<|]);

}

ll query(int L,int R,int l,int r,int pos)

{

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

    return maxx[pos];

    int mid=(l+r)>>;

    ll ans=;

    if(L<=mid)

    ans=max(ans,query(L,R,l,mid,pos<<));

    if(R>mid)

    ans=max(ans,query(L,R,mid+,r,pos<<|));

    return ans;

}

int main()

{

    int x,y,i,t;

    while(~scanf("%d%d",&x,&t))

    {

        buildtree(,x,);

        for(i=;i<t;i++)

        {

            int flag;

            scanf("%d",&flag);

            if(flag==)

            {

                int p;

                ll c;

                scanf("%d%lld",&p,&c);

                update(p,c,,x,);

            }

            else

            {

                int u,v;

                scanf("%d%d",&u,&v);

                printf("%lld\n",query(u,v,,x,));

            }

        }

    }

    return ;

}

卿学姐与公主

Time Limit: 2000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

某日，百无聊赖的卿学姐打开了某11区的某魔幻游戏

在这个魔幻的游戏里，生活着一个美丽的公主，但现在公主被关押在了魔王的城堡中。

英勇的卿学姐拔出利刃冲向了拯救公主的道路。

走过了荒野，翻越了高山，跨过了大洋，卿学姐来到了魔王的第一道城关。

在这个城关面前的是魔王的精锐部队，这些士兵成一字排开。

卿学姐的武器每次只能攻击一个士兵，并造成一定伤害，卿学姐想知道某时刻从LL到RR这个区间内，从开始到现在累计受伤最严重的士兵受到的伤害。

最开始每个士兵的受到的伤害都是0

Input

第一行两个整数N,QN,Q表示总共有NN个士兵编号从11到NN，和QQ个操作。

接下来QQ行，每行三个整数，首先输入一个tt，如果tt是11，那么输入p,xp,x，表示卿学姐攻击了pp这个位置的士兵，并造成了xx的伤害。如果tt是22，那么输入L,RL,R，表示卿学姐想知道现在[L,R][L,R]闭区间内，受伤最严重的士兵受到的伤害。

1≤N≤1000001≤N≤100000

1≤Q≤1000001≤Q≤100000

1≤p≤N1≤p≤N

1≤x≤1000001≤x≤100000

1≤L≤R≤N1≤L≤R≤N

Output

对于每个询问，回答相应的值

Sample input and output

5 4 2 1 2 1 2 4 1 3 5 2 3 3

0 5

Hint

注意可能会爆int哦