Loading...

洛谷P1972 HH的项链

check评论:0 条 remove_red_eye浏览量:440 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-08-15

GG了qaq,这道题莫队只有$80$了

$80$还是讲一下吧qwq

这道题看到区间数种类,就想到莫队嘛...

code:

#include <bits/stdc++.h>
using namespace std;
struct asks
{
    int l,r,id,ans;
    bool operator<(const asks &q)const
    {
        return (l/500)==(q.l/500)?(r<q.r):((l/500)<(q.l/500));
    }
}e[200010];
int a[500010];
int tong[1000010];
int sum=0;
int n,m;
void add(int aa)
{
    tong[aa]++;
    if(tong[aa]==1)
    {
        sum++;
    }
}
void del(int aa)
{
    tong[aa]--;
    if(tong[aa]==0)
    {
        sum--;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&e[i].l,&e[i].r);
        e[i].id=i;
    }
    int l=1,r=0;
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++)
    {
        while(e[i].r>r)
        {
            r++;
            add(a[r]);
        }
        while(e[i].l<l)
        {
            l--;
            add(a[l]);
        }
        while(e[i].r<r)
        {
            del(a[r]);
            r--;
        }
        while(e[i].l>l)
        {
            del(a[l]);
            l++;
        }
        e[e[i].id].ans=sum;
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",e[i].ans);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名