一道挺妙的题,代码难度并不是很大。貌似洛谷春令营讲过这道题然而并没有人去写?(除了 LJC00118 和我 QAQ ...)

我们把区间离线,依次加入序列的每个数并更新以这个数作为右段点的查询的答案。

考虑新加入的数,它能够更新的区间一定满足以下性质。

  • 能够更新的区间不可能超过新加入的数的值上一次出现的位置(如果是第一次加入则为 0 )——再往前排序去重后并不会改变

  • 这个数最多会和值在其 \pm 11 的范围内的数产生贡献——长度超过 10 的极长连续段不需要统计答案。

我们可以把值域在其 \pm 11 范围内的数提取出来,并按照从后往前的顺序重新插入。每次考虑新加入的数对答案产生的贡献(注意是新「加入」而不是新「插入」)。可以发现这是个区间修改状物,可以直接线段树维护,也可以差分到树状数组上。

代码:

// =================================
//   author: memset0
//   date: 2019.03.06 23:20:58
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 1e6 + 20;
int n, m, a[N], tag[N], lst[N], s[11][N], ans[N][11];
std::vector <std::pair <int, int> > vet, qry[N];

void modify(int k, int w, int u) { for (int i = k; i; i -= i & -i) s[u][i] += w; }
void query(int k, int *ans) {
    for (int i = k; i <= n; i += i & -i)
        for (int u = 1; u <= 10; u++) ans[u] += s[u][i];
}

void main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1, l, r; i <= m; i++) read(l), read(r), qry[r].push_back(std::make_pair(l, i));
    for (int u = 1; u <= n; u++) {
        vet.clear();
        for (int i = std::max(1, a[u] - 11); i <= a[u] + 11; i++)
            if (lst[i] && lst[i] > lst[a[u]]) vet.push_back(std::make_pair(lst[i], i));
        vet.push_back(std::make_pair(lst[a[u]], -1));
        vet.push_back(std::make_pair(u, a[u]));
        std::sort(vet.rbegin(), vet.rend());
        tag[a[u]] = 1;
        for (int i = 0; i < vet.size() - 1; i++) {
            int L = 0, R = 0; if (~vet[i].second) tag[vet[i].second] = 1;
            while (tag[a[u] - L - 1]) ++L;
            while (tag[a[u] + R + 1]) ++R;
            int U = L + R + 1;
            if (1 <= L && L <= 10) modify(vet[i].first, -1, L), modify(vet[i + 1].first,  1, L);
            if (1 <= R && R <= 10) modify(vet[i].first, -1, R), modify(vet[i + 1].first,  1, R);
            if (1 <= U && U <= 10) modify(vet[i].first,  1, U), modify(vet[i + 1].first, -1, U);
        }
        tag[a[u]] = 0;
        for (auto it = vet.begin(); it != vet.end(); it++) if (~it->second) tag[it->second] = 0;
        for (auto it = qry[u].begin(); it != qry[u].end(); it++) query(it->first, ans[it->second]);
        lst[a[u]] = u;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= 10; j++) putchar('0' + ans[i][j] % 10);
        putchar('\n');
    }
}

} signed main() { return ringo::main(), 0; }

巧妙的思路 树状数组

已有 3 条评论

  1. Jack_killer Jack_killer

    $orz memset0 tpl$

  2. Spfa Spfa

    Orz memset0tql

如何让 SYZOJ 资瓷多线程并测
上一篇 «
洛谷4208 [JSOI2008]最小生成树计数
» 下一篇