2207: 【模板】可持久化线段树1
时间限制: 2 Sec 内存限制: 256 MB提交: 45 解决: 14
[提交][状态][讨论版]
题目描述
你需要维护1个数列的若干版本：
对于给定的数列:a1...an
存在如下两种操作：
1.在vi版本的基础上，修改ax为val
2.查询第vi版本的[l,r]内的最小值。
注：
版本i表示为第i次操作后的数列情况，即改动不影响过去。
版本0为初始版本，若操作为查询，则直接复制一次数列作为当前版本。
输入
第1行2个正整数n,m表示数列长度以及操作次数
第2行n个整数表示初始序列ai
接下来m行，每行格式为vi opti xi yi
表示在vi版本的基础上，执行操作opti
若opti = 1 ,表示修改axi 为 yi(保证1<=xi<=n)
若opti = 2 ，表示查询[xi,yi]内的最小值（保证1<=xi<=yi<=n）
输出
对于所有opti=2的操作
输出1行表示答案。
样例输入
5 10
1 2 3 4 5
0 2 1 3
1 1 2 6
1 1 3 0
3 2 2 5
3 2 1 3
2 1 1 8
6 2 1 3
7 2 1 2
0 1 3 5
9 2 2 5
样例输出
1
0
0
3
6
2
提示
1<=n,m<=5*10^5
0<=vi<i
1<=opti<=2
|xi|,|yi|<=10^9
代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #define MN 500005 4 #define MM 20000005 5 using namespace std; 6 int n,q,v[MN],rt[MN],cnt,T[MM],ls[MM],rs[MM]; 7 void build(int &k,int l,int r){ 8 if(!k) k=++cnt; 9 if(l==r){T[k]=v[l];return;} 10 int mid=(l+r)>>1; 11 build(ls[k],l,mid); build(rs[k],mid+1,r); 12 T[k]=min(T[ls[k]],T[rs[k]]); 13 } 14 void update(int &k,int l,int r,int v,int ad){ 15 ls[++cnt]=ls[k],rs[cnt]=rs[k],k=cnt; 16 if(l==r){T[k]=ad;return;} 17 int mid=(l+r)>>1; 18 if(v<=mid) update(ls[k],l,mid,v,ad); 19 else update(rs[k],mid+1,r,v,ad); 20 T[k]=min(T[ls[k]],T[rs[k]]); 21 } 22 int query(int k,int l,int r,int a,int b){ 23 if(l==a&&r==b) return T[k]; 24 int mid=(l+r)>>1; 25 if(b<=mid) return query(ls[k],l,mid,a,b); 26 if(a>mid) return query(rs[k],mid+1,r,a,b); 27 return min(query(ls[k],l,mid,a,mid),query(rs[k],mid+1,r,mid+1,b)); 28 } 29 int main() 30 { 31 scanf("%d%d",&n,&q); 32 for(int i=1;i<=n;i++) scanf("%d",&v[i]); 33 build(rt[0],1,n); 34 for(int i=1;i<=q;i++){ 35 int lst,opt,x,y; 36 scanf("%d%d%d%d",&lst,&opt,&x,&y); 37 rt[i]=rt[lst]; 38 if(opt==1) update(rt[i],1,n,x,y); 39 else printf("%d ",query(rt[i],1,n,x,y)); 40 } 41 return 0; 42 }