求助,题目是P3919 可持久化线段树
查看原帖
求助,题目是P3919 可持久化线段树
344382
lmrttx楼主2020/11/15 10:23

为什么RE了两个点???

代码:

#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
struct node{
	int l,r,val;
}tree[maxn*10];
int n,m,a[maxn*10],root[maxn*10],top;

int clean_(int id){
	top++;
	tree[top]=tree[id];
	return top;
}

int build(int id,int l,int r){
	top++;
	id=top;
	if(l==r){
		tree[id].val=a[l];
		return top;
	}
	int mid=(l+r)>>1;
	tree[id].l=build(tree[id].l,l,mid);
	tree[id].r=build(tree[id].r,mid+1,r);
	return id;
}

int update(int id,int l,int r,int x,int val){
	id=clean_(id);
	if(l==r)tree[id].val=val;
	else {
		int mid=(l+r)>>1;
		if(x<=mid)
			tree[id].l=update(tree[id].l,l,mid,x,val);
		else tree[id].r=update(tree[id].r,mid+1,r,x,val);
	}
	return id;
}

int query(int id,int l,int r,int x){
	if(l==r)return tree[id].val;
	else {
		int mid=(l+r)>>1;
		if(x<=mid)
		    return query(tree[id].l,l,mid,x);
		else return query(tree[id].r,mid+1,r,x);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)scanf("%d",&a[i]);
	root[0]=build(0,1,n);
	for(register int i=1,root1,op,x;i<=m;i++){
		scanf("%d%d%d",&root1,&op,&x);
		switch (op){
			case 1:
				int y;
				scanf("%d",&y);
				root[i]=update(root[root1],1,n,x,y);
				break;
			case 2:
				printf("%d\n",query(root[root1],1,n,x));
				root[i]=root[root1];
				break;
		}
	}
	return 0;
}
2020/11/15 10:23
加载中...