15:Challenge 11（主席树裸题）

总时间限制:: 10000ms
单个测试点时间限制:: 1000ms
内存限制:: 262144kB

描述

给一个长为N的数列，有M次操作，每次操作是以下两种之一：

（1）修改数列中的一个数

（2）求某次操作后连续一段的和

输入

第一行两个正整数N和M。
第二行N的整数表示这个数列。
接下来M行，每行开头是一个字符，若该字符为'M'，则表示一个修改操作，接下来两个整数x和y，表示把x位置的数修改为y；若该字符为'Q'，则表示一个询问操作，接下来三个整数x、y、z，表示求数列中[x,y]这段区间在第z次操作后的和。

输出

对每一个询问操作单独输出一行，表示答案。

样例输入

样例输出

提示

1<=N<=10^5，1<=M<=10^5，输入保证合法，且所有整数及答案可用带符号32位整型存储。

感觉数据有问题，

调了大半天最后居然是读入优化错了。

但是我前几道题也是用的这个读入优化，，，，

见鬼了。。

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int MAXN=;

const int mod=;

inline void read(int &n)

{

    //char c='+';bool flag=0;n=0;

    //while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();

    //while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();

    scanf("%d",&n);

}

struct node

{

    int ls,rs,sum;

    node(){ls=rs=sum=;}

}tree[MAXN];

int how;

int root[MAXN];

int cz[MAXN];

int ans=;

int tot=;

void update(int k)

{

    tree[k].sum=tree[tree[k].ls].sum+tree[tree[k].rs].sum;

}

void change(int l,int r,int &k,int pre,int pos,int val)

{

    if(!k)    k=++tot;

    tree[k].sum=tree[pre].sum;

    if(l==r)

    {

        tree[k].sum=val;

        return ;

    }

    int mid=(l+r)>>;

    if(pos<=mid)    tree[k].rs=tree[pre].rs,change(l,mid,tree[k].ls,tree[pre].ls,pos,val);

    else tree[k].ls=tree[pre].ls,change(mid+,r,tree[k].rs,tree[pre].rs,pos,val);

    update(k);

}

void query(int l,int r,int k,int wl,int wr)

{

    if(wl<=l&&r<=wr)

    {    ans+=tree[k].sum;

        return ;    }

    int mid=(l+r)>>;

    if(wl<=mid)    query(l,mid,tree[k].ls,wl,wr);

    if(wr>mid)    query(mid+,r,tree[k].rs,wl,wr);

}

int main()

{

    int n,m;

    read(n);read(m);

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

    {

        read(how);

        change(,n,root[],root[],i,how);

    }

    int now=;

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

    {

        cz[i]=now;

        char s[];

        scanf("%s",s);

        if(s[]=='M')// 修改

        {

            now++;cz[i]=now;

            int pos,val;read(pos);read(val);

            change(,n,root[now],root[now-],pos,val);

        }

        else

        {

            int ll,rr,tim;

            read(ll);read(rr);read(tim);

            ans=;

            query(,n,root[cz[tim]],ll,rr);

            printf("%d\n",ans);

        }

    }

    return ;

}

好吧是读入优化没判断负数

巴特西

15:Challenge 11（主席树裸题）

最新文章

热门文章