C-Alice and Bob

題目大意：

m次詢問，每次詢問一個(gè)區(qū)間中有多少個(gè)連續(xù)的的子區(qū)間不同數(shù)的個(gè)數(shù)大于等于k
（強(qiáng)制在線）

思路：

首先考慮樸素做法
假設(shè)i作為左端點(diǎn)時(shí)向右擴(kuò)展到f[i]這個(gè)區(qū)間有k個(gè)數(shù)字
枚舉區(qū)間[L,R]內(nèi) 的所有的數(shù)字作為左端點(diǎn)
對(duì)于[L,R]內(nèi)的一個(gè)點(diǎn)t，

1. f[t]<=R，那么t作為左端點(diǎn)的貢獻(xiàn)是(R - f[t] + 1)
2. f[t]>R，那么t作為左端點(diǎn)的貢獻(xiàn)是 0

由于f數(shù)組是不遞減的，我們可以在[L,R]中二分一個(gè)位置pos
如果pos作為左端點(diǎn)的貢獻(xiàn)是0，那么[pos,R]的所有貢獻(xiàn)都是0
對(duì)于有貢獻(xiàn)的部分可以用公式

這部分可以用前綴和公式O（1）求
f數(shù)組和以尺取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;
}