C-Alice and Bob

题目大意：

m次询问，每次询问一个区间中有多少个连续的的子区间不同数的个数大于等于k
（强制在线）

思路：

首先考虑朴素做法
假设i作为左端点时向右扩展到f[i]这个区间有k个数字
枚举区间[L,R]内 的所有的数字作为左端点
对于[L,R]内的一个点t，

1. f[t]<=R，那么t作为左端点的贡献是(R - f[t] + 1)
2. f[t]>R，那么t作为左端点的贡献是 0

由于f数组是不递减的，我们可以在[L,R]中二分一个位置pos
如果pos作为左端点的贡献是0，那么[pos,R]的所有贡献都是0
对于有贡献的部分可以用公式

这部分可以用前缀和公式O（1）求
f数组和以尺取O（n）求

Code

ll n, a[maxn], m, k, kind;
map<ll, ll> mp;
ll f[maxn], s[maxn];
void add(ll x) {
    mp[a[x]]++;
    if (mp[a[x]] == 1)
        kind++;
}
void del(ll x) {
    mp[a[x]]--;
    if (mp[a[x]] == 0)
        kind--;
}
int main() {
    // ios::sync_with_stdio(false);
    n = read(), m = read(), k = read();
    rep(i, 1, n) a[i] = read();
    int R = 1, L = 1;
    for (L = 1; L <= n; L++) {
        while (kind < k && R <= n)
            add(R), R++;
        if (kind == k)
            f[L] = R - 1;
        else
            f[L] = n + 1;
        del(L);
    }
    rep(i, 1, n) s[i] = s[i - 1] + f[i];
    ll ans = 0;
    while (m--) {
        ll l, r, l1, r1;
        l1 = read(), r1 = read();
        l = min(l1 ^ ans, r1 ^ ans) + 1;
        r = max(l1 ^ ans, r1 ^ ans) + 1;

        int L = 1, R = n, pos;
        while (L <= R) {
            int mid = (L + R) >> 1;
            if (f[mid] > r)
                pos = mid, R = mid - 1;
            else
                L = mid + 1;
        }
        pos--;
        if(pos<l) puts("0"),ans = 0;
        else {
            ll s1 =0 , s2 =0 ;
            s2 = (r+1)*(pos-l+1);
            s1 = s[pos] - s[l-1];
            printf("%lld\n",s2 - s1),ans =  s2 - s1;
        }

    }

    return 0;
}