http://www.lydsy.com/JudgeOnline/problem.php?id=1878

只会莫队做。。。

树状数组

#include
      
       using namespace std;const int N = 1000010;struct query {    int l, r, id;} q[N];int n, m, color;int c[N], tree[N], ans[N], pre[N][2];bool cp(query i, query j) { return i.r < j.r; }namespace bit{    int lowbit(int i) { return i & (-i); }    void update(int pos, int delta)    {        for(int i = pos; i <= n; i += lowbit(i)) tree[i] += delta;    }    int ask(int pos)    {        int ret = 0;        for(int i = pos; i; i -= lowbit(i)) ret += tree[i];        return ret;    }} using namespace bit;int main(){    scanf("%d%d%d", &n, &color, &m);    for(int i = 1; i <= n; ++i) scanf("%d", &c[i]);    for(int i = 1; i <= m; ++i) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;    sort(q + 1, q + m + 1, cp);    int pos = 0;    for(int i = 1; i <= m; ++i)    {        if(pre[c[i]][0]) update(pre[c[i]][0], 1);        if(pre[c[i]][1]) update(pre[c[i]][1], -1);        pre[c[i]][1] = pre[c[i]][0];        pre[c[i]][0] = i;        while(q[pos + 1].r == i)         {            ++pos; ans[q[pos].id] = ask(q[pos].r) - ask(q[pos].l - 1);                }        }    for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);    return 0;}