有时间再修
P3919 【模板】可持久化线段树 1(可持久化数组)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define cs const
#define il inline
#define ri register
#define pc(i) putchar(i)
using namespace std;
il void read(int &as)
{
as=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();as*=f;
}
void wt(int x){if(x<0)x=-x,pc('-');if(x>9) wt(x/10);pc(x%10|48);}
cs int N=1e6+7;
int ro[N*31],sum[N*31],ls[N*31],rs[N*31],tot,n,m,val[N];
#define mid (l+r>>1)
void build(int &cur,cs int l,cs int r)
{
cur=++tot;
if(l==r) return sum[tot]=val[l],void();
build(ls[cur],l,mid),build(rs[cur],mid+1,r);
}
void ins(int &cur,cs int pre,cs int l,cs int r,cs int q,cs int k)
{
cur=++tot;
ls[cur]=ls[pre],rs[cur]=rs[pre],sum[cur]=sum[pre];
if(l==r) return sum[cur]=k,void();
if(q<=mid) ins(ls[cur],ls[pre],l,mid,q,k);
if(q>mid) ins(rs[cur],rs[pre],mid+1,r,q,k);
}
int query(cs int cur,cs int l,cs int r,cs int q)
{
if(l==r) return sum[cur];
if(q<=mid) return query(ls[cur],l,mid,q);
if(q>mid) return query(rs[cur],mid+1,r,q);
}
signed main()
{
read(n),read(m);
for(ri int i=1;i<=n;++i) read(val[i]);
build(ro[0],1,n);
for(ri int i=1,op,x,y,cur;i<=m;++i)
{
read(cur),read(op);
if(op==1) read(x),read(y),ins(ro[i],ro[cur],1,n,x,y);
else read(x),wt(query(ro[cur],1,n,x)),pc('\n'),ro[i]=ro[cur];
}
return 0;
}
P3834 【模板】可持久化线段树 2
点击查看代码
#include<bits/stdc++.h>
#define cs const
#define il inline
#define ri register
#define pc(i) putchar(i)
using namespace std;
il void read(int &as)
{
as=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();as*=f;
}
void wt(int x){if(x<0)x=-x,pc('-');if(x>9) wt(x/10);pc(x%10|48);}
cs int N=2e5+7;
int A[N],lsh[N],tot,ro[N],n,m,Lsh;
struct Seg{int ls,rs,v;}t[N<<5];
#define mid (l+r>>1)
void build(int &cur,cs int l,cs int r)
{
cur=++tot; if(l==r) return;
build(t[tot].ls,l,mid),build(t[tot].rs,mid+1,r);
}
void add(int &cur,cs int pre,cs int l,cs int r,cs int pos)
{
cur=++tot,t[cur]=t[pre],t[cur].v++;
if(l==r) return;
if(pos<=mid) add(t[cur].ls,t[cur].ls,l,mid,pos);
else add(t[cur].rs,t[pre].rs,mid+1,r,pos);
}
int query(cs int nl,cs int nr,cs int l,cs int r,cs int k)
{
if(l==r) return lsh[l];
int x=t[t[nr].ls].v-t[t[nl].ls].v;
if(x>=k) return query(t[nl].ls,t[nr].ls,l,mid,k);
else return query(t[nl].rs,t[nr].rs,mid+1,r,k-x);
}
signed main()
{
read(n),read(m);
for(ri int i=1;i<=n;++i) read(A[i]),lsh[i]=A[i];
sort(lsh+1,lsh+1+n),Lsh=unique(lsh+1,lsh+1+n)-lsh-1;
build(ro[0],1,Lsh);
for(ri int i=1,x;i<=n;++i)
x=lower_bound(lsh+1,lsh+1+Lsh,A[i])-lsh,
add(ro[i],ro[i-1],1,Lsh,x);
for(ri int i=1,l,r,k;i<=m;++i)
read(l),read(r),read(k),wt(query(ro[l-1],ro[r],1,Lsh,k)),pc('\n');
return 0;
}