可持久化线段树需要开 nlogn 的数组,此题 n≤106,我线段树开 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;
}