CF 1638E Colorful Operations

题目描述

https://codeforces.com/problemset/problem/1638/E

简要题意：现在有一个长度为 $n$ 的数列 $a_i$，初始时，每个位置的值都是 $0$，颜色为 $1$，现在有 $m$ 个操作，操作有三种：给定区间 $[l,r]$ 和颜色 $c$，将区间 $[l,r]$ 染成 $c$；给定颜色 $c$ 和值 $x$，将所有颜色为 $c$ 的位置的值增加 $x$；给定位置 $i$，求 $a_i$

$n,m\le 10^6$

Solution

我们考虑用线段树维护区间连续段，同时全局维护加标记，这样二操作可以直接修改全局标记，一操作我们注意到如果区间颜色都相同可以直接打标记，那么如果区间颜色相同我们打标记，否则我们暴力向下递归修改

我们考虑使用势能分析证明这样操作的时间复杂度，我们定义势能为区间连续段的个数，注意到一操作至多使连续段的个数增加 $2$，从而得到 $\phi(n)=O(n)$，同时一操作的势能代价函数 $f(x)=x\log n$，所以总的时间复杂度为 $f(\phi(n))=O(n\log n)$

#include <iostream>
#define maxn 1000010
#define ll long long
using namespace std;

int n, m;
ll add[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int col;
    ll v; 
} T[maxn * 4];
inline void maintain(int i) { T[i].col = T[lc].col == T[rc].col ? T[lc].col : 0; }

void build(int i, int l, int r) {
    if (l == r) return T[i] = { 1, 0 }, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i); 
}

inline void Update(int i, ll v, int col) { T[i].v += v; if (col) T[i].col = col; } 

inline void pushdown(int i) {
    ll &v = T[i].v; int &col = T[i].col;
    Update(lc, v, col); Update(rc, v, col);
    v = col = 0; 
} 

void update(int i, int l, int r, int L, int R, int col) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R && T[i].col) return Update(i, add[T[i].col] - add[col], col);
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, col); update(rc, m + 1, r, L, R, col);
    maintain(i);
}

ll query(int i, int l, int r, int k) {
    if (l == r) return T[i].v + add[T[i].col];
    int m = l + r >> 1; pushdown(i);
    if (k <= m) return query(lc, l, m, k);
    else return query(rc, m + 1, r, k); 
}

inline void solve_1() {
    int x, y, z; cin >> x >> y >> z;
    update(1, 1, n, x, y, z); 
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    add[x] += y;
}

inline void solve_3() {
    int x; cin >> x;
    cout << query(1, 1, n, x) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        char s[20]; cin >> s + 1;
        switch (s[1]) {
        case 'C': solve_1(); break;
        case 'A': solve_2(); break;
        case 'Q': solve_3(); break;
        }
    }
    return 0;
}