自动搬运

查看原文

来自洛谷，原作者为

	寒鸽儿 寒鸽儿gugugu~

搬运于2025-08-24 22:50:53，当前版本为作者最后更新于2023-11-30 20:33:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

$T$ 组询问，有一个长为 $n$ 的序列，$<c_i, v_i>$ 表示 $i$ 的颜色和权值。 $q$ 次询问：

1. $c_i \gets c'$
2. $v_i \gets v'$
3. 给定 $x, S = \{t_1, t_2, \cdots, t_k\}$ ，求包含 $x$ 的极大区间的权值和，满足区间内的点的颜色 $\in S$ 。

$1 \leq n, q \leq 10^5, \sum n, q \leq 3 \times 10^5, \sum |S| \leq 10^6$ 。

题解

考虑把颜色和权值分开维护。

权值的区间和显然只需要用树状数组即可区间查询。

对于颜色，有一个 $\mathcal{O}(\sum |S| \log^2 n)$ 的暴力：

对每种颜色开一个下标线段树，动态开点，对于某个位置 $i$ 的颜色 $c_i$ ，则把代表 $c_i$ 的线段树的下标 $i$ 设为 $1$ 。

二分 $x$ 所在区间的右端点 $r$，如果从 $S$ 中所有颜色对应线段树查出的 $[x,r]$ 之和相加等于 $r - x + 1$ ，说明极大的右端点 $R \leq r$ 。则二分的单次 check 复杂度为 $\mathcal{O}(|S| \log n)$ 。

考虑优化：其实查询时可以把 $|S|$ 棵线段树叠加在一起，每个结点的和等于 $|S|$ 棵线段树对应节点的和，则访问这个虚构的树的节点的复杂度为 $\mathcal{O}(|S|)$ ，直接在线段树上二分 $\mathcal{O}(\log n)$ 次遍历结点可以得到极大区间的右端点，左端点的求法一样。这样复杂度降到 $\mathcal{O}(\sum |S| \log n)$ 。

处理时可以差分后直接二分前缀，为了保证前缀和的单调性，可以令每个位置 -1（颜色包含的下标对应位置为 $0$ ，不包含的为 $-1$（只需要让结点的值等于实际值 - 区间长度即可））。

Code

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)

using namespace std;
using ll = long long;

const int N = 1e5 + 10, Q = 1e5 + 10;
namespace SEG {
    int ls[(N + Q) * 20], rs[(N + Q) * 20], cnt[(N + Q) * 20], n, tot;
    int *root;
    void init(int N, int *ROOT) {
        n = N; root = ROOT;
        rep(i,1,n) root[i] = 0;
        rep(i,1,tot) ls[i] = rs[i] = cnt[i] = 0;
        tot = 0;
    }
    void insert(int &p, int lp, int rp, int x, int v) {
        if(!p) p = ++ tot;
        if(lp == rp) { cnt[p] += v; return ; }
        int mid = (lp + rp) >> 1;
        if(x <= mid) insert(ls[p], lp, mid, x, v);
        else insert(rs[p], mid + 1, rp, x, v);
        cnt[p] = cnt[ls[p]] + cnt[rs[p]];
    }
    int qry(int p, int lp, int rp, int l, int r) {
        if(!p) return 0;
        if(l <= lp && rp <= r) return cnt[p];
        int mid = (lp + rp) >> 1;
        if(r <= mid) return qry(ls[p], lp, mid, l, r);
        if(l > mid) return qry(rs[p], mid + 1, rp, l, r);
        return qry(ls[p], lp, mid, l, r) + qry(rs[p], mid + 1, rp, l, r);
    }
    int qL(vector<int> &ps, int lp, int rp, int val) {
        if(lp == rp) return lp;
        int mid = (lp + rp) >> 1;
        int right = - (rp - mid);
        for(int p : ps) right += cnt[rs[p]];
        if(right <= val) {
            for(int &p : ps) p = rs[p];
            return qL(ps, mid + 1, rp, val);
        }
        for(int &p : ps) p = ls[p];
        return qL(ps, lp, mid, val - right);
    }
    int qR(vector<int> &ps, int lp, int rp, int val) {
        if(lp == rp) return lp;
        int mid = (lp + rp) >> 1;
        int left = - (mid - lp + 1);
        for(int p : ps) left += cnt[ls[p]];
        if(left <= val) {
            for(int &p : ps) p = ls[p];
            return qR(ps, lp, mid, val);
        }
        for(int &p : ps) p = rs[p];
        return qR(ps, mid + 1, rp, val - left);
    }
    int qryLeft(vector<int> roots, int x) {
        for(int &c : roots) c = root[c];
        int sum = 0;
        for(int rt : roots) sum += qry(rt, 0, n + 1, x + 1, n + 1);
        return qL(roots, 0, n + 1, sum - n + x - 2);
    }
    int qryRight(vector<int> roots, int x) {
        for(int &c : roots) c = root[c];
        int sum = 0;
        for(int rt : roots) sum += qry(rt, 0, n + 1, 0, x - 1);
        return qR(roots, 0, n + 1, sum - x - 1);
    }
}

namespace BIT {
    ll c[N];
    int n;
    inline void init(int N) {
        n = N;
        rep(i,1,n) c[i] = 0;
    }
    inline void add(int x, int v) {
        for(; x <= n; x += x & (-x)) c[x] += v;
    }

    inline ll qry(int x) {
        ll ret = 0;
        for(; x; x -= x & (-x)) ret += c[x];
        return ret;
    }
    inline ll qry(int l, int r) {
        return l == 1 ? qry(r) : qry(r) - qry(l - 1);
    }
}

int root[N], col[N], v[N], n;

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if(fopen("yl.in", "r")) {
        freopen("yl.in", "r", stdin);
        freopen("yl.out", "w", stdout);
    }

    int T;
    cin >> T;

    while(T --) {
        int q;
        cin >> n >> q;
        SEG::init(n, root);
        BIT::init(n);
        rep(i,1,n) cin >> col[i];
        rep(i,1,n) cin >> v[i];
        rep(i,1,n) SEG::insert(SEG::root[col[i]], 0, n + 1, i, 1);
        rep(i,1,n) BIT::add(i, v[i]);
        int opt, p, x, k;
        while(q --) {
            cin >> opt;
            if(opt == 1) {
                cin >> p >> x;
                SEG::insert(root[col[p]], 0, n + 1, p, -1);
                SEG::insert(root[col[p] = x], 0, n + 1, p, 1);
            } else if(opt == 2) {
                cin >> p >> x;
                BIT::add(p, x - v[p]);
                v[p] = x;
            } else {
                cin >> x >> k;
                vector<int> vec(k);
                rep(i,0,k - 1) cin >> vec[i];
                int ansL = SEG::qryLeft(vec, x) + 1;
                int ansR = SEG::qryRight(vec, x) - 1;
                cout << BIT::qry(ansL, ansR) << endl;
            }
        }
    }

    return 0;
}