题意
给定一个长度为 \(n\) 的数组，初始每个数的颜色为 \(1\)，值为 \(0\)。
维护以下操作：
- 将 \(l \to r\) 的颜色替换成 \(c\)。
- 将数组中颜色为 \(c\) 的元素的值加上 \(x\)。
- 输出 \(a_i\) 的值。
\(n, q \le 10 ^ 6\)
Sol
通过操作1不难想到珂朵莉。
不难发现，只有区间推平的珂朵莉树的时间复杂度显然为 \(q \log n\)。
考虑如何维护操作2，发现我们对于每个颜色开一个 \(tag\) 就行了。
考虑操作2对于操作1的影响，不难发现我们需要将区间内颜色段自身的 \(tag\) 先下放，然后再减掉新的颜色的 \(tag\)。
区间修改单点查询，树状数组简单维护即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <set>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE
/* #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) */
/* char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf; */
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1e6 + 5;
namespace Bit {
array <int, N> edge;
int lowbit(int x) { return x & -x; }
void modify(int x, int y, int n) {
while (x <= n) {
edge[x] += y;
x += lowbit(x);
}
return;
}
int query(int x) {
int ans = 0;
while (x) {
ans += edge[x];
x -= lowbit(x);
}
return ans;
}
}
namespace Chtholly {
class Node {
public:
int l, r;
mutable int v;
Node (int _l, int _r, int _v) : l(_l), r(_r), v(_v) {}
bool operator <(const Node &t) const { return l < t.l; }
};
array <int, N> tag;
set <Node> Cht;
auto split(int x, int n) {
if (x > n) return Cht.end();
auto it = --Cht.upper_bound(Node(x, 0, 0));
int l = it -> l, r = it -> r, v = it -> v;
if (l == x) return it;
Cht.erase(it), Cht.insert(Node(l, x - 1, v));
return Cht.insert(Node(x, r, v)).fi;
}
void assign(int l, int r, int n, int k) {
auto itr = split(r + 1, n), itl = split(l, n);
for (auto it = itl; it != itr; it++) {
Bit::modify(it -> l, tag[it -> v], n);
Bit::modify(it -> r + 1, -tag[it -> v], n);
}
Cht.erase(itl, itr), Cht.insert(Node(l, r, k));
Bit::modify(l, -tag[k], n);
Bit::modify(r + 1, tag[k], n);
}
int query(int x) {
auto it = --Cht.upper_bound(Node(x, 0, 0));
return tag[it -> v];
}
}
char strbuf[15];
signed main() {
int n = read(), q = read();
Chtholly::Cht.insert(Chtholly::Node(1, n, 1));
while (q--) {
scanf("%s", strbuf);
if (strbuf[0] == 'C') {
int l = read(), r = read(), k = read();
Chtholly::assign(l, r, n, k);
}
if (strbuf[0] == 'A') {
int x = read(), y = read();
Chtholly::tag[x] += y;
}
if (strbuf[0] == 'Q') {
int x = read();
write(Bit::query(x) + Chtholly::query(x)), puts("");
}
}
return 0;
}