题意
给定一个数列。每个数字有一个颜色。
单点修改数字，区间修改颜色。
求：
- 包含所有颜色的数字和最小的区间
- 没有重复颜色的数字和最大的区间
数据随机。
Sol
数据随机，直接上珂朵莉树。
跑双指针的时候套个线段树求最大最小区间和就行。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <set>
#include <queue>
#include <cassert>
#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 = 1e5 + 5, inf = 1e18;
array <int, N> s;
namespace Sgt {
array <int, N * 4> kmax, kmin, edge;
void pushup(int x) {
edge[x] = edge[x * 2] + edge[x * 2 + 1];
kmax[x] = max(kmax[x * 2], kmax[x * 2 + 1]);
kmin[x] = min(kmin[x * 2], kmin[x * 2 + 1]);
}
void build(int x, int l, int r) {
if (l == r) {
edge[x] = kmax[x] = kmin[x] = s[l];
return;
}
int mid = (l + r) >> 1;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
pushup(x);
}
void modify(int x, int l, int r, int k, int y) {
if (k > r || k < l) return;
if (l == r) {
edge[x] = kmin[x] = kmax[x] = y;
return;
}
int mid = (l + r) >> 1;
if (k <= mid) modify(x * 2, l, mid, k, y);
else modify(x * 2 + 1, mid + 1, r, k, y);
pushup(x);
}
int query(int x, int l, int r, int L, int R) {
if (L > r || R < l) return 0;
if (L <= l && R >= r) return edge[x];
int mid = (l + r) >> 1, ans = 0;
if (L <= mid) ans += query(x * 2, l, mid, L, R);
if (R > mid) ans += query(x * 2 + 1, mid + 1, r, L, R);
return ans;
}
int query_max(int x, int l, int r, int L, int R) {
if (L > r || R < l) return 0;
if (L <= l && R >= r) return kmax[x];
int mid = (l + r) >> 1, ans = 0;
if (L <= mid) ans = max(ans, query_max(x * 2, l, mid, L, R));
if (R > mid) ans = max(ans, query_max(x * 2 + 1, mid + 1, r, L, R));
return ans;
}
int query_min(int x, int l, int r, int L, int R) {
if (L > r || R < l) return inf;
if (L <= l && R >= r) return kmin[x];
int mid = (l + r) >> 1, ans = inf;
if (L <= mid) ans = min(ans, query_min(x * 2, l, mid, L, R));
if (R > mid) ans = min(ans, query_min(x * 2 + 1, mid + 1, r, L, R));
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; }
};
set <Node> Cht;
auto split(int x, int n) {
if (x > n) return Cht.end();
auto it = --Cht.upper_bound(Node(x, 0, 0));
if (it -> l == x) return it;
int l = it -> l, r = it -> r, v = it -> v;
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 v, int n) {
auto itr = split(r + 1, n), itl = split(l, n);
Cht.erase(itl, itr);
Cht.insert(Node(l, r, v));
}
array <int, 105> cur;
int tot = 0;
void add(int x) {
cur[x]++;
if (cur[x] == 1) tot++;
}
void del(int x) {
cur[x]--;
if (!cur[x]) tot--;
}
int query1(int _l, int _r, int n, int m) {
auto itr = split(_r + 1, n), itl = split(_l, n), l = itl;
int ans = inf;
if (m == 1)
return Sgt::query_min(1, 1, n, _l, _r);
tot = 0;
cur.fill(0);
for (auto r = itl; r != itr; r++) {
add(r -> v);
while (cur[l -> v] > 1)
del(l -> v), l++;
if (tot == m)
ans = min(ans, Sgt::query(1, 1, n, l -> r, r -> l));
}
return ans == inf ? -1 : ans;
}
int query2(int _l, int _r, int n, int m) {
auto itr = split(_r + 1, n), itl = split(_l, n);
int ans = Sgt::query_max(1, 1, n, _l, _r);
cur.fill(0);
auto r = itl; cur[itl -> v] = 1;
for (auto l = itl; l != itr; cur[l -> v]--, l++) {
while ((!(r -> r - r -> l) || l == r) && !cur[next(r, 1) -> v] && next(r, 1) != itr)
r++, cur[r -> v]++;
if (l != r)
ans = max(ans, Sgt::query(1, 1, n, l -> r, r -> l));
if (l == r) r++, cur[r -> v]++;
}
assert(ans > 0);
return ans;
}
}
signed main() {
int n = read(), q = read(), m = read();
for (int i = 1; i <= n; i++)
s[i] = read();
Sgt::build(1, 1, n);
for (int i = 1; i <= n; i++)
Chtholly::Cht.insert(Chtholly::Node(i, i, read()));
while (q--) {
int op = read();
/* assert(op != 4); */
if (op == 1) {
int x = read(), y = read();
Sgt::modify(1, 1, n, x, y);
s[x] = y;
}
if (op == 2) {
int l = read(), r = read(), y = read();
Chtholly::assign(l, r, y, n);
}
if (op == 3) {
int l = read(), r = read();
write(Chtholly::query1(l, r, n, m)), puts("");
}
if (op == 4) {
int l = read(), r = read();
write(Chtholly::query2(l, r, n, m)), puts("");
}
}
return 0;
}