RT,86分T两个点,都用了1.5S,卡不过去了。标签写着主席树,不知道是否加强数据后卡了
我的代码如下:
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
return x*f;
}
const int N=5e6+7,M=5e7+7;
int n,m,arr[N],last[N],Root[N];
int cnt;
struct TREE{int ls,rs,sum;}tree[M];
void update(int &NEW,int OLD,int l,int r,int val){//主席树维护last位置上数的数量,所以LR范围取0-n即可
NEW=++cnt;tree[NEW]=tree[OLD];tree[NEW].sum++;
if(l==r) return;
if(val<=mid) update(tree[NEW].ls,tree[OLD].ls,l,mid,val);
if(val>=mid+1) update(tree[NEW].rs,tree[OLD].rs,mid+1,r,val);
}
int query(int x,int y,int l,int r,int idx){
//拿维护每个last值数量的主席树,前缀和出区间权值线段树后,计算区间内有多少last<idx
//我只要减出来的树中维护的值域<idx的部分
if(l>=idx) return 0;
if(r<idx) return tree[y].sum-tree[x].sum;
return query(tree[x].ls,tree[y].ls,l,mid,idx)+query(tree[x].rs,tree[y].rs,mid+1,r,idx);
}
int main()
{
n=read();
for(int i=1;i<=n;i++) arr[i]=read(),update(Root[i],Root[i-1],0,n,last[arr[i]]),last[arr[i]]=i;
m=read();
int x,y;
for(int i=1;i<=m;i++){
x=read(),y=read();
printf("%d\n",query(Root[x-1],Root[y],0,n,x));
}
return 0;
}