主席树求调一下

P3919 【模板】可持久化线段树 1(可持久化数组)

@[Vsinger_洛天依](/user/1000298) node 节点中你定义了 $l$ 和 $r$,但是你 build 中并没有给他们赋值 insert 中 qwq 是新建的版本,但为什么你在给 q 节点进行更新? 而且 qwq 节点应该继承 q 节点的儿子等信息,直接 t[qwq]=t[q] 多好() 修改后的代码(不晓得为什么MLE了一个) ```cpp #include<bits/stdc++.h> #define lc t[q].ls #define rc t[q].rs #define mid ((l+r)/2) #define int long long using namespace std; const int N=1e6+5; int n,m,a[N*30],tot,root[N*30]; inline int read(){ int f=1,x=0;char ch; while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-')f=-1;}; while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}; return f*x; } struct node{ int l,r,ls,rs; int lazy,dat; }t[N*30]; void build(int &q, int l, int r){ q=++tot; t[q].l=l; t[q].r=r; if(l==r){ t[q].dat=a[l]; return; } build(lc,l,mid); build(rc,mid+1,r); } inline void insert(int &qwq,int q,int l,int r,int i,int val){ qwq=++tot; t[qwq]=t[q]; t[qwq].l=l;t[qwq].r=r; if(l==r){ t[qwq].dat=val; return; } if(i<=mid) insert(t[qwq].ls,lc,l,mid,i,val); else insert(t[qwq].rs,rc,mid+1,r,i,val); t[qwq].dat=t[t[qwq].ls].dat+t[t[qwq].rs].dat; } inline int ask(int q,int l,int r){ if(!q) return 0; if(t[q].l>r||t[q].r<l) return 0; if(t[q].l>=l&&t[q].r<=r) return t[q].dat; return ask(lc,l,r)+ask(rc,l,r); } signed main(){ // freopen("1.in","r",stdin); n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(); build(root[0],1,n); for(int i=1;i<=m;i++){ int qwq=read(),opt=read(),x=read(); if(opt==1){ int y=read(); insert(root[i],root[qwq],1,n,x,y); } else{ cout<<ask(root[qwq],x,x)<<endl; root[i]=root[qwq]; } } } ```
by daitouzero @ 2024-01-28 22:17:29


哦找到为嘛MLE了,数组开大了,把 node 里面的 lazy 删掉就行了
by daitouzero @ 2024-01-28 22:22:44


|