传送门: 洛谷 P1972 HH 的项链 https://www.luogu.org/problemnew/show/P1972
算法分析: 先排序 (右边界从小到大, 这样就不会对答案产生影响), 然后用树状数组维护从 \([1,j]\) 中不同的数量, 最后用前缀和计算即可
- #include
- #include
- #include
- #define in(x) x=read()
- using namespace std;
- const int maxN=500000;
- struct Q
- {
- int l,r,id;
- }que[maxN+1];
- int tree[maxN+1],n,m,a[maxN+1];
- int ans[maxN+1],flag[maxN+1];
- inline int read(),sum(int);
- inline int lowbit(int x) {return x&(-x);}
- void update(int,int);
- bool comp(Q x,Q y) {return x.r<y.r;}
- int main()
- {
- in(n); for(int i=1;i<=n;i++) in(a[i]); in(m);
- for(int i=1;i<=m;i++)
- {
- in(que[i].l); in(que[i].r);
- que[i].id=i;
- }
- sort(que+1,que+m+1,comp);
- for(int i=1;i<=m;i++)
- {
- for(int j=que[i-1].r+1;j<=que[i].r;j++)
- {
- if(flag[a[j]]) update(flag[a[j]],-1);
- update(j,1); flag[a[j]]=j;
- }
- ans[que[i].id]=sum(que[i].r)-sum(que[i].l-1);
- }
- for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
- return 0;
- }
- void update(int x,int val) {while(x<=n) {tree[x]+=val; x+=lowbit(x);}}
- inline int read()
- {
- char ch=getchar();
- int num=0,f=1;
- while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
- if(ch=='-') {f=-1; ch=getchar();}
- while(ch>='0' && ch<='9')
- {
- num=num*10+ch-'0';
- ch=getchar();
- }
- return num*f;
- }
- inline int sum(int x)
- {
- int ans=0;
- while(x) {ans+=tree[x]; x-=lowbit(x);}
- return ans;
- }
来源: http://www.bubuko.com/infodetail-2949112.html