1 条题解
-
0光明正大 LV 4 @ 2019-02-11 14:44:16
#include<bits/stdc++.h>
using namespace std;
int n,m,next=1,a[500050],b[500050],c[500050],ans[500050];
//b[i]表示数字i的位置,c[i]表示在i这个位置增加的个数
struct question{int l,r,d;} qu[500050];
inline int gint()
{ //拙劣的快读(据说还有更快的)。
int ff=1,ee=0;char ss=getchar();
while((ss<'0'||ss>'9')&&ss!='-') ss=getchar();
while((ss>='0'&&ss<='9')||ss=='-')
{if(ss=='-') ff=-1;else ee=(ee<<1)+(ee<<3)+ss-'0';ss=getchar();}
return ee*ff;
}
bool cmp(question x,question y) {return x.r<y.r;}
inline int lowbit(int x) {return x&-x;}
inline void add(int x,int d) {for(;x<=n;x+=lowbit(x)) c[x]+=d;}
inline int ask(int x) {int sum=0;for(;x;x-=lowbit(x)) sum+=c[x];return sum;}
int main()
{
n=gint();for(int i=1;i<=n;i++) a[i]=gint();m=gint();
for(int i=1;i<=m;i++) qu[i].l=gint(),qu[i].r=gint(),qu[i].d=i;
sort(qu+1,qu+m+1,cmp);
for(int i=1;i<=m;i++)
{
for(int j=qu[i-1].r+1;j<=qu[i].r;j++)//增加的部分
{
//如果出现过这个数字,则在之前的位置减去1
if(b[a[j]]) add(b[a[j]],-1);
add(j,1);//现在位置加上1
b[a[j]]=j;//记录a[j]的位置
}
ans[qu[i].d]=ask(qu[i].r)-ask(qu[i].l-1);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
- 1
信息
- 难度
- 6
- 分类
- (无)
- 标签
- 递交数
- 136
- 已通过
- 40
- 通过率
- 29%
- 上传者