题目链接
cogs 2554. [福利]可持久化线段树
题解
没有
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
inline int read () {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c=='-')f=-1; c=getchar();}
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x*f;
}
const int maxn = 100007;
int n,m,a[maxn],tot = 1,root[maxn];
struct Chairman_Tree {
int ch[2],num ;
} ;
Chairman_Tree t[maxn << 4];
#define lc t[x].ch[0]
#define rc t[x].ch[1]
inline void update(int x) { t[x].num = std::max(t[lc].num,t[rc].num); }
void build(int & x,int l,int r) {
x = ++ tot;
if(l == r) {
t[x].num = a[l];return ;
}
int mid = l + r >> 1;
build(lc,l,mid); build(rc,mid+1,r);return ;
update(x) ;
}
int query(int x,int l,int r,int L,int R) {
if(l == r) return t[x].num;
int mid = l + r >>1;
int ret = 0;
if(mid >= L) ret = std::max(ret,query(lc,l,mid,L,R)) ;
if(mid < R) ret = std::max(ret,query(rc,mid+1,r,L,R)) ;
return ret ;
}
void modify(int pre,int &x,int l,int r,int pos,int w) {
t[x = ++tot] = t[pre];
if(l == r) {
t[x].num = w;return ;
}
int mid = l + r >> 1;
if(pos <= mid) modify(t[pre].ch[0],lc,l,mid,pos,w);
else modify(t[pre].ch[1],rc,mid + 1,r,pos,w);
update(x);
}
int main () {
freopen("longterm_segtree.in","r",stdin);
freopen("longterm_segtree.out","w",stdout);
n = read(),m = read(); int tmp = 1;
for(int i = 1;i <= n;++ i) a[i] = read();
build(root[1],1,n);
for(int T,op,a,b,i = 1;i <= m;++ i) {
op = read(),T = read();
if(op == 1) {
a = read(),b = read();
modify(root[T],root[++tmp],1,n,a,b);
}
else {
a = read(),b = read();//,root[i] = root[T];
printf("%d\n",query(root[T],1,n,a,b));
}
}
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/8710463.html
