记录编号	351093	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]采花	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	4.899 s
提交时间	2016-11-16 10:26:16	内存使用	129.99 MiB

//%%%%膜拜想出建两棵树的大神犇们
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 200001
struct node
{
    int ls, rs;
    int cnt;
}ns[MAXN*55+1];
int last = 1;
int build(int l, int r)
{
    if(l > r)return 0;
    int c = last++;
    node &d = ns[c];
    if(l == r)return c;
    else 
    {
        int m = (l+r)>>1;
        d.ls = build(l, m);
        d.rs = build(m+1, r);
    }
    return c;
}
int insert(int base, int l, int r, int v) 
{
    int c = last++;
    ns[c] = ns[base];
    if(l == r && l == v)
    {
        ns[c].cnt++;
        return c;
    }
    else
    {
        int m = (l+r)>>1;
        if(v <= m)ns[c].ls = insert(ns[base].ls, l, m, v);
        else ns[c].rs = insert(ns[base].rs, m+1, r, v);
        ns[c].cnt = ns[ns[c].ls].cnt + ns[ns[c].rs].cnt;
    }
    return c;
}
int query(int pre, int cur, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
        return ns[cur].cnt-ns[pre].cnt;
    int res = 0;
    int m = (l+r)>>1;
    if(ql <= m)res += query(ns[pre].ls, ns[cur].ls, l, m, ql, qr);
    if(m < qr)res += query(ns[pre].rs, ns[cur].rs, m+1, r, ql, qr);
    return res;
}
int root[MAXN*2+2];
int col[MAXN];
int prev1[MAXN];
int prev2[MAXN];
int main()
{
    freopen("flower++.in", "r", stdin);
    freopen("flower++.out", "w", stdout);
    int n, c, q;
    scanf("%d %d %d", &n, &c, &q);
    for(int i = 1; i <= n; i++)
        scanf("%d", col+i);
    root[0] = build(1, n);
    root[n+1] = build(1, n);
    for(int i = 1; i <= n; i++)
    {
        int v = col[i];
        if(prev1[v])
            root[i] = insert(root[i-1], 1, n, prev1[v]);
        else root[i] = root[i-1];
        if(prev2[v])
            root[n+i+1] = insert(root[n+i], 1, n, prev2[v]);
        else root[n+i+1] = root[n+i];
        prev2[v] = prev1[v];
        prev1[v] = i;
    }
    int ans = 0;
    while(q--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        l ^= ans; r ^= ans;
        ans = query(root[l-1], root[r], 1, n, l, r);
        ans -= query(root[n+l], root[n+r+1], 1, n, l, r);
        printf("%d\n", ans);
    }
    return 0;
}