20230630
P3919 【模板】可持久化线段树 1（可持久化数组）
题目大意
传送门
题目已经说得很清楚了
Solution
一道可持久化线段树的板子题
注意数组开大一点！！！
H_W_Y-Coding
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;//开大一点
int n,m,a[maxn],rt[maxn],tot=0,op,x,val,p;
struct seg{
int val,ch[2];
}tr[maxn<<4];
namespace SGT{
#define lc tr[p].ch[0]
#define rc tr[p].ch[1]
inline void build(int &p,int l=1,int r=n){
p=++tot;
if(l==r){
tr[p].val=a[l];
return ;
}
int mid=l+((r-l)>>1);
build(lc,l,mid);
build(rc,mid+1,r);
}
inline void update(int &p,int pre,int x,int val,int l=1,int r=n){
p=++tot;
tr[p].val=tr[pre].val;
tr[p].ch[0]=tr[pre].ch[0];
tr[p].ch[1]=tr[pre].ch[1];
if(l==r){
tr[p].val=val;
return ;
}
int mid=l+((r-l)>>1);
if(x<=mid) update(lc,tr[pre].ch[0],x,val,l,mid);
else update(rc,tr[pre].ch[1],x,val,mid+1,r);
}
inline int query(int p,int x,int l=1,int r=n){
if(l==r) return tr[p].val;
int mid=l+((r-l)>>1);
if(x<=mid) return query(lc,x,l,mid);
else return query(rc,x,mid+1,r);
}
}
using namespace SGT;
int main(){
/*2023.7.6 H_W_Y P3919 【模板】可持久化线段树 1（可持久化数组） 可持久化线段树*/
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(rt[0]);
for(int i=1;i<=m;i++){
scanf("%d%d",&p,&op);
if(op==1){
scanf("%d%d",&x,&val);
update(rt[i],rt[p],x,val);
}
else{
scanf("%d",&x);
printf("%d\n",query(rt[p],x));
rt[i]=++tot;
tr[rt[i]]=tr[rt[p]];
}
}
return 0;
}
P3834 【模板】可持久化线段树 2
题目大意
传送门
题目已经说得很清楚了
Solution
第二道板子题
H_W_Y-Coding
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,a[maxn],b[maxn],l,r,k,m,rt[maxn],tot=0,len=0;
struct seg{
int val,ch[2];
}tr[maxn<<4];
namespace SGT{
#define lc tr[p].ch[0]
#define rc tr[p].ch[1]
inline void update(int &p,int pre,int x,int l=0,int r=len){
p=++tot;
tr[p].val=tr[pre].val+1;
tr[p].ch[0]=tr[pre].ch[0];
tr[p].ch[1]=tr[pre].ch[1];
if(l==r) return ;
int mid=l+((r-l)>>1);
if(x<=mid) update(lc,tr[pre].ch[0],x,l,mid);
else update(rc,tr[pre].ch[1],x,mid+1,r);
}
inline int query(int p,int pre,int x,int l=0,int r=len){
if(l==r) return l;
int mid=l+((r-l)>>1),cnt=tr[lc].val-tr[tr[pre].ch[0]].val;
if(x<=cnt) return query(lc,tr[pre].ch[0],x,l,mid);
else return query(rc,tr[pre].ch[1],x-cnt,mid+1,r);
}
}
using namespace SGT;
int main(){
/*2023.7.6 H_W_Y P3834 【模板】可持久化线段树 2 可持久化线段树*/
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+n+1);
len=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++) update(rt[i],rt[i-1],lower_bound(b+1,b+len+1,a[i])-b);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",b[query(rt[r],rt[l-1],k)]);
}
return 0;
}