题解

1 条题解

  • 0
    @ 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%
上传者