[牛客练习赛73] D-离别 题解

题意就不说了，中文题面，我觉得题目应该讲的够清楚了。

先分享一下我做这道题的辛酸路程吧
看完这道题后，我的第一想法就是先预处理出以每个点作为左端点然后得到一个右端点的范围使得它们构成的区间是合法的。以这一步好像是和出题人题解里说的是一样的。然后对于一个询问要如何快速的回答呢？起初我脑补了一个主席树来求区间内大于k的数的和之类的东西，但是发现好像需要分类讨论，然后想了想那样写起来巨麻烦就把这个想法叉了（也许是我太菜了，没想到好的处理方法QAQ）。
接下来的一个小时时间里我还陆续脑补了几个假算法但是也都被我自己叉了...然后又看了一遍题目发现好像并没有要求强制在线？而我却一直在想用一个在线做法去做...我真是个XX。那如果离线做的话我可以用莫队，然后想了想再结合我最初的那个想法好像就可以了？ 赶紧火速敲完，对着样例调了调几个小bug就一发AC了。
结束后我翻了翻大家这题的ac代码貌似大部分人也是离线搞的，但是复杂度好像是。我果然还是太菜了...只能想到。（但是跑的好像不慢？

具体做法

先两次滑动窗口预处理出对于每个下标i的一个范围使得区间中出现最多的数正好出现k次。也就是对于每个以i为左端点，以范围内为下标的这些点作为右端点，它们构成的区间是合法的。
然后离线处理所有询问，这里都是莫队的套路做法。关键点在于区间端点+1 -1发生变化时，我要如何快速的实时去维护答案。现在假设当前区间为,此时区间左端点往左移动1个单位，新移动进来下标为i的一个数，那么当前这个区间的答案总数就 = 原来区间的答案 + 以下标i为左端点的合法区间个数。而这些新的合法区间个数可以O(1)的算出来，因为我们已经知道了i的合法范围是，那么只需要计算出范围内落在区间内数的个数(也就是两个区间求交 可以O(1)完成)就是新区间的答案需要再加上的值了。而左端点删除一个数也可以同样类比,其实就是把'+'改成'-'就好了。那如果是右端点发生变化呢？ 那么对序列直接反过来预处理一遍就好了，对于每个i同样两次滑动窗口预处理得到以它作为右端点的一个合法范围，然后类比左端点的做法就好了。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define X first
#define Y second
#define pb push_back
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pii pair<int,int>
#define New_Time srand((unsigned)time(NULL))
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
int head[2000010], Edge_Num;
struct Edge { int to, next; ll w; }e[4000010];
inline void ade(int x, int y, ll w) { e[++Edge_Num] = { y,head[x],w }; head[x] = Edge_Num; }
inline void G_init(int n) { memset(head, 0, sizeof(int) * (n + 100)); Edge_Num = 0; }
int dir[8][2] = { {-1,0},{0,-1},{-1,-1},{1,-1},{1,0},{0,1},{1,1},{-1,1} };
const long double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
inline ll rd() {
    ll x = 0; bool f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')f = 0; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return f ? x : -x;
}
const double eps = 1e-8;
const ll mod = 20000311;
const int M = 1e6 + 10;
const int N = 1e6 + 10;
int cnt[N];
int lim, num;
int a[N];
struct MM {
    int l, r;
}L[N], R[N];
void add(int i) {
    if (cnt[a[i]] == lim - 1)++num;
    ++cnt[a[i]];
}
void sub(int i) {
    if (cnt[a[i]] == lim)--num;
    --cnt[a[i]];
}
int S;
struct MMm {
    int id, l, r;
    bool friend operator<(const MMm& m1, const MMm& m2) {
        int b1 = m1.l / S, b2 = m2.l / S;
        return (b1 ^ b2) ? b1 < b2 : ((b1 & 1) ? m1.r<m2.r : m1.r>m2.r);
    }
}qr[N];
ll ans[N];
ll now;
int nl, nr;//[nl,nr]为当前区间，now当前区间的答案
void ad(int x) {
    if (x == nr) {
        ll pl = max(nl, R[x].l);
        if (R[x].l && R[x].r >= pl) {
            now += R[x].r - pl + 1;
        }
    }
    else {
        ll pr = min(nr, L[x].r);
        if (L[x].l && L[x].l <= pr) {
            now += pr - L[x].l + 1;
        }
    }
}
void de(int x) {
    if (x == nr) {
        ll pl = max(nl, R[x].l);
        if (R[x].l && R[x].r >= pl) {
            now -= R[x].r - pl + 1;
        }
    }
    else {
        ll pr = min(nr, L[x].r);
        if (L[x].l && L[x].l <= pr) {
            now -= pr - L[x].l + 1;
        }
    }
}
void move(int tl, int tr) {//移动到[tl,tr]
    //要注意先加再删,否则删一个不存在的数会出错
    while (nr < tr) ++nr, ad(nr);
    while (nl > tl)--nl, ad(nl);
    while (nr > tr)de(nr), nr--;
    while (nl < tl)de(nl), nl++;
}
void solve() {
    int n = rd(), q = rd(), k = rd();
    S = n / sqrt(q) + 1;
    for (int i = 1; i <= n; i++)a[i] = rd();
    for (int i = 1; i <= q; i++) {
        qr[i].id = i;
        qr[i].l = rd(), qr[i].r = rd();
    }
    lim = k, num = 0;
    for (int l = 1, r = 0; l <= n; l++) {
        while (num == 0 && r + 1 <= n) {
            ++r;
            add(r);
        }
        if (num)L[l].l = r;
        sub(l);
    }
    lim = k + 1, num = 0;
    for (int l = 1, r = 0; l <= n; l++) {
        while (num == 0 && r + 1 <= n) {
            ++r;
            add(r);
        }
        if (L[l].l) {
            if (num)L[l].r = r - 1;
            else L[l].r = r;
        }
        sub(l);
    }

    lim = k, num = 0;
    for (int r = n, l = n + 1; r >= 1; r--) {
        while (num == 0 && l - 1 >= 1) {
            --l;
            add(l);
        }
        if (num)R[r].r = l;
        sub(r);
    }
    lim = k + 1, num = 0;
    for (int r = n, l = n + 1; r >= 1; r--) {
        while (num == 0 && l - 1 >= 1) {
            --l;
            add(l);
        }
        if (R[r].r) {
            if (num)R[r].l = l + 1;
            else R[r].l = l;
        }
        sub(r);
    }
    sort(qr + 1, qr + 1 + q);
    nl = 1, nr = 0, now = 0;
    for (int i = 1; i <= q; i++) {
        move(qr[i].l, qr[i].r);
        ans[qr[i].id] = now;
    }
    for (int i = 1; i <= q; i++)printf("%lld\n", ans[i]);
}
int main() {
    int T = 1;
    //T = rd();
    while (T--)solve();

}