[Ynoi2016] 镜中的昆虫

Macesuted QWQ LV 10 SU @ 2021-10-2 13:16:49

在我的个人博客中阅读

Statement

维护一个长为 $n$ 的序列 $a_i$ ，有 $m$ 次操作。

将区间 $[l,~r]$ 的值修改为 $x$ 。
询问区间 $[l,~r]$ 出现了多少种不同的数，也就是说同一个数出现多次只算一个。

$1 \le n,~m \le 10^5,~1 \le a_i \le 10^9$

Solution

区间数不同颜色数量问题我们常用的解决方案是记 $pre_i$ 等于最大的 $j$ 满足 $j < i$ 且 $a_j = a_i$ ，数区间内满足 $pre_i < l$ 的数量即为区间内的颜色数量。

此题的难点在于区间修改操作，经分析不难发现当一个区间 $[l,~r]$ 被修改为 $x$ 时 $\forall i \in (l,~r],~pre[i]=i-1$ ，所以在每次操作后我们只需要：

将 $pre_l$ 修改为上一个 $x$ 区间的右端点。
将下一个 $x$ 区间的左端点的 $pre$ 改为 $r$ 。
将 $(l,~r]$ 区间内的所有 $pre_i$ 改为 $i-1$ 。

考虑 3 操作，如果我们在每次修改时将所有 $pre_i \neq i-1$ 的位置找出并修改为 $i-1$ ，全局花在 3 操作上的修改次数为 $O(n+m)$ ：初始时每个 $pre_i$ 可能都不等于 $i-1$ ，而后面的 $m$ 个操作中每个操作最多只会让两个 $pre_i$ 修改得不等于 $i-1$ ，所以全局出现过 $pre_i$ 不等于 $i-1$ 情况的次数为 $O(n+m)$ ，所以花在 3 操作上的修改次数也就为 $O(n+m)$ 。

考虑如何快速找出 $pre_i \neq i-1$ 的位置。容易发现这样的位置一定是一个连续颜色段的开头。因此我们对原序列建一颗 ODT，每次修改 $[l,~r]$ 时，1 操作和 2 操作直接单点修改，3 操作找到 ODT 上被 $[l,~r]$ 包含的所有连续颜色段，将它们全部删除并把它们的左端点的 $pre$ 设为 $i-1$ 即可。

我们可以使用树套树在线维护修改操作并 $O(\log^2 n)$ 解决查询操作。

考虑使用复杂度不变但空间更小的做法。

我们现在是在使用树套树在线解决带修改二维数点问题，考虑再开一维表示数据修改的时间，问题就转变为静态三维数点问题，离线 CDQ 分治即可。

时间复杂度仍旧为 $O(m \log^2 n)$ ，空间复杂度优化到 $O(n+m)$ 。

Code

View on GitHub

Code

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 * @brief
 *      My Solution: https://macesuted.moe/article/h1065
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
inline void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    queue<char> que;
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) que.push(c), c = getch();
    string s;
    s.resize(que.size());
    for (register int i = 0; i < (int)s.size(); i++) s[i] = que.front(), que.pop();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (register int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
inline T read() {
    register T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
inline void write(const T& t) {
    register T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 100005

typedef pair<int, int> pii;

struct Node {
    int tim, pos, pre, delta;
    inline bool operator<(const Node& oth) const { return this->pre < oth.pre; }
};
struct Ask {
    int id, tim, l, r;
    inline bool operator<(const Ask& oth) const { return this->l < oth.l; }
};

vector<Node> nodes;
vector<Ask> asks;

map<int, set<pii> > record;

int a[maxn], pre[maxn];

class ODT {
   private:
    map<pii, int> color;

    void split(int l, int mid, int r) {
        int col = color[(pii){l, mid}] = color[(pii){mid + 1, r}] = color[(pii){l, r}];
        color.erase((pii){l, r});
        record[col].erase((pii){l, r}), record[col].insert((pii){l, mid}), record[col].insert((pii){mid + 1, r});
        return;
    }
    void erase(int tim, int l, int r) {
        int col = color[(pii){l, r}];
        color.erase((pii){l, r});
        set<pii>::iterator i = ++record[col].find((pii){l, r});
        if (i != record[col].end())
            nodes.push_back((Node){tim, i->first, pre[i->first], -1}),
                nodes.push_back((Node){tim, i->first, pre[i->first] = pre[l], +1});
        nodes.push_back((Node){tim, l, pre[l], -1}), nodes.push_back((Node){tim, l, pre[l] = l - 1, +1});
        record[col].erase((pii){l, r});
        return;
    }

   public:
    inline void build(int l, int r, int col) {
        return color[(pii){l, r}] = col, record[col].insert((pii){l, r}), void();
    }
    void insert(int tim, int l, int r, int col) {
        map<pii, int>::iterator t = --color.lower_bound((pii){l + 1, 0});
        if (t->first.first != l) split(t->first.first, l - 1, t->first.second);
        t = --color.lower_bound((pii){r + 1, 0});
        if (t->first.second != r) split(t->first.first, r, t->first.second);
        while (true) {
            map<pii, int>::iterator i = color.lower_bound((pii){l, 0});
            if (i == color.end() || i->first.second > r) break;
            erase(tim, i->first.first, i->first.second);
        }
        record[col].insert((pii){l, r});
        set<pii>::iterator i = record[col].find((pii){l, r}), il = i, ir = i;
        int p = 0;
        if (il != record[col].begin()) p = (--il)->second;
        nodes.push_back((Node){tim, l, pre[l], -1}), nodes.push_back((Node){tim, l, pre[l] = p, +1});
        if (++ir != record[col].end())
            nodes.push_back((Node){tim, ir->first, pre[ir->first], -1}),
                nodes.push_back((Node){tim, ir->first, pre[ir->first] = r, +1});
        color[(pii){l, r}] = col;
        // t = color.find((pii){l, r});
        // if (t != color.begin() && (--t)->second == col) {
        //     int nl = t->first.first;
        //     record[col].erase((pii){t->first.first, t->first.second}), record[col].erase((pii){l, r});
        //     color.erase(t), color.erase((pii){l, r});
        //     record[col].insert((pii){l = nl, r});
        //     color[(pii){l, r}] = col;
        // }
        // t = ++color.find((pii){l, r});
        // if (t != color.end() && t->second == col) {
        //     int nr = t->first.second;
        //     record[col].erase((pii){t->first.first, t->first.second}), record[col].erase((pii){l, r});
        //     color.erase(t), color.erase((pii){l, r});
        //     record[col].insert((pii){l, r = nr});
        //     color[(pii){l, r}] = col;
        // }
        return;
    }
};
class BIT {
   private:
    int tree[maxn];

   public:
    void add(int p, int val) {
        for (register int i = p; i < maxn; i += i & -i) tree[i] += val;
        return;
    }
    int sum(int p) {
        int sum = 0;
        for (register int i = p; i; i -= i & -i) sum += tree[i];
        return sum;
    }
};

ODT tree;
BIT bit;

int answer[maxn];

void CDQ(int nl, int nr, int ql, int qr, int tl, int tr) {
    if (nl > nr || ql > qr) return;
    int tmid = (tl + tr) >> 1, nmid = nl - 1, qmid = ql - 1;
    while (nmid < nr && nodes[nmid + 1].tim <= tmid) nmid++;
    while (qmid < qr && asks[qmid + 1].tim <= tmid) qmid++;
    CDQ(nl, nmid, ql, qmid, tl, tmid), CDQ(nmid + 1, nr, qmid + 1, qr, tmid + 1, tr);
    if (nl > nmid || qmid + 1 > qr) return;
    sort(nodes.begin() + nl, nodes.begin() + nmid + 1), sort(asks.begin() + qmid + 1, asks.begin() + qr + 1);
    int j = nl;
    for (register int i = qmid + 1; i <= qr; i++) {
        while (j <= nmid && asks[i].l > nodes[j].pre) bit.add(nodes[j].pos, nodes[j].delta), j++;
        answer[asks[i].id] += bit.sum(asks[i].r) - bit.sum(asks[i].l - 1);
    }
    for (register int i = nl; i < j; i++) bit.add(nodes[i].pos, -nodes[i].delta);
    return;
}

int main() {
    int n = read<int>(), m = read<int>();
    for (register int i = 1; i <= n; i++) a[i] = read<int>();
    for (register int i = 1, j; i <= n; i = j + 1) {
        j = i;
        while (j < n && a[j + 1] == a[i]) j++;
        tree.build(i, j, a[i]);
        set<pii>::iterator t = record[a[i]].find((pii){i, j});
        int p = 0;
        if (t != record[a[i]].begin()) p = (--t)->second;
        pre[i] = p;
        for (register int k = i + 1; k <= j; k++) pre[k] = k - 1;
    }
    for (register int i = 1; i <= n; i++) nodes.push_back((Node){0, i, pre[i], +1});
    for (register int i = 1; i <= m; i++)
        if (read<int>() == 1) {
            int l = read<int>(), r = read<int>(), col = read<int>();
            tree.insert(i, l, r, col);
        } else {
            int l = read<int>(), r = read<int>();
            asks.push_back((Ask){(int)asks.size(), i, l, r});
        }
    // for (vector<Node>::iterator i = nodes.begin(); i != nodes.end(); i++)
    //     cerr << i->tim << ' ' << i->pos << ' ' << i->pre << ' ' << i->delta << endl;
    CDQ(0, (int)nodes.size() - 1, 0, (int)asks.size() - 1, 0, m);
    for (register int i = 0; i < (int)asks.size(); i++) write(answer[i]), putch('\n');
    return 0;
}

ID: 216
时间: 1500ms
内存: 64MiB
难度: 8
标签: (无)
递交数: 48
已通过: 8
上传者: Macesuted

1 条题解

Statement

Solution

Code

信息

状态

开发

支持

1 条题解

Statement

Solution

Code

[Ynoi2016] 镜中的昆虫

信息

状态

开发

支持

还没有账户？

登录