求问
查看原帖
求问
1367000
Ybll_楼主2025/6/19 15:29

可持久化线段树需要开 nlognn\log n 的数组,此题 n106n\le10^6,我线段树开 30 倍空间为什么会 RE

#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;
il int read()
{
	re int x=0,f=1;
	char c;
	while(!isdigit(c=getchar()))
	{
		if(c=='-')f=-1;
	}
	while(isdigit(c))
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
il void writing(re int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)writing(x/10);
	putchar(x%10+48);
}
il void write(re int x)
{
	writing(x);
	puts(""); 
}
const int N=1000005;
struct node
{
	int ls,rs,sum;
}tree[N*40];
int cnt,root[N],a[N],b[N],lst[N];
il void new_node(re int &x,re int sum)
{
	tree[++cnt]=tree[x];
	tree[cnt].sum+=sum;
	x=cnt;
}
il void build(re int &id,re int l,re int r)
{
	id=++cnt;
	if(l==r)return;
	int mid=l+r>>1;
	build(tree[id].ls,l,mid);
	build(tree[id].rs,mid+1,r);
}
il void update(re int l,re int r,re int &id,re int p,re int sum)
{
	if(l>p||r<p)return;
	new_node(id,sum);
	if(l==r)return;
	re int mid=l+r>>1;
	update(l,mid,tree[id].ls,p,sum);
	update(mid+1,r,tree[id].rs,p,sum);
}
il int query(re int l,re int r,re int id,re int p)
{
	if(r<p)return 0;
	if(l>=p)return tree[id].sum;
	re int mid=l+r>>1;
	return query(l,mid,tree[id].ls,p)+query(mid+1,r,tree[id].rs,p);
}
signed main()
{
	re int n,Q,m;
	cin>>n;
	for(re int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	build(root[0],1,n);
	for(re int i=1;i<=n;i++)
	{
		root[i]=root[i-1];
		if(lst[a[i]]==0)update(1,n,root[i],i,1);
		else
		{
			update(1,n,root[i],lst[a[i]],-1);
			update(1,n,root[i],i,1);
		}
		lst[a[i]]=i;
	}
	Q=read();
	while(Q--)
	{
		re int l=read(),r=read();
		write(query(1,n,root[r],l));
	}
	return 0;
}
2025/6/19 15:29
加载中...