「题解」洛谷 P3709 大爷的字符串题

题目

P3709 大爷的字符串题

简化题意。

noip 是大爷。

这 sb 题目读懂题是最难的。。。

有一个序列，每次询问一段区间，对这段区间进行如下操作。

每个询问维护一个集合 (S)，从区间中任选一个数 (x)（每个 (x) 只能取一次），将 (x) 往 (S) 里插。

如果集合 (S) 是空的或者集合 (S) 里存在大于等于 (x) 的元素那么 (rp--)。

如果是第二种情况，把 (S) 清空。

最后插入 (x)。

你要使得最后的 (rp) 最大。

每个询问之间互不影响，(rp) 从 (0) 开始。

思路

回滚莫队。手玩样例自己造了样例之后发现答案是区间出现最多次的数的出现次数的相反数。

假如现在有 11223 这个区间。

考虑如何插入，先按顺序插 (1,2,3) 这样子 (rp - 1)，然后插 (1,2)，这样子 (rp - 1)，最后答案就是 (-2)。

发现我们每次插入的都是一个严格递增的数列。

区间出现最多次的数的出现次数就是能构造出最少多少个严格递增的数列。

于是要维护每个数的出现次数，好像从区间里删数的时候不好更新最大值，加数的话很好维护最大值，于是回滚莫队。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 200001

int max(int a, int b) { return a > b ? a : b; }

int n, m, a[MAXN], ans[MAXN], cnt[MAXN];
int sqrn, num[MAXN], cnt_[MAXN];
struct query {
    int x, y, id;
    friend bool operator < (query q1, query q2) {
        if (num[q1.x] != num[q2.x]) return num[q1.x] < num[q2.x];
        return q1.y < q2.y;
    }
}q[MAXN];
struct lsh {
    int w, id;
    friend bool operator < (lsh l1, lsh l2) {
        return l1.w < l2.w;
    }
}c[MAXN];

int main() {
    scanf("%d %d", &n, &m), sqrn = n / sqrt(m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d ", &a[i]);
        num[i] = (i - 1) / sqrn + 1;
        c[i].w = a[i], c[i].id = i;
    }
    std::sort(c + 1, c + n + 1);
    for (int i = 1, now = 0; i <= n; ++i) {
        if (c[i].w != c[i - 1].w) ++now;
        a[c[i].id] = now;
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &q[i].x, &q[i].y);
        q[i].id = i;
    }
    std::sort(q + 1, q + m + 1);
    int l = 0, r = 0, now = 0, lastblock = 0; cnt[0] = 1;
    for (int i = 1; i <= m; ++i) {
        if (num[q[i].x] == num[q[i].y]) {
            int temp = 0;
            for (int j = q[i].x; j <= q[i].y; ++j) {
                ++cnt_[a[j]];
                temp = max(temp, cnt_[a[j]]);
            }
            for (int j = q[i].x; j <= q[i].y; ++j) --cnt_[a[j]];
            ans[q[i].id] = temp;
            continue;
        }
        if (num[q[i].x] != lastblock) {
            int stop = num[q[i].x] * sqrn;
            while (l < stop + 1) --cnt[a[l++]];
            while (r > stop) --cnt[a[r--]];
            now = 0, lastblock = num[q[i].x];
        }
        while (r < q[i].y) {
            ++cnt[a[++r]];
            now = max(cnt[a[r]], now);
        }
        int l_ = l, temp = now;
        while (l_ > q[i].x) {
            ++cnt[a[--l_]];
            temp = max(temp, cnt[a[l_]]);
        }
        while (l_ < l) --cnt[a[l_++]];
        ans[q[i].id] = temp;
    }
    for (int i = 1; i <= m; ++i) printf("%d
", -ans[i]);
    return 0;
}