UESTC1324 卿学姐与公主 分块板子

#include<iostream>

#include<cmath>

using namespace std;

const int maxn=1e5+;

//表示当前数在哪一块里面

int belong[maxn];

//每块的大小

int block;

//一共多少块

int num;

//这个数所在块的左端点

int l[maxn];

//这个数所在块的右端点

int r[maxn];

int n,q;

long long a[maxn],Max[maxn];

void build()

{

    //每块的大小

    block=sqrt(n);

    //处理多少块

    num=n/block;

    //如果有多出来的

    if(n%block)

        num++;

    //更新每块的左右边界

    for(int i=;i<=num;i++)

        l[i]=(i-)*block+,r[i]=i*block;

    r[num]=n;

    //当前数属于哪一块

    for(int i=;i<=n;i++)

        belong[i]=(i-)/block+;

    //更新最大值

    for(int i=;i<=num;i++)

        for(int j=l[i];j<=r[i];j++)

            Max[i]=max(Max[i],a[j]);

}

void update(int x,int y)

{

    a[x]+=y;

    Max[belong[x]]=max(Max[belong[x]],a[x]);

}

long long ask(int x,int y)

{

    long long ans=;

    //如果在同一块里面

    if(belong[x]==belong[y])

    {

        for(int i=x;i<=y;i++)

            ans=max(a[i],ans);

        return ans;

    }

    //如果不在，分开讨论

    for(int i=x;i<=r[belong[x]];i++)

        ans=max(ans,a[i]);

    for(int i=belong[x]+;i<belong[y];i++)

        ans=max(ans,Max[i]);

    for(int i=l[belong[y]];i<=y;i++)

        ans=max(ans,a[i]);

    return ans;

}

int main()

{

    cin>>n>>q;

    build();

    for(int i=;i<=q;i++)

    {

        int op,l,r;

        cin>>op>>l>>r;

        if(op==)

            update(l,r);

        else

            cout<<ask(l,r)<<endl;

    }

 }