Description

给定序列 $a=(a_1,a_2,\cdots ,a_n),b=(b_1,b_2,\cdots ,b_n)$ 和常数 $c$，有 $m$ 个操作分四种：

• $\mathrm{set}(x,v)$：执行 $a_x\leftarrow v$.
• $\mathrm{assign}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $b_i\leftarrow k$.
• $query1(l,r)$：求 min ⁡ [ u , v ] ∈ [ l , r ] , ∣ { b u , b u + 1 , ⋯ , b v } ∣ = c ( ∑ i = u v a i ) \min\limits_{[u,v] \in [l,r], |\{b_u,b_{u+1},\cdots,b_v\}|=c} (\sum\limits_{i=u}^v a_i) [u,v]∈[l,r],∣{bu​,bu+1​,⋯,bv​}∣=cmin​(i=u∑v​ai​)，若没有满足条件的区间，答案为 $-1$.
• $query2(l,r)$：求 max ⁡ [ u , v ] ∈ [ l , r ] , ∣ { b u , b u + 1 , ⋯ , b v } ∣ = ( v − u + 1 ) ( ∑ i = u v a i ) \max\limits_{[u,v] \in [l,r], |\{b_u,b_{u+1},\cdots,b_v\}|=(v-u+1)} (\sum\limits_{i=u}^v a_i) [u,v]∈[l,r],∣{bu​,bu+1​,⋯,bv​}∣=(v−u+1)max​(i=u∑v​ai​).

Limitations

$1\le n,m\le 10^5$
$1\le a_i,v\le 10^4$
$1\le b_i,k\le c\le 100$
$1\le l,r,x\le n,l\le r$
$1\text{s},256\text{MB}$，保证数据随机

Solution

显然可以用珂朵莉树维护 $b$，用线段树维护 $a$，需要支持单点改，区间和，最大，最小.
对于查询操作，由于 $c$ 不大，可以直接对每种颜色开桶，然后在珂朵莉树上跑双指针，即可求出答案，具体见代码.

Code

$6.23\text{KB},1.20\text{s},14.98\text{MB}\text{(in total, C++20 with O2)}$

// Problem: P5251 [LnOI2019] 第二代图灵机
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5251
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}const int inf = 2e9;
struct Chtholly {int l, r;mutable int v;inline Chtholly() {}inline Chtholly(int _l, int _r, int _v): l(_l), r(_r), v(_v) {}inline bool operator<(const Chtholly& rhs) const {return l < rhs.l;}
};struct Node {int l, r, sum, max, min;
};
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }struct SegTree {vector<Node> tr;inline SegTree() {}inline SegTree(const vector<int>& a) {const int n = a.size();tr.resize(n << 2);build(0, 0, n - 1, a);}inline void pushup(int u) {tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;tr[u].max = std::max(tr[ls(u)].max, tr[rs(u)].max);tr[u].min = std::min(tr[ls(u)].min, tr[rs(u)].min);}inline void build(int u, int l, int r, const vector<int>& a) {tr[u].l = l;tr[u].r = r;if (l == r) {tr[u].sum = tr[u].max = tr[u].min = a[l];return;}const int mid = (l + r) >> 1;build(ls(u), l, mid, a);build(rs(u), mid + 1, r, a);pushup(u);}inline void set(int u, int p, int v) {if (tr[u].l == tr[u].r) {tr[u].sum = tr[u].max = tr[u].min = v;return;}const int mid = (tr[u].l + tr[u].r) >> 1;if (p <= mid) set(ls(u), p, v);else set(rs(u), p, v);pushup(u);}inline int sum(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;int ans = 0, mid = (tr[u].l + tr[u].r) >> 1;if (l <= mid) ans += sum(ls(u), l, r); if (r > mid) ans += sum(rs(u), l, r);return ans;}inline int min(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].min;int ans = inf, mid = (tr[u].l + tr[u].r) >> 1;if (l <= mid) ans = std::min(ans, min(ls(u), l, r)); if (r > mid) ans = std::min(ans, min(rs(u), l, r));return ans;}inline int max(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].max;int ans = 0, mid = (tr[u].l + tr[u].r) >> 1;if (l <= mid) ans = std::max(ans, max(ls(u), l, r)); if (r > mid) ans = std::max(ans, max(rs(u), l, r));return ans;}
};struct ODT {using It = set<Chtholly>::iterator;int n, c;set<Chtholly> odt;vector<int> vis;inline ODT() {}inline ODT(const vector<int>& a, int _c): n(a.size()), c(_c) {for (int i = 0; i < n; i++) odt.emplace(i, i, a[i]);}inline auto split(int p) {auto it = odt.lower_bound(Chtholly(p, -1, -1));if (it != odt.end() && it->l == p) return it;it--;int l = it->l, r = it->r, v = it->v;odt.erase(it);odt.emplace(l, p - 1, v);return odt.emplace(p, r, v).first;}inline void assign(int l, int r, int v) {auto itr = split(r + 1), itl = split(l);odt.erase(itl, itr);odt.emplace(l, r, v);}inline int query_all(int l, int r, SegTree& sgt) {vis.assign(c, 0);auto itr = split(r + 1), itl = split(l);auto ls = itl, rs = itl;int res = 1, ans = inf;vis[rs->v] = 1;while (rs != itr) {if (res == c) {if (ls == rs) ans = min(ans, sgt.min(0, ls->l, ls->r));else ans = min(ans, sgt.sum(0, ls->r, rs->l));vis[ls->v]--;res -= (vis[ls->v] == 0);ls++;}else {rs++;res += (vis[rs->v] == 0);vis[rs->v]++;}}return (ans == inf ? -1 : ans);}inline bool check(It itl, It itr) {if (itl == itr || next(itl) == itr) return false;for (auto it = next(itl); it != itr; it++) {if (it->l != it->r) return true;}return false;}inline int query_unique(int l, int r, SegTree& sgt) {vis.assign(c, 0);int ans = sgt.max(0, l, r);auto itr = split(r + 1), itl = split(l);auto ls = itl, rs = itl;for (; rs != itr; rs++) {vis[rs->v]++;while (check(ls, rs)) {vis[ls->v]--;ls++;}while (ls != rs && vis[rs->v] > 1) {vis[ls->v]--;ls++;}if (ls != rs) ans = max(ans, sgt.sum(0, ls->r, rs->l));}return ans;}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m, c;scanf("%d %d %d", &n, &m, &c);vector<int> a(n), b(n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);for (int i = 0; i < n; i++) scanf("%d", &b[i]), b[i]--;SegTree seg(a);ODT odt(b, c);for (int i = 0, op, x, y, v; i < m; i++) {scanf("%d", &op);if (op == 1) {scanf("%d %d", &x, &v); x--;seg.set(0, x, v);}else if (op == 2) {scanf("%d %d %d", &x, &y, &v);x--, y--, v--;odt.assign(x, y, v);}else if (op == 3) {scanf("%d %d", &x, &y);x--, y--;printf("%d\n", odt.query_all(x, y, seg));}else if (op == 4) {scanf("%d %d", &x, &y);x--, y--;printf("%d\n", odt.query_unique(x, y, seg));}}return 0;
}