query SPOJ 莫队离线||在线主席树

发表于 | 分类于 | 阅读次数：

区间问题，很快就想到莫队，原来还能用主席树做，奇妙。

题目链接

莫队

莫队算法就不说了，有点含量的就是update函数，注意的是当一个数字增加到个数为1，我们计数++，当一个数字减少到个数为0，计数–。还有update函数，要用void，int会超时

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 1000005;
struct node{
   int l, r, id, answer;
}q[200005];
int col[50005],sum[1000005],cnt,num[1000005];;
int a[maxn];
bool cmp(node a, node b)
{
    return col[a.l] == col[b.l]? (a.r < b.r) :(a.l < b.l);
}

void update(int x, int add)
{
    sum[a[x]] += add;
    if(sum[a[x]] == 1 && add == 1) cnt++;
    if(sum[a[x]] == 0 && add == -1) cnt--;
}

int main()
{
    int n, Q;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
        col[i] = i / (int)sqrt(n) + 1;
    }
    scanf("%d",&Q);
    for(int i = 1; i <= Q; ++i)
    {
        scanf("%d %d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + Q + 1, cmp);
    int l = 1, r = 0;
    for(int i = 1; i <= Q; ++i)
    {
        while(l < q[i].l){update(l,-1) ; l++;}
        while(l > q[i].l){l--; update(l, 1);}
        while(r < q[i].r){ r++; update(r , 1);}
        while(r > q[i].r){update(r, -1); r--;}
        num[q[i].id] = cnt;
    }
    for(int i = 1; i <= Q; ++i)
    {
       printf("%d\n",num[i]);
    }
}

主席树

妈耶，理解原理后敲完一遍就AC，天不亡我！！！！

我们遍历N个元素，如果这个元素之前没有出现过，那么正在建立的这颗线段树就要把对应的这个位置上加1，否则的话如果这个元素之前出现过的最后位置是Index, 那我们就把这个位置的数目-1，在以当前的位置更新目前的这棵线段树。

这样当我们查询L，R区间时，我们就找以rt[R]为根的树，因为每棵线段树都存的是从起点到当前元素的不重复元素个数，所以在rt[R]的树上，我们可以找到任意起点到R这段区间的不重复元素的个数。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <map>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
const int N = 3e4 + 5;

struct node{
    int ls, rs, sum;
}tree[4000005];
const int maxn = 30005;
int a[maxn], rt[maxn];
int tot = 0;
void build(int &o, int l, int r)
{
    o = ++tot;
    tree[o].sum = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(tree[o].ls, l , mid);
    build(tree[o].rs, mid + 1, r);
}

void update(int &o , int last, int l, int r, int pos, int add)
{
    o = ++tot;
    tree[o].ls = tree[last].ls;
    tree[o].rs = tree[last].rs;
    tree[o].sum = tree[last].sum + add;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) update(tree[o].ls, tree[last].ls, l, mid, pos, add);
    else update(tree[o].rs, tree[last].rs, mid + 1, r, pos , add);
}
int sum;
void query(int o, int l, int r, int left, int right)
{
    if(left > r || right < l) return;
    if(left <= l && right >= r)
    {
        sum += tree[o].sum;
        return;
    }
    int mid = (l + r ) >> 1;
    query(tree[o].ls, l, mid, left, right);
    query(tree[o].rs, mid + 1, r, left, right);
}
int main()
{
    int n,Q,l,r;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&Q);
    build(rt[0], 1, n);
    map<int,int>M;
    for(int i = 1; i <= n; ++i)
    {
        if(!M[a[i]])
        {
            update(rt[i], rt[i - 1], 1, n, i, 1);
        }
        else{
            int temp;
            update(rt[i], rt[i - 1], 1, n, M[a[i]], -1);
            update(rt[i], rt[i], 1, n, i, 1);
        }
        M[a[i]] = i;
    }
    while(Q--)
    {
        sum = 0;
        scanf("%d %d",&l, &r);
        query(rt[r], 1, n, l , r);
        cout << sum << '\n';
    }
}