莫队基础+ H的项链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int cnt[N],a[N],ans=0;
struct node{
    int l,r,id;
};
node que[N];
int T,ANS[N];//离线
int n,m;
bool cmp(node a,node b)
{
    if(a.l/T!=b.l/T) return a.l/T<b.l/T;
    if((a.l/T)&1)  return a.r<b.r;//奇偶性优化
//如果l在奇数块，就按照r顺序排序，否则按照r逆序排序。
    return a.r>b.r;
}
void add(int x)
{    //拓展一个数
    if(!cnt[x]) ans++;
    //若这个数还没有过，更新答案
    cnt[x]++;
}
void del(int x)
{
    cnt[x]--;
    if(!cnt[x]) ans--;
    //如果这个数已经消失了,更新答案
}
signed main()
{   cin>>n;
    T=sqrt(n);
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>que[i].l>>que[i].r;que[i].id=i;
    }   
    sort(que+1,que+1+m,cmp);//排序
    int l=1,r=0;//最开始l,r指针对应位置
    for(int i=1;i<=m;i++)
    {   //add是增加下一个位置数
        //del是删除当前位置数
        while(r<que[i].r) add(a[++r]);
        while(r>que[i].r) del(a[r--]);
        while(l>que[i].l) add(a[--l]);
        while(l<que[i].l) del(a[l++]);
        ANS[que[i].id]=ans;//离线操作
    }
    for(int i=1;i<=m;i++)
    cout<<ANS[i]<<endl;

    return 0;
}