Description

萧芸斓是 Z 国的公主, 平时的一大爱好是采花.

今天天气晴朗, 阳光明媚, 公主清晨便去了皇宫中新建的花园采花. 花园足够大, 容纳了 \(n\) 朵花, 花有 \(c\) 种颜色 (用整数 \(1-c\) 表示), 且花是排成一排的, 以便于公主采花. 公主每次采花后会统计采到的花的颜色数, 颜色数越多她会越高兴! 同时, 她有一癖好, 她不允许最后自己采到的花中, 某一颜色的花只有一朵. 为此, 公主每采一朵花, 要么此前 已采到此颜色的花, 要么有相当正确的直觉告诉她, 她必能再次采到此颜色的花. 由于时间 关系, 公主只能走过花园连续的一段进行采花, 便让女仆福涵洁安排行程. 福涵洁综合各种因素拟定了 \(m\) 个行程, 然后一一向你询问公主能采到多少朵花 (她知道你是编程高手, 定能快速给出答案!) , 最后会选择令公主最高兴的行程 (为了拿到更多奖金!) .

Input

第一行四个空格隔开的整数 \(n, c\) 以及 \(m\).

接下来一行 \(n\) 个空格隔开的整数, 每个 数在 \([1, c]\) 间, 第 \(i\) 个数表示第 \(i\) 朵花的颜色.

接下来 \(m\) 行每行两个空格隔开的整数 \(l\) 和 \(r (l \lt r)\), 表示女仆安排的行程为 公主经过第 \(l\) 到第 \(r\) 朵花进行采花.

Output

共 \(m\) 行, 每行一个整数, 第 \(i\) 个数表示公主在女仆的第 \(i\) 个行程中能采到的花的 颜色数.

Sample Input

5 3 5
1 2 2 3 1
1 5
1 2
2 2
2 3
3 5

Sample Output

2
0 0 1 0

Data Range

对于 100% 的数据,\(1 \leq n \leq 10^6, c \leq n, m \leq 10^6\).

Explanation

发现此题就是求区间内数量超过 \(2\) 的数的和是多少.

可以用单调 DP 瞎搞一发 (优化, 带链表), 然后加上奇怪的树状数组.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 1001000;

class BinaryIndexedTree
{
public:
    int n, dat[maxn];
    int lowbit(int x) { return x & (-x); }
    void change(int pos, int val)
    {
        for (int i = pos; i <= n; i += lowbit(i))
            dat[i] += val;
        return ;
    }
    int query(int pos)
    {
        int res = 0;
        for (int i = pos; i > 0; i -= lowbit(i))
            res += dat[i];
        return res;
    }
} bit;

struct query_t { int l, r, pos; };
bool operator < (query_t a, query_t b) {
    return a.l < b.l; }
query_t q[maxn];

int n, c, m;
int arr[maxn];
int next[maxn], begin[maxn]; // structures that maintain a chain.
int res[maxn]; // Final results, must be printed in order.

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &c, &m);
    bit.n = n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    // Building chain
    for (int i = n; i >= 1; i--) {
        next[i] = begin[arr[i]];
        begin[arr[i]] = i;
    }
    // Building BIT tree
    for (int i = 1; i <= c; i++)
        if (next[begin[i]])
            bit.change(next[begin[i]], 1);
    // Reading queries
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].pos = i;
    }
    sort(q + 1, q + 1 + m);
    // Fiddling with the BIT.
    int lef = 1;
    for (int i = 1; i <= m; i++) {
        while (lef < q[i].l) {
            if (next[lef])
                bit.change(next[lef], -1);
            if (next[next[lef]])
                bit.change(next[next[lef]], 1);
            lef += 1;
        }
        res[q[i].pos] = bit.query(q[i].r) - bit.query(q[i].l - 1);
    }
    // Outputting results
    for (int i = 1; i <= m; i++)
        printf("%d\n", res[i]);
    return 0;
}