11.5 game
题单介绍
### 11.5
### t1
给定一颗以 $1$ 为根的 $n$ 个节点的树，每个节点有两个点权 $w_x,v_x$，每次操作可以交换选择一个节点 $x$ 和其一个儿子 $y$，交换 $w_x,w_y$，然后 $w_x \gets w_x+c$，$w_y \gets w_y-c$，其中 $c$ 是给定常数。
$1 \leq n \leq 2 \times 10^5$。
任意操作，最小化 $\sum_{i=1}^{n}|w_i-v_i|$。
考虑将一个节点上移一步会 $+c$，将一个节点下移会 $-c$，所以预处理每个点的深度 $dep_i$，然后将 $w_x \gets w_x+dep_xc$，$v_x \gets v_x+dep_xc$，对 $w$ 和 $v$ 分别排序后贪心依次匹配即可。
```cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cctype>
#define ll long long
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define GO(x) for(int i = h[x],y = e[i];i;y = e[i=ne[i]])
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 2e5+10;
static int e[N],ne[N],h[N],tot;
inline void add(int x,int y){e[++tot] = y,ne[tot] = h[x],h[x] = tot;}
static int dep[N],n;
static ll w[N],v[N],c;
void dfs(int x){
GO(x)dep[y] = dep[x]+1,dfs(y);
}
signed main(){
freopen("wound.in","r",stdin);
freopen("wound.out","w",stdout);
readx(n),readx(c);
FOR(i,1,n)readx(w[i]);
FOR(i,1,n)readx(v[i]);
int fr;FOR(i,2,n)readx(fr),add(fr,i);
dfs(1);
FOR(i,1,n)w[i] += c*dep[i],v[i] += c*dep[i];
std::sort(w+1,w+1+n),std::sort(v+1,v+1+n);
ll ans = 0;
FOR(i,1,n)ans+=std::abs(w[i]-v[i]);
output(ans),putchar(10);
return 0;
}
```
### t2
给定 $n$ 个节点，$m$ 条边的有向图，有 $3$ 种操作，每个节点有 $a_i,b_i$ 两种点权，$a_i$ 给定初始值，$b_i$ 初始为 $0$。
操作 $0$：
给定 $l,r$，求 $\sum_{i=l}^{r}a_i$。
操作 $1/2$：
给定 $l,r,c$，依次访问 $l$ 到 $r$ 的节点。
每访问一个节点 $u$，将每个点按边权从小到大的顺序遍历出边，然后将其出点加入到序列 $S$ 的末尾，$S$ 可重。
然后将 $i$ 置为 $1$，$k$ 置为 $0$，执行完以下操作后，$i \gets i+c$；如果 $i$ 超过序列 $S$ 的元素数后，结束此次操作。
如果 $a_i = 0$，不进行任何操作；
如果 $a_i \not = 0$：
$k \gets k+1$
如果总操作是操作 $1$：$a_i \gets \max(0,a_i-b_i)$，$b_i \gets b_i+k$。
如果总操作是操作 $2$：$a_i \gets \max(0,a_i-kb_i)$，$b_i \gets b_i+1$。
上述两种操作均是顺次进行的。
$q$ 次操作。
$1 \leq n,q \leq 2 \times 10^5$，$1 \leq m \leq 4 \times 10^5$，$1 \leq a_i \leq 10^9$。
时间限制 $8s$，空间 $512 MB$。
至多进行 $O(nV^{\frac{1}{3}})$ 次有效的的 $1,2$ 操作，$V$ 为 $a_i$ 最大值。
考虑一次操作，视其对前 $V^{\frac{1}{3}}$ 个元素暴力操作，记一个 $b_i$ 在 $V^{\frac{1}{3}}$ 次操作之后被操作的次数为 $n$，则 $a_i$ 至少被减去了 $V^{\frac{1}{3}}\dfrac{(1+n)n}{2}$，所以每个元素至多贡献 $V^{\frac{1}{3}}$ 后面操作。
考虑如何跳过没有值的位置。
对 $c$ 分块，$c \lt B$ 对每个位置维护 $O(B)$ 个并查集，$c \geq B$ 暴力跳。
能平衡到 $O(m \sqrt q)$，但是空间开不下，块长被迫缩小。
修改考虑用分块 $O(1)$ 修，$O(\sqrt n)$ 查询。
总时间复杂度 $O(nV^{\frac{1}{3}}+m \sqrt q+q \sqrt n)$ 这样。
```cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <vector>
#include <cassert>
// #define ll __int128
#define ll long long
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
// #define GO(x) for(int i = h[x],y = e[i];i;y = e[i=ne[i]])
#define GO(x) for(auto &y:e[x])
#define ve std::vector
#define pb push_back
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
template<typename T1,typename T2>inline T1 maxi(T1 x,T2 y){return x<y?y:x;}
template<typename T1,typename T2>inline T1 mini(T1 x,T2 y){return x<y?x:y;}
const int N = 2e5+10,M = 4e5+10+150,B = 150,G = 500,nf = 1e9;
static int n,m,q;
static int a[N],b[N];
static ll su[G];
static int fa[M][B],c[M];
static int l[N],r[N],tp,stk[N],tktp,po[N],st[G],ed[G],tot,len;
static ve<int> e[N],id[N];
int find(int x,int now){return fa[x][now]^x?fa[x][now]=find(fa[x][now],now):x;}
inline ll qy(int l,int r){
int L = po[l],R = po[r];
ll ans = 0;
if(L^R){
FOR(i,L+1,R-1)ans+=su[i];
FOR(i,l,ed[L])ans+=a[i];
FOR(i,st[R],r)ans+=a[i];
}
else FOR(i,l,r)ans+=a[i];
return ans;
}
inline void work1(int id,int k){a[id] = maxi(0,a[id]-b[id]),b[id] = mini(b[id]+k,nf);}
inline void work2(int id,int k){a[id] = maxi(0,a[id]-1ll*k*(b[id]++));}
signed main(){
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
readx(n),readx(m),readx(q);
len = std::sqrt(n),tot = (n-1)/len+1;
FOR(i,1,tot)st[i] = ed[i-1]+1,ed[i] = i*len;
ed[tot] = n;
FOR(i,1,n)po[i] = (i-1)/len+1;
FOR(i,1,n)readx(a[i]),su[po[i]]+=a[i];
int u,v;FOR(i,1,m)readx(u),readx(v),e[u].pb(v);
FOR(x,1,n){
l[x] = tp+1;
GO(x)c[++tp] = y,id[y].pb(tp);
r[x] = tp;
}
FOR(j,1,B-1)FOR(i,1,tp+B)fa[i][j] = i;
for(int op,Pl,Pr,jp,k;q--;){
readx(op),readx(Pl),readx(Pr);
if(!op)output(qy(Pl,Pr)),putchar(10);
else{
readx(jp);k = 0;
for(int t = l[Pl],id;t <= r[Pr];jp>=B?(t+=jp):(t=find(t+jp,jp)))if(a[c[t]]){
ll pre = a[id=c[t]];
if(op&1)work1(id,++k);
else work2(id,++k);
if(!a[id])stk[++tktp] = id;
su[po[id]]+=a[id]-pre;
}
FOR(tid,1,tktp)for(auto &i:id[stk[tid]])FOR(j,1,B-1)fa[i][j] = i+j,tp+1;
tktp = 0;
}
}
return 0;
}
```
### t3
$T$ 组数据。
有一个 $n$ 个节点的完全图，给定其中 $m$ 条合法的简单路径。
记 $p_{a,x}$ 表示在 $a$ 路径中 $x$ 点的下标。
两条路径 $a,b$ 不一致，当且仅当存在两个点 $x,y$，它们在 $a,b$ 中均有出现，并且满足 $(p_{a,x}-p_{a,y})(p_{b,x}-p_{b,y}) \gt 0$，同时两条路径中 $x,y$ 两点之间的子段不完全相同。
比如：
$4，1，2，3$ 和 $5，6，4，1，2$ 是一致的。
$1，2，3$ 和 $1，3，2$ 是不一致的。
判断是否不存在两条路径不一致。
$1 \leq \sum n,\sum m,\sum k \leq 3 \times 10^5$，其中 $k$ 是路径长度。
形式化题意：给定 $m$ 个序列，每个序列的元素在 $[1,n]$ 以内，并且不重复。
两个序列 $a,b$ 同构，等价于对于所有其中在 $a,b$ 中均有出现的元素 $x,y$，如果它们满足 [$p_{a,x} \lt p_{a,y}$ 并且 $p_{b,x} \lt p_{b,y}$] 或者满足 [$p_{a,x} \gt p_{a,y}$ 并且 $p_{b,x} \gt p_{b,y}$]，不妨设是满足第 $1$ 种条件，均有 $a$ 序列中 $[p_{a,x},p_{a,y}]$ 的子段与 $b$ 序列中 $[p_{b,x},p_{b,y}]$ 的子段完全一样。
判断所有序列两两之间是否均同构。
存在一种 $\min(len_a,len_b)$ 判断两条路径是否一致的方法。
就是从左往右扫描一条路径 $a$，对于第一个出现的相同节点 $c$，记录 $p_{a,c}-p_{b,c}$ 的值以及 $p_{b,c}$；
如果后续有扫描到相同节点 $d$，并且
如果 $p_{a,d} \lt p_{a,c}$ 那不用管它。
否则如果： $p_{a,d}-p_{b,d} \not= p_{a,c}-p_{b,c}$ 两条路径肯定不一致；
否则要求 $c,d$ 之间都没有出现过 $p_{a,d} \lt p_{a,c}$ 以及是公共点。
说人话就是对 $a,b$ 中共同出现的元素之间两两连边（思维层面的），如果存在两条分别从元素 $x$ 和元素 $y$ 出发的边，满足二者不相交，那么这两条边的斜率一定要一致，并且 $[p_{a,x},p_{a,y}]$ 中间的点必须都有连边，并且斜率一致，具体实现可以参考代码或者上述说明。
考虑对于路径长度 $len$ 分治。
当 $len \gt B$ 时，暴力检查其与其它所有路径是否一致，检查一条边的时间复杂度是 $O(\sum k)$ 的，总时间复杂度 $O(\dfrac{k^2}{B})$。
否则考虑两个路径 $a,b$ 的 $x,y$ 中间子段相等的限制，等价于 $a_{p_{a,x}+1}=b_{p_{b,x}+1}$，发现其具有递归性。
考虑暴力维护每条路径 $a$ 中的三元组 $(a_x,a_{x+1},a_y)$，$(x \lt y)$。
不存在两条路径不一致，等价于不存在三元组满足第一项与第三项对应相等的同时，第二项不等。
记 $t$ 为 $len \leq B$ 的路径的平均长度，则时间复杂度约为 $O(t^2 \dfrac{k}{t}) = O(tk)$，$t$ 最大取 $B$。
所以 $B$ 取 $\sqrt k$ 即可。
时间复杂度 $O(k \sqrt k)$。
```cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <vector>
#define ll long long
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define GO(x) for(int i = h[x],y = e[i];i;y = e[i=ne[i]])
#define ve std::vector
#define pb push_back
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 3e5+10,nf = 1e9+10,B = std::sqrt(N);
static int len[N],n,m,npy[N],tp[N],p[N];
struct node{int x,y;};
static ve<int> s[N];
static ve<node> f[N];
inline bool check(const ve<int> &s1,int *p2,int l1){
int mi = nf,id = -nf;
bool flg = 0;
FOR(i,1,l1){
int now = s1[i];
int p = p2[now];
if(p){
if(id==-nf){
id = i-p;
mi = p;
continue;
}
else if(i-p==id){
if(flg)return 0;
continue;
}
if(mi<p)return 0;
if(mi==p)puts("?"),exit(0);
}
else if(id!=-nf)flg |= 1;
}
return 1;
}
inline void solve(){
readx(n),readx(m);
FOR(i,1,n)f[i].clear();
FOR(i,1,m){
s[i].clear();
readx(len[i]);
s[i].resize(len[i]+2);
FOR(j,1,len[i]){
readx(s[i][j]);
}
}
FOR(i,1,m){
if(len[i]>=B){
FOR(j,1,len[i])p[s[i][j]] = j;
FOR(j,1,m)if(i^j)if(!check(s[j],p,len[j])){
FOR(j,1,len[i])p[s[i][j]] = 0;
return puts("NO"),void();
}
FOR(j,1,len[i])p[s[i][j]] = 0;
}
else{
FOR(j1,1,len[i]){
FOR(j2,j1+1,len[i]){
f[s[i][j1]].pb((node){s[i][j1+1],s[i][j2]});
}
}
}
}
FOR(i,1,n){
for(auto t:f[i]){
if(!npy[t.y])npy[t.y] = t.x;
else if(npy[t.y]^t.x){
for(auto &t:f[i])npy[t.y] = 0;
return puts("NO"),void();
}
}
for(auto &t:f[i])npy[t.y] = 0;
}
puts("YES");
}
signed main(){
freopen("mismatch.in","r",stdin);
freopen("mismatch.out","w",stdout);
int t;for(readx(t);t--;solve());
return 0;
}
```
### t4
[P14035 [PAIO 2025] GCD](https://www.luogu.com.cn/problem/P14035)
给定长度为 $n$ 的序列和常数 $k$ 和 $V$，求：
$\sum_{x=0}^{V}\sum_{i=1}^{n}\sum_{j=i+1}^{n}((\gcd\{a_1,a_2,\cdots,a_i,a_j,a_{j+1},\cdots,a_{n}\})^k \text{xor} x)(a_i+a_j)$
$1 \leq n \leq 5 \times 10^5，1 \leq k \leq 100,1 \leq V \leq 10^9$。
考虑前后缀 $gcd$ 至多有 $\log V$ 个不同的段，所以至多有 $\log^2 V$ 种不同 $\gcd$ 组合。
后面的 $a_i,a_j$ 用 $a_i$，$ia_i$ 的前缀和 和 $(n-i+1)a_i$ 的后缀和维护一下。
$\gcd$ $k$ 次方后亦或 $[0,V]$ 内的 $x$，可以按位考虑贡献。
高于 $30$ 的位一定会被贡献，低于 $30$ 的位考虑其与 $x$ 该位会有多少贡献。
```cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <ctime>
#define ll long long
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define GO(x) for(int i = h[x],y = e[i];i;y = e[i=ne[i]])
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 5e5+10,mo = 998244353,G = 50+10,base = (1ll<<30)-1;
static int p[N],s[N],x,pa[N],a[N],n,k,V,tpa[N],tsa[N];
static ll pw[G];
static int r[N],l[N];
inline ll ksm(int a,int b){int c = 1;for(;b;b>>=1,a = 1ll*a*a%mo)if(b&1)c = 1ll*c*a%mo;return c;}
inline ll ksm_aya(int a,int b){int c = 1;for(;b;b>>=1,a = (1ll*a*a)&base)if(b&1)c = (1ll*c*a)&base;return c;}
inline void prepw(int n){pw[0] = 1;FOR(i,1,n)pw[i] = pw[i-1]<<1;}
inline int ji1(int wei,int x){return ((x+1)/pw[wei+1])*pw[wei]+std::min((x+1)%pw[wei+1],pw[wei]);}
inline int cal(int now,int x){
int ans = 0,len = std::max(now?std::__lg(now):0,x?std::__lg(x):0);
FOR(i,0,len){
bool p = now&pw[i];
int tmp = ji1(i,x);
if(!p)tmp = x+1-tmp;
ans = (0ll+ans+1ll*pw[i]*tmp%mo)%mo;
}
return ans;
}
static int pl[N],tpl,pr[N],tpr;
inline int work1(int l1,int l2,int r1,int r2){return (1ll*(pa[l2]-pa[l1-1])*(r2-r1+1)%mo+1ll*(pa[r2]-pa[r1-1])*(l2-l1+1)%mo)%mo;}
inline int work2(int l1,int l2,int r1,int r2){
r1 = std::max(l1,r1);
ll ans1 = (tpa[r2]-tpa[r1-1])-1ll*l1*(pa[r2]-pa[r1-1])%mo;
l2 = std::min(l2,r2);
int tl1 = std::max(l1,r1);
ll ans2 = (tsa[tl1]-tsa[l2+1])-1ll*(n-r2+1)*(pa[l2]-pa[tl1-1])%mo;
ans2 = (0ll+ans2+1ll*(pa[tl1-1]-pa[l1-1])*(r2-r1+1)%mo)%mo;
return (ans1+ans2)%mo;
}
signed main(){
freopen("wave.in","r",stdin);
freopen("wave.out","w",stdout);
prepw(40);
readx(n),readx(k),readx(V);
FOR(i,1,n)readx(a[i]);
FOR(i,1,n)p[i] = std::__gcd(a[i],p[i-1]),pa[i] = (0ll+pa[i-1]+a[i])%mo,tpa[i] = (0ll+tpa[i-1]+1ll*i*a[i]%mo)%mo;
REP(i,n,1)s[i] = std::__gcd(a[i],s[i+1]),tsa[i] = (0ll+tsa[i+1]+1ll*(n-i+1)*a[i]%mo)%mo;
r[n+1] = n+1;
REP(i,n,1)r[i] = s[i]==s[i+1]?r[i+1]:i;
FOR(i,1,n)l[i] = p[i]==p[i-1]?l[i-1]:i;
for(int i = 2,j = 1;i <= n+1;i++){
if(p[i]!=p[i-1])pl[++tpl] = j,j = i;
}
for(int i = n-1,j = n;i >= 0;--i){
if(s[i]!=s[i+1])pr[++tpr] = j,j = i;
}
pl[tpl+1] = n+1;
int ans = 0;
FOR(i,1,tpl){
int l1 = pl[i],l2 = pl[i+1]-1;
FOR(j,1,tpr){
int r1 = pr[j+1]+1,r2 = pr[j];
if(r2<=l1)break;
ll now = std::__gcd(p[l1],s[r1]);
ll lyc = ksm_aya(now,k),tmp = (0ll+ksm(now,k)-lyc)%mo;
ll fnl = (1ll*tmp*(V+1)%mo+cal(lyc,V))%mo;
tmp = 0;
if(r1>l2)tmp = work1(l1,l2,r1,r2);
else if(r2<=l2)tmp = work2(l1,l2,r1,r2);
else tmp = (0ll+work1(l1,l2,l2+1,r2)+work2(l1,l2,r1,l2))%mo;
ans = (0ll+ans+1ll*tmp*fnl%mo)%mo;
}
}
output((0ll+ans+mo)%mo),putchar(10);
return 0;
}
```