P4690 [Ynoi Easy Round 2016] 镜中的昆虫 题解

题目大意

给定长度为 \(n\) 的颜色序列 \(a\)，需要维护两种操作：

• 给定 \(l,r,c\)，将区间 \([l,r]\) 内的颜色全部覆盖为 \(c\)；
• 给定 \(l,r\)，查询区间 \([l,r]\) 内不同颜色的种类数；

题解

首先考虑单修怎么做。

见cdq分治。

接下来考虑区修怎么做。根据区间颜色覆盖的均摊结论，我们可以得到：

对一个长度为 \(n\) 的颜色序列进行 \(m\) 次区间赋值，pre 数组的改变次数为 \(O(n+m)\)（不计常数）。

每次将一个颜色段 \([l,r]\) 删除，最多会改变两个位置的 \(pre\)：左端点 \(l\) 和右侧第一个同色点 \(nxt[r]\)。每次执行区间覆盖 \([l,r]\) 时最多插入 \(3\) 个颜色段，插入时会修改 \(l\) 和 \(nxt[r]\) 两个位置的 pre，每个颜色段最多被删除一次，因此修改操作不超过 \(2(n+3m)+2m=10\times MAXN=O(n+m)\) 个。

我们使用 ODT 维护颜色段，在 assign() 内产生对 pre 的修改操作，并按照时间顺序和查询操作混合送入 cdq 中处理即可。

卡常

lxl 毒瘤，64M 内存限制。。。

主要针对 cdq 中操作序列的传递进行优化。直接传 vector<Op> & 肯定不行。那每次传 \([ql,qr]\) 表示操作序列为 op[ql:qr]，可以减少栈的消耗。这就需要使用辅助数组存储拆分的结果。为了进一步减少内存，辅助数组不能定义为 Op 类型，只存储下标即可。

具体的，我们定义两个数组 swp[i] 和 tmp[i]，分别用来记录操作序列的实际顺序和拆分结果。初始时 swp[i]=i，cdq 内我们将分到左侧区间的操作的 swp 先装入 tmp，右侧区间的操作排列在其后面，然后从 tmp 复制回 swp 即可。

空间 \(63.48\text{MB}\)，时间 \(8.58s\) 。

AC 代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#define cint const int &
using namespace std;
const int N = 1E5 + 10;

struct Query {
    int tp, l, r, x;
    inline Query(cint _tp = 0, cint _l = 0, cint _r = 0, cint _x = 0) :
        tp(_tp), l(_l), r(_r), x(_x) {}
};

struct Op {
    int tp, l, r, v, w, id;
};

struct Node {
    int l, r, c;
    inline Node(int _l, int _r, int _c) :
        l(_l), r(_r), c(_c) {}
    inline bool operator<(const Node &b) const {
        return l < b.l;
    }
};

int n, m;
int a[N], pre[N], ans[N];
Query q[N];
Op op[11 * N];
int swp[11 * N], tmp[11 * N], opCnt;

int num[2 * N], nn;

void lisanhua() {
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
    }
    for(int i = 1; i <= m; i++) {
        if(q[i].tp == 1) q[i].x = lower_bound(num + 1, num + 1 + nn, q[i].x) - num;
    }
}

void add_modify(cint p, cint v) {
    if(p > n || p < 1) return;
    if(v == pre[p]) return;
    op[++opCnt] = {1, p, p, pre[p], -1, 0};
    op[++opCnt] = {1, p, p, pre[p] = v, 1, 0};
}

void add_query(cint l, cint r, cint id) {
    op[++opCnt] = {0, l, r, l - 1, 1, id};
}

namespace odt {

    set<Node> pos[2 * N], tr;

    int get_pre(cint x) {
        if(x > n || x < 1) return -1;
        set<Node>::iterator it = --tr.upper_bound({x, 0, 0});
        if(x > it->l) return x - 1;
        it = --pos[it->c].find(*it);
        return it->r;
    }

    int get_suc(cint x) {
        if(x > n || x < 1) return -1;
        set<Node>::iterator it = --tr.upper_bound({x, 0, 0});
        if(x < it->r) return x + 1;
        it = ++pos[it->c].find(*it);
        return it->l;
    }

    void build() {
        for(int i = 1; i <= nn; i++) pos[i].insert({0, 0, i});
        for(int i = 1; i <= nn; i++) pos[i].insert({n + 1, n + 1, i});
        tr.insert({0, 0, 0});
        tr.insert({n + 1, n + 1, 0});
        for(int i = 2, j = 1; i <= n + 1; i++) {
            if(a[i] != a[j]) {
                tr.insert({j, i - 1, a[i - 1]});
                pos[a[i - 1]].insert({j, i - 1, a[i - 1]});
                j = i;
            }
        }
    }

    set<Node>::iterator split(cint x) {
        set<Node>::iterator it = --tr.upper_bound({x, 0, 0});
        if(it->l == x) return it;
        int l = it->l, r = it->r, c = it->c;
        pos[c].erase(*it);
        tr.erase(it);
        pos[c].insert({l, x - 1, c});
        pos[c].insert({x, r, c});
        tr.insert({l, x - 1, c});
        tr.insert({x, r, c});
        return tr.find({x, r, c});
    }

    void assign(cint l, cint r, cint c) {
        set<Node>::iterator itr = split(r + 1), itl = split(l);
        for(set<Node>::iterator it = itl; ++it != itr; ) {
            add_modify(it->l, it->l - 1);
        }
        vector<int> suc;
        for(set<Node>::iterator it = itl; it != itr; ++it) {
            int tmp = get_suc(it->r);
            if(tmp > r) suc.push_back(tmp);
        }
        for(set<Node>::iterator it = itl; it != itr; ++it) {
            pos[it->c].erase(*it);
        }
        pos[c].insert({l, r, c});
        tr.erase(itl, itr);
        tr.insert({l, r, c});
        for(int tmp : suc) {
            add_modify(tmp, get_pre(tmp));
        }
        add_modify(l, get_pre(l));
        add_modify(get_suc(r), r);
    }

}

namespace BIT {
    int sum[N];
    inline int lowbit(cint x) { return x & -x; }
    inline void modify(cint p, cint v) {
        for(int i = p; i <= n; i += lowbit(i)) sum[i] += v;
    }
    inline int query(cint l, cint r) {
        int res = 0;
        for(int i = r; i > 0; i -= lowbit(i)) res += sum[i];
        for(int i = l - 1; i > 0; i -= lowbit(i)) res -= sum[i];
        return res;
    }
    inline void clear(cint p) {
        for(int i = p; i <= n; i += lowbit(i)) sum[i] = 0;
    }
};

void cdq(int l, int r, int ql, int qr) {
    if(ql > qr) return;
    if(l == r) {
        for(int i = ql; i <= qr; i++) {
            Op &o = op[swp[i]];
            if(o.tp == 1) BIT::modify(o.l, o.w);
            else ans[o.id] += BIT::query(o.l, o.r);
        }
        for(int i = ql; i <= qr; i++) {
            Op &o = op[swp[i]];
            if(o.tp == 1) BIT::clear(o.l);
        }
        return;
    }

    int mid = (l + r) >> 1;
    for(int i = ql; i <= qr; i++) {
        Op &o = op[swp[i]];
        if(o.tp == 1 && o.v <= mid) BIT::modify(o.l, o.w);
        if(o.tp == 0 && o.v > mid) ans[o.id] += BIT::query(o.l, o.r);
    }
    for(int i = ql; i <= qr; i++) {
        Op &o = op[swp[i]];
        if(o.tp == 1 && o.v <= mid) BIT::clear(o.l);
    }

    int lcnt = 0;
    for(int i = ql; i <= qr; i++) {
        Op &o = op[swp[i]];
        if(o.v <= mid) tmp[++lcnt] = swp[i];
    }
    int rcnt = lcnt;
    for(int i = ql; i <= qr; i++) {
        Op &o = op[swp[i]];
        if(o.v > mid) tmp[++rcnt] = swp[i];
    }
    for(int i = ql; i <= qr; i++) {
        swp[i] = tmp[i - ql + 1];
    }
    // if(rcnt != qr - ql + 1) throw -1;

    cdq(l, mid,     ql, ql + lcnt - 1);
    cdq(mid + 1, r, ql + lcnt, qr);
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        num[++nn] = a[i];
    }
    for(int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if(op == 1) {
            q[i].tp = 1;
            cin >> q[i].l >> q[i].r >> q[i].x;
            num[++nn] = q[i].x;
        } else {
            q[i].tp = 0;
            cin >> q[i].l >> q[i].r;
        }
    }

    lisanhua();

    odt::build();

    for(int i = 1; i <= n; i++) {
        pre[i] = odt::get_pre(i);
        op[++opCnt] = {1, i, i, pre[i], 1, 0};
    }

    for(int i = 1; i <= m; i++) {
        if(q[i].tp == 0) {
            add_query(q[i].l, q[i].r, i);
        } else {
            odt::assign(q[i].l, q[i].r, q[i].x);
        }
    }

    for(int i = 1; i <= opCnt; i++) swp[i] = i;
    cdq(0, n - 1, 1, opCnt);

    for(int i = 1; i <= m; i++) {
        if(q[i].tp == 0) cout << ans[i] << '\n';
    }

    return 0;
}

/*

20 0
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
1 9 2 3 3 3 6 6 2 2 2 4 4 1 1 9 8 7 6 6
1 1 5 3
3 3 3 3 3 3 6 6 2 2 2 4 4 1 1 9 8 7 6 6
2 5 10
1 2 4 6
3 6 6 6 3 3 6 6 2 2 2 4 4 1 1 9 8 7 6 6
2 1 20
2 1 19
2 1 18


20 6
1 9 2 3 3 3 6 6 2 2 2 4 4 1 1 9 8 7 6 6
1 1 5 3
2 5 10
1 2 4 6
2 1 20
2 1 19
2 1 18


20 3
1 9 2 3 3 3 6 6 2 2 2 4 4 1 1 9 8 7 6 6
1 1 5 3
1 2 4 6
2 1 20

*/