[GDCPC2023] F. Traveling in Cells
寒鸽儿
·
·
题解
题意
1. $c_i \gets c'
-
v_i \gets v'
- 给定 x, S = \{t_1, t_2, \cdots, t_k\} ，求包含 x 的极大区间的权值和，满足区间内的点的颜色 \in S 。
### 题解
考虑把颜色和权值分开维护。
权值的区间和显然只需要用树状数组即可区间查询。
对于颜色，有一个 $\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
```cpp
#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;
}
```