2025-2026 XCPC

备战省赛，也是组队后的第一次训练。

这一场签到题比较多，一小时以内按顺序过了 A,I,C,D,K。接下来我和 Sky 讨论了一下 M 的做法，确定了 $O(n^2)$ 的 DP 维护直径，其间 Zlw 一眼 B 板子题，在 1.5h 一发通过了该题。

之后我和 Zlw 尝试口胡 E,F，没错他基本口胡出来了，大力模板。Sky 提交 M 题 RE，我去瞅了眼，发现三点共线导致分母为 $0$，立马帮他改成了叉积写法。之后又 WA，看了半天发现是 INF 开的不够大，红温……好在 3.5h 内通过。

然后我开始写 E 的字典树，写了半天发现巨丑还会运行错误，果断叫上 Zlw 来写，在提交了几发后发现神秘错误，在封榜后通过。之后就是 F，和队友确定了线段树二分写法，但是似乎和他的码风不太一样，于是被踹下来。但是由于写得有点屎，赛时没过，知道赛后 40 min 后通过该题。

最后赛时 $8$ 题首尾（主要由 Zlw 写了一大半的题 orzorzorz，以及 Sky 的难题攻克）！

F 题有点深刻，自己又写了一遍。终于琢磨出为什么赛时会有这么多队伍过，原来还有两支 $\log$ 的弱智写法。还是写一下线段树二分的做法吧，借鉴了一下题解，时间复杂度 $O(\sum k\log n)$。

#include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pii pair <int,int>
using namespace std;
const int MAX = 4e6 + 50;
const int MOD = 1e9 + 7;
inline int read ();
int t,n,q,cnt,ls[MAX],rs[MAX],tree[MAX];
class BIT 
{int n;vector <ll> c;int lowbit (int x) {return x & (-x);}public :BIT (int n) : n (n),c (n + 1,0) {}void modify (int x,int v) {for (int i = x;i <= n;i += lowbit (i)) c[i] += v;}ll query (int x) {ll res = 0;for (int i = x;i;i -= lowbit (i)) res += c[i];return res;}
};
void modify (int &cur,int l,int r,int x,int v)
{if (!cur) cur = ++cnt,ls[cur] = rs[cur] = tree[cur] = 0;tree[cur] += v;if (l == r) return ;int mid = (l + r) >> 1;if (x <= mid) modify (ls[cur],l,mid,x,v);else modify (rs[cur],mid + 1,r,x,v);
}
int calc (vector <int> cur)
{int res = 0;for (auto v : cur) res += tree[v];return res;
}
vector <int> next_L (vector <int> cur)
{for (auto &v : cur) v = ls[v];return cur;
}
vector <int> next_R (vector <int> cur)
{for (auto &v : cur) v = rs[v];return cur;
}
int search_L (vector <int> cur,int l,int r,int pos)
{if (calc (cur) == r - l + 1) return 0;if (l == r) return l;int mid = (l + r) >> 1;if (pos <= mid) return search_L (next_L (cur),l,mid,pos);else{int res = search_L (next_R (cur),mid + 1,r,pos);if (!res) return search_L (next_L (cur),l,mid,pos);else return res;}
}
int search_R (vector <int> cur,int l,int r,int pos)
{if (calc (cur) == r - l + 1) return n + 1;if (l == r) return l;int mid = (l + r) >> 1;if (pos > mid) return search_R (next_R (cur),mid + 1,r,pos);else{int res = search_R (next_L (cur),l,mid,pos);if (res == n + 1) return search_R (next_R (cur),mid + 1,r,pos);else return res;}
}
int main ()
{t = read ();while (t--){n = read ();q = read ();cnt = 0;vector <int> val (n + 1),col (n + 1),rt (n + 1,0);BIT tr (n);for (int i = 1;i <= n;++i) col[i] = read (),modify (rt[col[i]],1,n,i,1);for (int i = 1;i <= n;++i) val[i] = read (),tr.modify (i,val[i]);while (q--){int ty = read ();if (ty == 1){int p = read (),x = read ();modify (rt[col[p]],1,n,p,-1);col[p] = x;modify (rt[col[p]],1,n,p,1);}else if (ty == 2){int p = read (),v = read ();tr.modify (p,v - val[p]);val[p] = v;}else{int st = read (),k = read ();vector <int> p;for (int i = 1;i <= k;++i){int x = read ();p.push_back (rt[x]);}int l = search_L (p,1,n,st),r = search_R (p,1,n,st);printf ("%lld\n",tr.query (r - 1) - tr.query (l + 1 - 1));}}}return 0;
}
inline int read ()
{int s = 0;int f = 1;char ch = getchar ();while ((ch < '0' || ch > '9') && ch != EOF){if (ch == '-') f = -1;ch = getchar ();}while (ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar ();}return s * f;
}