cogs2554 [福利]可持久化线段树

原题链接

每次修改复制一遍就行了。。。

1A！！！

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "longterm_segtree"

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

#define mid ((l+r)>>1)

typedef long long ll;

il int gi(){

    rg int x=0,f=1;rg char ch=getchar();

    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*f;

}

typedef struct node* point;

struct node{

    int max;

    point ls,rs;

    node(int _max){max=_max,ls=rs=NULL;}

};

point root[100001];

int num[10001];

point build(int l,int r){

    point now=new node(19260817);

    if(l==r)now->max=num[l];

    else now->ls=build(l,mid),now->rs=build(mid+1,r),now->max=max(now->ls->max,now->rs->max);

    return now;

}

il int Max(point now,int l,int r,int ll,int rr){

    if(ll<=l&&r<=rr)return now->max;

    if(mid<rr)

	if(mid+1>ll)return max(Max(now->ls,l,mid,ll,rr),Max(now->rs,mid+1,r,ll,rr));

	else return Max(now->rs,mid+1,r,ll,rr);

    else return Max(now->ls,l,mid,ll,rr);

}

il vd Update(point&now,point fr,int l,int r,int pos,int num){

    now=new node(19260817),*now=*fr;

    if(l==r){now->max=num;return;}

    if(pos<=mid)Update(now->ls,fr->ls,l,mid,pos,num);

    else Update(now->rs,fr->rs,mid+1,r,pos,num);

    now->max=max(now->ls->max,now->rs->max);

}

int main(){

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    int n=gi(),q=gi(),cnt=0;

    rep(i,1,n)num[i]=gi();

    root[++cnt]=build(1,n);

    int opt;

    int k,a,b;

    while(q--){

	opt=gi();

	k=gi(),a=gi(),b=gi();

	if(opt==0)printf("%d\n",Max(root[k],1,n,a,b));

	else Update(root[++cnt],root[k],1,n,a,b);

    }

    return 0;

}

好慢mdzz。。。

巴特西

cogs2554 [福利]可持久化线段树

cogs2554 [福利]可持久化线段树

原题链接

最新文章

热门文章