SPOJ DQUERY 练习赛 （主席树数组模板）

询问区间不同的数的个数，强制在线。

信息无法合并，考虑可持久化。

原来一直写树套树，才打了个主席树模板，结果指针跳着跳着就re了，qwq，怎么都调不出来【绝望。。。迫不得已改了个数组。

题目和spoj上应该是一样的（并没有测过，拒绝背锅）

主要还是当个模板，并发誓一天之内拒绝指针！

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define lson(x) tree[x].ls
#define rson(x) tree[x].rs

const int N = ;

struct Tree{
    int l, r, ls, rs, val;
}tree[N*];

int tot, tail, a[N], root[N], mp[N], prev[N];
int n, q, lastans;

int build(int l, int r){
    int num = ++tail;
    tree[num].l = l;
    tree[num].r = r;
    if (l == r)
        return num;
    int mid = (l + r) >> ;
    lson(num) = build(l, mid);
    rson(num) = build(mid+, r);
    return num;
}

void update(int num){
    tree[num].val = tree[lson(num)].val + tree[rson(num)].val;
}

int modify(int cur, int pos){
    int num = ++tail;
    tree[num] = tree[cur];
    if (tree[num].l == tree[num].r){
        tree[num].val++;
        return num;
    }
    int mid = (tree[num].l + tree[num].r) >> ;
    if (pos <= mid)
        lson(num) = modify(lson(num), pos);
    else
        rson(num) = modify(rson(num), pos);
    update(num);
    return num;
}

int query(int num1, int num2, int l, int r){
    if (tree[num1].l == l && tree[num1].r == r){
        return tree[num2].val - tree[num1].val;
    }
    int mid = (tree[num1].l + tree[num1].r) >> ;
    if (r <= mid)
        return query(lson(num1), lson(num2), l, r);
    else if (l > mid)
        return query(rson(num1), rson(num2), l, r);
    else
        return query(lson(num1), lson(num2), l, mid) + query(rson(num1), rson(num2), mid+, r);
}

int main(){
    scanf("%d", &n, &q);
    for (int i=; i<=n; i++){
        scanf("%d", a[i]);
        mp[++tot] = a[i];
    }
    sort(mp+, mp++tot);
    tot = unique(mp+, mp++tot) - mp - ;
    //unique(num,mun+n)返回的是num去重后的尾地址，不真正把重复的元素删除，
    //其实是，该函数把重复的元素一到后面去了，然后依然保存到了原数组中，
    //然后返回去重后最后一个元素的地址，
    for (int i=; i<=n; i++)
        a[i] = lower_bound(mp+, mp++tot, a[i]) - mp;
    root[] = build(, n);
    for (int i=; i<=n; i++){
        root[i] = modify(root[i-], prev[a[i]]);
        prev[a[i]] = i;//前驱 
    }
    scanf("%d", &q);
    while ( q-- ){
        int l, r;
        scanf("%d%d", &l, &r);
        l ^= lastans; r ^= lastans;
        lastans = (r-l+) - query(root[l-], root[r], l, r);
        printf("%d\n", lastans);
    }
    return ;
}

/*
令一个数值的前驱为它上一个出现的位置，则所有前驱在当前区间内的值都
不能被统计。这部分可以通过可持久化线段树查询区间内前驱在当前区间的数的
个数。补集转化即可得到答案。复杂度O(n log n)。
*/