hjt树求调
  • 板块灌水区
  • 楼主Surge_of_Force
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/1/23 07:37
  • 上次更新2023/10/28 11:29:59
查看原帖
hjt树求调
230875
Surge_of_Force楼主2022/1/23 07:37

请问我的 hjt树 可持久化线段树,哪里有问题

#include<bits/stdc++.h>
#define ll long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define int long long
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline int read() {
  int fh = 1, res = 0; char ch = getchar();
  for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
  for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
  res = res * fh;
  return res;
}
inline void write(ll x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,m,top,b[MAX],ans,root[MAX];
struct node{int w,lc,rc;}a[MAX*40];
void build(int l,int r,int &k)
{
	if(!k) k=++top;
	if(l==r){a[k].w=b[l];return ;}
	int mid=(l+r)>>1;
	build(l,mid,a[k].lc);
	build(mid+1,r,a[k].rc);
	return ;
}
void change(int l,int r,int x,int z,int &k)
{
	a[++top]=a[k];k=top;
	if(l==r){a[k].w=z;return ;}
	int mid=(l+r)>>1;
	if(x<=mid) change(l,mid,x,z,a[k].lc);
	if(mid+1<=x) change(mid+1,r,x,z,a[k].rc);
	return ;
}
void ask(int l,int r,int x,int k)
{
	if(l==r){ans=a[k].w;return ;}
	int mid=(l+r)>>1;
	if(x<=mid) ask(l,mid,x,a[k].lc);
	if(mid+1<=x) ask(mid+1,r,x,a[k].rc);
	return ;
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++) b[i]=read();
	build(1,n,root[0]);
	for(int i=1;i<=m;i++)
	{
		int v=read(),opt=read();
		if(opt==1)
		{
			int x=read(),z=read();
			root[i]=top+1;
			change(1,n,x,z,root[v]);
		}
		if(opt==2)
		{
			int x=read();
			ask(1,n,x,root[v]);
			printf("%d\n",ans);
			root[i]=root[v];
		}
	}
	return 0;
}
```cpp
2022/1/23 07:37
加载中...