P5251 [LnOI2019] 第二代图灵机 Solution

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;
}