NOI2026 训练（二十）
Contest Link
\(\text{By DaiRuiChen007}\)
*A. [P15941] 多方通信 2 (8)
Problem Link
好有日本特色的题目。
首先肯定要 Boruvka，每个人每轮向所有人发当前所属的连通块，以及最小出边的权值和终点，每轮每个人都能维护出下一轮的结构。
信息量是 \(n^2V\) 级别的，恰好可以压进 \(2^{64}\) 级别内。
不过我们还需要传边权和信息，注意到一个人不需要向自己传递最小出边，所以可以把这 \(nV\) 的信息用来传边权和。
此时需要九轮，尝试进一步优化，显然比较有优化空间的是开头和结尾的轮次，对于第一轮，我们注意到每个点的最小出边不会构成长度 \(>2\) 的环，也就是说以任意顺序加入这些边，保留不成环的都可以。
那么此时我们只要 \(n\) 的信息传递边终点，剩余部分还能再传递每个点的次小出边，此时每个连通块大小 \(\ge 3\)。
对于较后面的轮次，特点是连通块数量少，考虑直接一次性维护所有边权，具体来说设连通块数量为 \(k\)，如果 \(\binom k2<n\)，我们直接让每个点维护一对连通块之间的最小边权，只要前一轮每个点向对应的位置发送信息求出，然后下一轮把这些信息都发到 \(0\) 上跑 Kruskal 就行。
进行三轮 Boruvka 后连通块大小 \(\ge 12\)，则 \(k\le 21\) 可以运行此算法。
考虑一下维护权值的过程，有一个小问题是第一轮每个点最小出边权值未知，类似上面的做法，我们把这条边权的信息发到下一层的同一个点，直到计算每个连通块间最小边的那一轮，我们不用 \(0\) 表示连通块间最小边，而是把这些边权信息发过去，这样下一轮 \(0\) 就能知道这轮 Boruvka 的边权和。
时间复杂度 \(\mathcal O(n^2\log n)\)。
代码：
#include<bits/stdc++.h>
#include "multi.h"
#define ull unsigned long long
using namespace std;
const ull inf=(1ll<<48)-1;
struct Edge { ull w; int u,v; };
bool operator <(const Edge&u,const Edge&v) { return u.w<v.w; }
vector<ull>strategy(int n,int O,int x,vector<ull>a,vector<ull>b) {if(!O) {vector <Edge> E;for(int j=0;j<n;++j) if(j!=x) E.push_back({a[j],j,x});stable_sort(E.begin(),E.end()),E.resize(2,E[0]);return vector<ull>(n,E[1].w<<16|E[1].u<<8|E[0].u);}vector <int> f(n),ot(n); vector <Edge> E;iota(f.begin(),f.end(),0);auto in=[&](int u) { for(;f[u]^u;u=f[u]=f[f[u]]); return u; };ull Z=O>1?b[x]>>8:0;if(O==5) {int m=b[x]&255;for(int i=0,k=1;i<m;++i) for(int j=i+1;j<m;++j,++k) E.push_back({b[k],i,j});stable_sort(E.begin(),E.end());for(auto&e:E) if(in(e.u)!=in(e.v)) f[in(e.u)]=in(e.v),Z+=e.w;return {Z};}if(O==1) {for(int i=0,j;i<n;++i) if(in(i)!=in(j=b[i]&255)) f[in(i)]=in(j),Z+=(i==x?a[j]:0);for(int i=0;i<n;++i) E.push_back({b[i]>>16,in(b[i]>>8&255),in(i)});stable_sort(E.begin(),E.end());for(auto&e:E) if(!ot[e.v]++&&in(e.u)!=in(e.v)) {Z+=(x?0:e.w),f[in(e.u)]=in(e.v);}} else if(O<=3) {for(int i=0;i<n;++i) f[i]=b[i]&255;for(int i=0;i<n;++i) {if(i!=x) E.push_back({b[i]>>16,in(b[i]>>8&255),in(i)});else {int u=x; ull w=inf;for(int j=0;j<n;++j) if(in(j)!=in(x)&&a[j]<=w) w=a[j],u=j;E.push_back({w,in(u),in(x)});}}stable_sort(E.begin(),E.end());for(auto&e:E) if(!ot[e.v]++&&in(e.u)!=in(e.v)) Z+=(x?0:e.w),f[in(e.u)]=in(e.v);}if(O<=2) {int u=x; ull w=inf;for(int j=0;j<n;++j) if(in(j)!=in(x)&&a[j]<=w) w=a[j],u=j;vector<ull>c(n,w<<16|u<<8|in(x)); c[x]=Z<<8|in(x);return c;} else if(O==3) {vector<ull>c(n,inf); vector<int>p(n,-1); int m=0;for(int i=0;i<n;p[i]=p[in(i)],++i) if(p[in(i)]<0) p[in(i)]=m++;for(int i=0,k=1;i<m;++i) for(int j=i+1;j<m;++j,++k) if(i==p[x]) {for(int u=0;u<n;++u) if(p[u]==j) c[k]=min(c[k],a[u]);}c[0]=Z<<8|(x?0:m);return c;} else {if(x) return vector<ull>(n,*min_element(b.begin(),b.end()));return vector<ull>(n,accumulate(b.begin(),b.end(),0ll));}
}
B. [P15584] 网格树 (4)
Problem Link
先考虑子任务 3，容易发现充要条件是对于每个子树，深度为 \(i\) 的点不超过 \(i+1\) 个。
因此对于原问题，我们要对每个不合法的子树延长一些边使得该条件被满足。
很显然我们先延长根到左右儿子的边使得两侧最大深度相同，然后肯定是直接把所有点的深度一起增加来调整。
直接维护差分数组，操作是平移、合并以及查询 \(\max i-v_i\)，容易平衡树实现。
时间复杂度是 \(\mathcal O(n\log^2n)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int sz[MAXN],ls[MAXN],rs[MAXN],pr[MAXN];
ll f[MAXN],a[MAXN];
void psu(int p) {f[p]=sz[ls[p]]+1-a[p],sz[p]=sz[ls[p]]+1+sz[rs[p]];if(ls[p]) f[p]=max(f[p],f[ls[p]]);if(rs[p]) f[p]=max(f[p],f[rs[p]]+sz[ls[p]]+1);
}
void split(int p,ll k,int&x,int&y) {if(!p) x=y=0;else if(a[p]<=k) x=p,split(rs[p],k,rs[x],y),psu(x);else y=p,split(ls[p],k,x,ls[y]),psu(y);
}
int merge(int x,int y) {if(!x||!y) return x|y;if(pr[x]<pr[y]) return rs[x]=merge(rs[x],y),psu(x),x;return ls[y]=merge(x,ls[y]),psu(y),y;
}
void ins(int&u,int o) {sz[o]=1,ls[o]=rs[o]=0,f[o]=1-a[o];int x,y; split(u,a[o],x,y);u=merge(merge(x,o),y);
}
vector <int> Q;
void gtr(int x) { if(x) gtr(ls[x]),Q.push_back(x),gtr(rs[x]); }
int fa[MAXN],e[MAXN][2],w[MAXN],rt[MAXN];
ll g[MAXN],h[MAXN];
void dfs(int x) {if(!e[x][0]) return ;for(int y:e[x]) dfs(y),g[x]=max(g[x],g[y]+w[y]);for(int y:e[x]) h[y]+=g[x]-g[y];int u=e[x][0],v=e[x][1];if(sz[rt[u]]<sz[rt[v]]) swap(u,v);Q.clear(),gtr(rt[v]);for(int i:Q) a[i]+=h[v]-h[u],ins(rt[u],i);h[x]=h[u],rt[x]=rt[u],a[x]=-h[x],ins(rt[x],x);ll z=max(0ll,f[rt[x]]-1-h[x]);h[x]+=z,g[x]+=z;
}
ll compute_min_depth(int n,vector<int>P,vector<int>C,vector<int>O) {mt19937 rnd(time(0));for(int i=1;i<=n;++i) pr[i]=rnd();for(int i=2;i<=n;++i) e[fa[i]=P[i-2]+1][O[i-2]]=i,w[i]=C[i-2];dfs(1);return g[1];
}
*C. [P15587] 排序 (7)
Problem Link
考虑一些有道理的树构造，例如一个点下面挂若干长度为 \(2\) 的链，那么只要根不在最大独立集中，则我们就能比较每条链上两个点的大小。
为了做到这一点，我们可以选两个点 \(x,y\)，如果 \(a_x\ge a_y\) 就把 \(y\) 作为根 \(x\) 作为儿子，这样就能保证了。
实现时可以随便取一个点当根，如果这个点被选了就和另一个点交换即可，为了防止 \(a_x=a_y\) 导致无限交换，此时选根说明每条链上都是下方更大，所以我们可以钦定至多交换一次。
此时我们只要通过比较若干对不相交元素把序列排序。
题目中的次数限制可能是 \(\log^2n\) 级别，考虑一些构造方法。
显然只要考虑还原 01 序列的方法，尝试进行归并，那么我们要找到合并后的的 01 分界线。
由于我们可以递归，因此直接把长度为 \(2^k\) 的序列分成两个长度为 \(2^{k-1}\) 的子序列排序就行。
那么我们要尽量找两个相对无序的序列递归排序更优，考虑直接把所有奇数位置和偶数位置分别排序。
此时两个子序列 \(1\) 的个数最多差 \(2\)，分讨发现我们只要交换某一对 \((2i-1,2i)\) 上的相邻元素，只要一次询问。
为了方便实现，使用 \(+\infty\) 把序列长度补至 \(2^{10}\)，这部分操作次数 \(55\)，然后插入两个根 \(x,y\) 可以二分，为了优化考虑同时二分，分别和 \(mid,mid+1\) 比较即可。
操作次数为 \(\dfrac{k(k+1)}{2}+k+\mathcal O(1)\)，其中 \(k=\log_2n=10\)。
时间复杂度 \(\mathcal O(n\log n)\)。
代码：
#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
const int m=1024;
int n,a[m][m],b[m],c[m],X,Y,mx;
bool in[m],ch;
bool cmp(int x,int y) {if((x>mx)^(y>mx)) return y>mx;return x<=mx&&a[x][y]<0;
}
vector<array<int,2>>E,Q;
void ask() {memset(in,0,sizeof(in)),in[X]=1,Q={{X,Y}},in[Y]=1;for(auto e:E) if(e[0]<=mx&&e[1]<=mx) Q.push_back({X,e[0]}),Q.push_back(e),in[e[0]]=in[e[1]]=1;for(int i=0;i<n;++i) if(!in[i]) Q.push_back({X,i});vector<int>Z=ask_question(Q);if(Z[X]&&!ch) return ch=1,swap(X,Y),ask();for(auto e:E) {if(Z[e[0]]) swap(e[0],e[1]);a[e[0]][e[1]]=-1,a[e[1]][e[0]]=1;}
}
void mrg(int k) {if(!k) {for(int i=0;i<m;i+=2) E.push_back({b[i],b[i+1]});ask(),E.clear();for(int i=0;i<m;i+=2) if(cmp(b[i+1],b[i])) swap(b[i],b[i+1]);return ;}for(int h=0;h<m;h+=2<<k) for(int i=0;i<(1<<k);++i) {c[h|i]=b[h+2*i],c[h|1<<k|i]=b[h+2*i+1];}memcpy(b,c,sizeof(b));mrg(k-1);for(int h=0;h<m;h+=2<<k) for(int i=0;i<(1<<k);++i) {c[h+2*i]=b[h|i],c[h+2*i+1]=b[h|1<<k|i];}memcpy(b,c,sizeof(b));for(int h=0;h<m;h+=2<<k) for(int i=1;i<(2<<k)-1;i+=2) E.push_back({b[h+i],b[h+i+1]});ask(),E.clear();for(int h=0;h<m;h+=2<<k) for(int i=1;i<(2<<k)-1;i+=2) if(cmp(b[h+i+1],b[h+i])) swap(b[h+i],b[h+i+1]);
}
void fd(int x=-1,int y=-1) {X=Y=-1;for(int i=0;i<(n>5?n-2:n);++i) if(i!=x&&i!=y) {if(X<0) X=b[i];else if(Y<0) Y=b[i];}
}
vector<int>sorting(int N) {n=N,X=n-1,Y=n-2,mx=n-3,iota(b,b+m,0);if(n==5) {mx=n-1;for(int x=0;x<n;++x) for(int y=x+1;y<n;++y) E={{x,y}},fd(x,y),ask(),ch=0;for(int t=1;t<n;++t) for(int i=t-1;~i&&cmp(b[i+1],b[i]);--i) swap(b[i],b[i+1]);return vector<int>(b,b+n);}for(int x=0;x<10;++x) mrg(x);int u=n-2,v=n-1; mx=n-1,ch=1;E.push_back({u,v}),fd(),ask(),E.clear();if(cmp(v,u)) swap(u,v);int lx=0,rx=n-3,ly=0,ry=n-3;while(lx<rx||ly<ry) {int x=(lx+rx)>>1,y=(ly+ry)>>1; E.clear();if(lx<rx) E.push_back({u,b[x]});if(ly<ry) E.push_back({v,b[y+1]});fd(x,y+1),ask(),E.clear();if(lx<rx) cmp(u,b[x])?rx=x:lx=x+1;if(ly<ry) cmp(b[y+1],v)?ly=y+1:ry=y;} ++ly;if(lx==n-3) {E.push_back({u,b[lx]}),fd(lx),ask(),E.clear();if(cmp(b[lx],u)) lx=ly=n-2;} else if(ly==1) {E.push_back({v,b[0]}),fd(0),ask(),E.clear();if(cmp(v,b[0])) lx=ly=0;}if(ly<lx) ly=lx;vector <int> Z(b,b+n-2);Z.insert(Z.begin()+ly,v);Z.insert(Z.begin()+lx,u);return Z;
}
D. [P15133] 最后的滑动窗口问题 (2)
Problem Link
考虑笛卡尔树上每个子树和询问区间的交，简单分讨可以写成二维偏序的形式计算。
时间复杂度 \(\mathcal O(n\log n)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
int n,m,a[MAXN],L[MAXN],R[MAXN],t[MAXN];
struct BIT {ll tr[MAXN],s;void init() { memset(tr,0,sizeof(tr)); }void add(int x,ll v) { for(;x<=n;x+=x&-x) tr[x]+=v; }ll qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
} X,Y;
bool in[MAXN];
ll f[MAXN*2];
vector <array<int,2>> Q[MAXN],A[MAXN];
void ins(int c,int l,int r) { A[r].push_back({l,c}); }
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m; vector <int> O;for(int i=1;i<=n;++i) cin>>a[i],O.push_back(i);sort(O.begin(),O.end(),[&](int x,int y){ return a[x]>a[y]; });for(int x:O) {int l=x,r=x; in[x]=1;if(in[x-1]) l=L[x-1],ins(t[l]-a[x],l,x-1);if(in[x+1]) r=R[x+1],ins(t[x+1]-a[x],x+1,r);t[l]=a[x],R[l]=r,L[r]=l;}ins(t[1],1,n);for(int i=1,l,r,k;i<=m;++i) cin>>l>>r>>k,Q[r].push_back({k,2*i}),Q[l-1+k-1].push_back({k,2*i-1});for(int i=1,d;i<=n;++i) {for(auto o:A[i]) d=i-o[0]+1,X.add(d,o[1]),Y.add(d,1ll*o[1]*d);for(auto o:Q[i]) f[o[1]]+=Y.qry(n)-Y.qry(o[0]-1)-(X.qry(n)-X.qry(o[0]-1))*(o[0]-1);}X.init(),Y.init();for(int i=n;i;--i) {for(auto o:Q[i]) f[o[1]]+=X.qry(i-o[0]+1)*(i-o[0]+2)-Y.qry(i-o[0]+1);for(auto o:A[i]) X.add(o[0],o[1]),Y.add(o[0],1ll*o[0]*o[1]);}for(int i=1;i<=m;++i) cout<<f[2*i]-f[2*i-1]<<"\n";return 0;
}
E. [P15134] XOR 染色 (3)
Problem Link
直接根据最高位分讨，如果这一位上 \(X_i=0\) 那么左右子树问题独立，求最大色数求和即可。
否则如果同时存在 \(B_i=0,B_i=1\) 的元素，那么左右两侧都变成完全图了，只要计算两侧之间能有多少相同元素。
也就是计算 \(A_i=0\) 的元素中有多少没被 \(B_i=1\) 覆盖，以及 \(A_i=1\) 的元素中有多少没被 \(B_i=0\) 的覆盖，两种元素求较小值即可。
如果只有 \(B_i=0\) 的元素，那么先加上 \(A_i=0\) 的所有所有元素，剩余 \(A_i=1\) 的子树和 \(B_i=0\) 的子树是一个一模一样的子问题，唯一的区别是此时没有被任何 \(B\) 覆盖的元素可以和 \(A_i=0\) 的元素填相同的颜色，这是平凡的情况。
时间复杂度 \(\mathcal O(n\log V)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
struct Trie {int c[MAXN*32],e[MAXN*32][2],n;void init() { for(int i=0;i<=n;++i) c[i]=e[i][0]=e[i][1]=0; n=1; }void ins(int x) {int u=1; ++c[1];for(int k=29;~k;--k) {if(!e[u][x>>k&1]) e[u][x>>k&1]=++n;++c[u=e[u][x>>k&1]];}}
} A,B;
int n,m,X;
int ct(int u,int v,int k) {if(!u||!v) return A.c[u];if(k<0) return 0;if(X>>k&1) return (B.e[v][0]?0:ct(A.e[u][0],B.e[v][1],k-1))+(B.e[v][1]?0:ct(A.e[u][1],B.e[v][0],k-1));return ct(A.e[u][0],B.e[v][0],k-1)+ct(A.e[u][1],B.e[v][1],k-1);
}
int dp(int u,int v,int k,bool h) {if(!u||!v) return A.c[u]&&!h;if(k<0) return A.c[u];if(!(X>>k&1)) return max(dp(A.e[u][0],B.e[v][0],k-1,h),dp(A.e[u][1],B.e[v][1],k-1,h));if(B.e[v][0]&&B.e[v][1]) {return A.c[u]-min(ct(A.e[u][0],B.e[v][1],k-1),ct(A.e[u][1],B.e[v][0],k-1));}int o=!B.e[v][0]; h|=A.c[A.e[u][o]];return dp(A.e[u][!o],B.e[v][o],k-1,h)+A.c[A.e[u][o]];
}
void solve() {cin>>n>>m>>X,A.init(),B.init();for(int i=1,x;i<=n;++i) cin>>x,A.ins(x);for(int i=1,x;i<=m;++i) cin>>x,B.ins(x);cout<<dp(1,1,29,0)<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
*F. [P15264] Cow Circle P (7.5)
Problem Link
考虑静态问题，注意到两个人的相对顺序不变，即任何时候序列都是原顺序的循环移位。
只要统计序列的开头，可以通过计算 \((n-1,0)\) 之间的边被经过的次数来求出。
枚举 \(1\) 最终的位置，对于每个位置需要做一个 \(\bmod n\) 的背包，不过注意到每个人对不同的位置只有 \(\mathcal O(1)\) 种本质不同的贡献且形如区间。
直接线段树维护区间乘单项式的背包即可。
时间复杂度 \(\mathcal O(n^2\log n)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5005,MOD=1e9+7,MAXM=1e6+5;
int n,m,a[MAXN],L[MAXN],R[MAXN],cl[MAXN],cr[MAXN];
ll K,wl[MAXN],wr[MAXN],Z[MAXM],f[MAXN],g[MAXN];
array<int,2>b[MAXN*2];
void solve() {cin>>n>>m>>K,memset(Z,0,m<<3);for(int i=1;i<=n;++i) cin>>wr[i],wl[i]=(1+MOD-wr[i])%MOD;for(int i=1;i<=n;++i) {cin>>a[i],L[i]=R[i]=0;b[2*i-1][0]=(a[i]+K)%m,b[2*i][0]=(a[i]-K%m+m)%m;cl[i]=((a[i]-K-b[2*i][0])/m%n+n)%n,cr[i]=(a[i]+K)/m%n;}for(int i=1;i<=2*n;++i) b[i][1]=i;sort(b+1,b+2*n+1);for(int i=1;i<=2*n;++i) {int x=(b[i][1]+1)/2;if(L[x]) R[x]=i;else if(b[L[x]=i][1]&1) swap(cl[x],cr[x]),swap(wl[x],wr[x]);}for(int i=1,x;i<=2*n;++i) {memset(f,0,n<<3),x=(b[i][1]+1)/2;if(i==L[x]) f[cl[x]]=wl[x];else f[cr[x]]=wr[x];for(int j=1;j<=n;++j) if(j!=x) {memset(g,0,n<<3);int s=(cl[j]+n-(L[j]<i))%n,t=(cr[j]+n-(R[j]<i))%n;for(int k=0;k<n;++k) {g[(k+s)%n]=(g[(k+s)%n]+f[k]*wl[j])%MOD;g[(k+t)%n]=(g[(k+t)%n]+f[k]*wr[j])%MOD;}memcpy(f,g,n<<3);}Z[b[i][0]]=(Z[b[i][0]]+f[0])%MOD;}for(int i=0;i<m;++i) cout<<Z[i]<<" \n"[i==m-1];
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
G. [P15945] 雨落三角 (4.5)
Problem Link
用三维偏序刻画三角形，\(x\ge a,y\ge b,x+y\le c\)，那么对 \(c\) 降序扫描线，每次加入一个 \(x\ge a,y\ge b\) 的矩形。
\(k=1\) 时只要维护矩形并，对每个 \(x\) 维护 \(\min y\)，操作是区间推平，直接用 ODT 维护，算答案时只要在轮廓线改变时算新矩形和 \(x+y\le c\) 的交集大小即可。
对于 \(k=2\)，每次在 \(k=1\) 范围内插入矩形时把原范围和新矩形的交插入 \(k=2\) 的范围内，然后不断重复 \(k\to k+1\) 过程即可。
时间复杂度 \(\mathcal O(nk\log n)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct seg { int l,r,h; };
bool operator<(const seg&u,const seg&v) { return u.l<v.l; }
int n,m,K;
set <seg> f[6]; ll Z[6];
ll sz(int l,int r,int h,int s) {s-=h,r=min(r,s-1); if(s<=l) return 0;return (2ll*s-l-r-1)*(r-l+1);
}
auto split(set<seg>&g,int x) {auto it=g.lower_bound({x,x,0});if(it!=g.end()&&it->l==x) return it;auto o=*--it; g.erase(it);g.insert({o.l,x-1,o.h});return g.insert({x,o.r,o.h}).first;
}
void ins(int k,int l,int r,int h,int s) {auto R=split(f[k],r+1),L=split(f[k],l);for(auto i=L;;++i) {if(i==R||i->h<=h) {if(i!=R&&k<K) ins(k+1,i->l,r,h,s);if(i!=L) f[k].erase(L,i),f[k].insert({l,i->l-1,h});return ;}Z[k]+=sz(i->l,i->r,h,s)-sz(i->l,i->r,i->h,s);if(k<K) ins(k+1,i->l,i->r,i->h,s);}
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>m>>n>>K;for(int i=1;i<=K;++i) f[i].insert({0,m,m});vector<seg>a;for(int i=1,x,y,z;i<=n;++i) cin>>x>>y>>z,a.push_back({x,y,x+y+z});sort(a.begin(),a.end(),[&](auto i,auto j){ return i.h>j.h; });for(auto i:a) if(i.l<m&&i.r<m) ins(1,i.l,m-1,i.r,i.h);for(int i=1;i<=K;++i) cout<<Z[i]<<"\n";return 0;
}
H. [P15493] JOI 之旅 2 (5)
Problem Link
思路就是先把树上路径逐步简化成简单结构（序列前缀），首先把树上路径拆成 \(\mathcal O(1)\) 条到根路径的信息，求自卷积也能拆成 \(\mathcal O(1)\) 条到根路径信息的乘积。
也就是求 \([z^b]\sum_{x,y} w_{x,y}(\sum_{i\in\mathrm{path}(rt,x)}z^{a_i})\times (\sum_{j\in\mathrm{path}(rt,y)} z^{a_j})\)。
而到根的树上路径可以用出入栈序列表示成 \(\sum_{i\le x}c_iz^{a_i}\)，这样就变成两个区间 \(i\le x,j\le y\) 选 \(a_i+a_j=b\) 了。
我们需要对 \(i\) 扫描线的时候动态维护每个被加入的前缀 \(j\in[1,y]\) 的贡献之和。
对 \(i\) 分块一下，整块部分在每个块处 \(\mathcal O(n)\) 计算每个 \(j\) 被多少个前缀覆盖了，散块则对 \(j\) 扫描线在对应位置加入这些 \(i\) 即可。
时间复杂度 \(\mathcal O(n\sqrt m+nq)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,m,q,M,fa[MAXN],va[MAXN],a[MAXN],ps[MAXN],dc,ec,st[17][MAXN],dfn[MAXN];
vector <int> G[MAXN];
ll Z[MAXN];
void dfs1(int u,int fz) {dfn[u]=++dc,fa[u]=st[0][dc]=fz,ps[u]=++ec,a[ec]=va[u];for(int v:G[u]) if(v^fz) dfs1(v,u);a[++ec]=-va[u];
}
int cmp(int x,int y) { return dfn[x]<dfn[y]?x:y; }
int LCA(int x,int y) {int l=min(dfn[x],dfn[y])+1,r=max(dfn[x],dfn[y]),k=__lg(r-l+1);return cmp(st[k][l],st[k][r-(1<<k)+1]);
}
int b[MAXN],dl[MAXN],in[MAXN],lp[MAXN],rp[MAXN];
struct info { int x,y,z; } f[MAXN*10];
ll s[MAXN],t[MAXN];
void dfs2(int u,int fz) {++s[va[u]];for(int i=1;i<=q;++i) if(b[i]%2==0) Z[i]+=1ll*dl[u]*s[b[i]/2];for(int v:G[u]) if(v^fz) dfs2(v,u);--s[va[u]];
}
basic_string <int> ql[MAXN],qr[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i) cin>>va[i];for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);dfs1(1,0);for(int k=0;k<16;++k) for(int i=1;i+(2<<k)-1<=n;++i) st[k+1][i]=cmp(st[k][i],st[k][i+(1<<k)]);cin>>m;for(int i=1,u,v,w,x;i<=m;++i) {cin>>u>>v,w=LCA(u,v),--dl[u],--dl[v],++dl[w];f[++M]={u,u,1},f[++M]={v,v,1},f[++M]={w,w,1};f[++M]={u,v,2},f[++M]={u,w,-2},f[++M]={v,w,-2};if(w!=1) x=fa[w],f[++M]={x,x,1},f[++M]={u,x,-2},f[++M]={v,x,-2},f[++M]={w,x,2},++dl[x];}cin>>q;for(int i=1;i<=q;++i) cin>>b[i];for(int i=1,l,r;i<=M;++i) l=ps[f[i].x],r=ps[f[i].y],f[i].x=min(l,r),f[i].y=max(l,r);m=0,sort(f+1,f+M+1,[&](auto i,auto j){ return i.x^j.x?i.x<j.x:i.y<j.y; });for(int i=1;i<=M;++i) {if(f[i].x!=f[m].x||f[i].y!=f[m].y) m-=m&&!f[m].z,f[++m]=f[i];else f[m].z+=f[i].z;}dfs2(1,0);int B=2*n/sqrt(m)+1;for(int i=1;(i-1)*B+1<=2*n;++i) {lp[i]=(i-1)*B+1,rp[i]=min(i*B,2*n);fill(in+lp[i],in+rp[i]+1,i);}memset(s,0,sizeof(s));for(int i=1;i<=m;++i) ql[in[f[i].x]-1]+=i,qr[f[i].y]+=i;for(int i=2*n;i>=1;--i) {for(int x:qr[i]) {int r=f[x].x,l=lp[in[r]],w=f[x].z;for(int j=l;j<=r;++j) {if(a[j]>0) s[a[j]]+=w;else s[-a[j]]-=w;}}int o=a[i]<0?-1:1,u=a[i]*o;for(int j=1;j<=q;++j) if(b[j]>u) Z[j]+=o*s[b[j]-u];}memset(s,0,sizeof(s));for(int i=in[2*n];i;--i) {if(ql[i].size()) {memset(t,0,sizeof(t)); ll su=0;for(int x:ql[i]) t[f[x].y]+=f[x].z;for(int j=2*n;j;--j) {su+=t[j];if(a[j]>0) s[a[j]]+=su;else s[-a[j]]-=su;}}for(int j=lp[i];j<=rp[i];++j) {int o=a[j]<0?-1:1,u=a[j]*o;for(int k=1;k<=q;++k) if(b[k]>u) Z[k]+=o*s[b[k]-u];}}for(int i=1;i<=q;++i) cout<<Z[i]/2<<"\n";return 0;
}
I. [P8275] 262144 Revisited (4)
Problem Link
自然想到区间 dp，并且交换值域定义域记 \(f_{v,l}=\max \{r\mid dp_{l,r-1}\le v\}\)，那么 \(v\to v+1\) 就是 \(f_l\gets f_{f_{l}}\)。
首先 \(f\) 相同的值可以一起修改，并且猜测 \(f\) 总的修改次数较小，可以证明是 \(\mathcal O(n\log n)\) 的，直接线段树维护。
时间复杂度 \(\mathcal O(n\log^2n)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5,V=1e6+25,MAXS=1<<19|5;
int n,a[MAXN],b[MAXN],mx[MAXS],ad[MAXS];
void adt(int p,int k) { mx[p]+=k,ad[p]+=k; }
void psd(int p) { if(ad[p]) adt(p<<1,ad[p]),adt(p<<1|1,ad[p]),ad[p]=0; }
void psu(int p) { mx[p]=max(mx[p<<1],mx[p<<1|1]); }
void add(int ul,int ur,int k,int l=1,int r=n,int p=1) {if(ul<=l&&r<=ur) return adt(p,k);int mid=(l+r)>>1; psd(p);if(ul<=mid) add(ul,ur,k,l,mid,p<<1);if(mid<ur) add(ul,ur,k,mid+1,r,p<<1|1);psu(p);
}
int fd(int x) {int l=1,r=n,p=1,m;for(;l<r;mx[p<<1]>=x?(r=m,p<<=1):(l=m+1,p=p<<1|1)) m=(l+r)>>1,psd(p);return l;
}
int qy(int x) {int l=1,r=n,p=1,m;for(;l<r;x<=m?(r=m,p<<=1):(l=m+1,p=p<<1|1)) m=(l+r)>>1,psd(p);return mx[p];
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i) cin>>a[i],b[i]=i,add(i,i,i);stable_sort(b+1,b+n+1,[&](int x,int y){ return a[x]<a[y]; });ll s=0,z=0;vector <int> c,d;for(int v=0,j=1;v<=V;++v) {vector<array<int,3>>h;for(int x:c) {int l=fd(x),r=fd(x+1),w=qy(x);if(l<r&&w>x) s+=1ll*(r-l)*(w-x),d.push_back(w),h.push_back({l,r-1,w-x});}for(auto&o:h) add(o[0],o[1],o[2]);for(;j<=n&&a[b[j]]==v;++j) {add(b[j],b[j],1),++s,d.push_back(b[j]);if(b[j]<n) d.push_back(b[j]+1);}sort(d.begin(),d.end()),d.erase(unique(d.begin(),d.end()),d.end()),c.swap(d),d.clear();z+=1ll*n*(n+1)/2-s;}cout<<z<<"\n";return 0;
}
J. [P16381] Tunnels (3)
Problem Link
每层独立，分别二分即可。
问题是在每个位置进入下一层后续需要的询问次数不一样，因此要从下往上进行 dp 计算从每个点出发的询问次数。
实际上的结构就是每次把 \(x,y\) 合并成 \(\max(x,y)+1\)，求最小操作次数，考虑一个贪心：每次找 \(a_i\le \min(a_{i-1},a_{i+1})\)，把 \(a_i\) 和左右两侧中较小的一个合并即可。
直接用单调栈维护该过程即可线性。
时间复杂度 \(\mathcal O(nm)\)。
代码：
#include<bits/stdc++.h>
#include "tunnels.h"
using namespace std;
const int MAXN=5e7+5;
int q,ls[MAXN],rs[MAXN],b[5005][5005],f[MAXN];
short L[MAXN],R[MAXN]; bool a[5005][5005];
int mrg(int x,int y) {return f[++q]=max(f[x],f[y])+1,L[q]=L[ls[q]=x],R[q]=R[rs[q]=y],q;
}
int build(int l,int r) {static int g[5005],t;g[t=1]=l;for(int i=l+1;i<=r;++i) {while(t>1&&(f[g[t-1]]<=f[i]||f[g[t-1]]==f[g[t]])) g[t-1]=mrg(g[t-1],g[t]),--t;if(f[g[t]]>f[i]) g[++t]=i;else for(g[t]=mrg(g[t],i);t>1&&f[g[t-1]]==f[g[t]];) g[t-1]=mrg(g[t-1],g[t]),--t;}while(t>1) g[t-1]=mrg(g[t-1],g[t]),--t;return g[1];
}
void solve(int n,int m,int k,const vector<vector<bool>>&A) {for(int i=0;i<n;++i) for(int j=0;j<m;++j) a[i][j]=A[i][j];for(int i=n-1;~i;--i) for(int l=0,r;l<m;++l) if(!a[i][l]) {for(r=l;r+1<m&&!a[i][r+1];++r);int h=q+1;for(int j=l;j<=r;++j) if(!a[i+1][j]) L[++q]=j,R[q]=j,f[q]=f[b[i+1][j]];if(h>q) for(int j=l;j<=r;++j) a[i][j]=1;else for(int j=l,c=build(h,q);j<=r;++j) b[i][j]=c;l=r;}for(int i=0,x;i<n;++i) {for(x=b[i][k];L[x]<R[x];) {int t=R[ls[x]];if(t<k) x=investigate(t)?ls[x]:rs[x];else x=investigate(t+1)?rs[x]:ls[x];}goDeeper(k=L[x]);}
}
*K. [P15588] 飞扬的松鼠 2 (7)
Problem Link
首先 \(l_i\gets \max l[1,i],r_i\gets \min r[i,n]\) 使得 \(l,r\) 递增，把折线中每个 \(v\to v+1\) 的位置看成一组匹配，则每个 \(v\) 要匹配一个区间中的某个位置，并且匹配的位置递增。
注意到如果 \(x>y,v\in[l_x,r_x],v+1\in[l_y,r_y]\)，那么肯定有 \(v+1\in[l_x,r_x],v\in[l_y,r_y]\)，所以匹配位置递增的限制被去掉了。
此时变成一个二分图完美匹配问题，右部点带权值并且有黑白两种，要算黑点个数 \(k\) 为 \(0\sim h\) 的最小权匹配。
显然看成一个拟阵问题来解决，考虑如何计算，根据拟阵基交换定理可证明答案具有凸性，可以 wqs 二分。
考虑 wqs 二分中 \(\delta\) 从 \(-\infty\to +\infty\) 的过程，每次变化只会把一个白色元素变成黑色的，所以我们只要算出每对这样的变化元素，然后按差值排序即可构建凸壳。
计算的时候也可以模拟，从 \(k\) 最小的解出发，按权值从小大大考虑未选黑点，插入后把产生的环上的最大白点弹出，模拟 wqs 二分的过程可以证明其正确性。
直接用 Hall 定理判定二分图匹配，可以用线段树维护拟阵。
时间复杂度 \(\mathcal O(n\log n)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef array<int,2> pii;
const int MAXN=2e5+5,N=1<<18,MAXS=1<<19|5;
struct info { int vl,xl,vr,xr,z; };
info operator+(const info&a,const info&b) {info c{b.vl,b.xl,a.vr,a.xr,min({a.z,b.z,a.vl+b.vr})};if(a.vl<c.vl) c.vl=a.vl,c.xl=a.xl;if(b.vr<c.vr) c.vr=b.vr,c.xr=b.xr;return c;
}
int n,m,a[MAXN],b[MAXN],L[MAXN],R[MAXN];
info f[MAXS]; int zl[MAXS],zr[MAXS];
void adt(int p,int kl,int kr) { zl[p]+=kl,zr[p]+=kr,f[p].vl+=kl,f[p].vr+=kr,f[p].z+=kl+kr; }
void psd(int p) { adt(p<<1,zl[p],zr[p]),adt(p<<1|1,zl[p],zr[p]),zl[p]=zr[p]=0; }
void psu(int p) { f[p]=f[p<<1]+f[p<<1|1]; }
void init(int l=1,int r=n,int p=1) {f[p]={m,r,0,l,m};if(l==r) return ;int mid=(l+r)>>1;init(l,mid,p<<1),init(mid+1,r,p<<1|1);
}
void add(int ul,int ur,int kl,int kr,int l=1,int r=n,int p=1) {if(ul>ur) return ;if(ul<=l&&r<=ur) return adt(p,kl,kr);int mid=(l+r)>>1; psd(p);if(ul<=mid) add(ul,ur,kl,kr,l,mid,p<<1);if(mid<ur) add(ul,ur,kl,kr,mid+1,r,p<<1|1);psu(p);
}
info qry(int ul,int ur,int l=1,int r=n,int p=1) {if(ul<=l&&r<=ur) return f[p];int mid=(l+r)>>1; psd(p);if(ur<=mid) return qry(ul,ur,l,mid,p<<1);if(mid<ul) return qry(ul,ur,mid+1,r,p<<1|1);return qry(ul,ur,l,mid,p<<1)+qry(ul,ur,mid+1,r,p<<1|1);
}
array<int,2> tr[MAXS];
void upd(int x,pii o) {for(tr[x+=N]=o;x;x>>=1) tr[x>>1]=max(tr[x],tr[x^1]);
}
int qmx(int l,int r) {pii s={0,0};for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {if(~l&1) s=max(s,tr[l^1]);if(r&1) s=max(s,tr[r^1]);}return s[1];
}
void add(int x,int o) {add(x+1,n,o,0),add(x,n,0,-o);if(!b[x]) upd(x,o>0?pii{a[x],x}:pii{0,0});
}
vector<ll>fly(int H,vector<int>A,vector<int>B,vector<int>le,vector<int>ri) {n=A.size(),m=H,init();for(int i=1;i<=n;++i) a[i]=A[i-1],b[i]=B[i-1],L[i]=max(L[i-1],le[i-1]),R[i]=ri[i-1];vector <ll> z(m+1,-1);if(R[n]<m||L[n]>m) return z;L[n]=R[n]=m;for(int i=n-1;i;--i) {R[i]=min(R[i],R[i+1]);if(L[i]>R[i]) return z;}for(int i=1;i<=m;++i) {int x=lower_bound(R+1,R+n+1,i)-R,y=lower_bound(L+1,L+n+1,i)-L;if(x>y) return z;add(y+1,n,-1,0),add(1,x-1,0,-1);}vector <int> X,Y,O;for(int i=1;i<=n;++i) (b[i]?Y:X).push_back(i);sort(X.begin(),X.end(),[&](int i,int j){ return a[i]<a[j]; });sort(Y.begin(),Y.end(),[&](int i,int j){ return a[i]<a[j]; });int cy=0,ct=0; ll su=0;vector <ll> dp;for(int x:X) {add(x,1);if(f[1].z<0) add(x,-1);else su+=a[x],++ct;}for(int y:Y) {add(y,1);if(f[1].z<0) add(y,-1),O.push_back(y);else su+=a[y],++ct,++cy;}if(ct<m) return z;for(int y:O) {add(y,1);int l=qry(1,y).xl,r=qry(y,n).xr,x=qmx(l,r);if(x) dp.push_back(a[y]-a[x]),add(x,-1);else add(y,-1);}z[cy]=su,sort(dp.begin(),dp.end());for(ll o:dp) z[++cy]=su+=o;return z;
}
L. [P15456] 奇妙的机器 (4)
Problem Link
判定 \(v\) 是否合法，感觉上应该先算出 \(v_{\min},v_{\max}\)，那么我们从 \(v_{\max}\) 不断操作直到长度为 \(1\)，显然可以让 \(v\le 1\)，感觉上应该能让 \(v\) 连续变化。
可以证明只要存在一个 \(l\le i<r\) 使得 \(S_i\ne T_i\)，则 \(v\in [1,v_{\max}]\) 都合法，构造考虑把 \(i\) 以外的元素随便操作，然后操作 \(i\) 让 \(v\gets v-1\) 即可。
否则要求 \(v\equiv v_{\max}\pmod 2\)，这是显然的因为 \(\oplus S_i\) 不变。
求 \(v_{\max}\) 就是 \((1,x)\) 的全保留，然后 \((0,1),(0,x)\) 拼起来，容易写成半群信息线段树维护。
\(v=0\) 的情况就特判，首先 \(n\) 个元素合为一个时，最后两个元素贡献的情况是确定的，其他元素都能任意调整，构造平凡，也就是 \([l,r-2]\) 中有 \(S_i\ne T_i\) 必定合法，否则只要看 \([r-1,r]\) 能否合法即可。
时间复杂度 \(\mathcal O((n+q)\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5,N=1<<19;
string S,T;
int n,q,a[MAXN];
struct BIT {int tr[MAXN],s;void add(int x,int v) { for(;x<=n;x+=x&-x) tr[x]+=v; }int qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
} E,C;
int qc(int x) { return S[x]=='W'?0:(T[x]=='W'?1:2); }
void add(int x,int o) {if(S[x]=='W') C.add(x,o);if(S[x]!=T[x]) E.add(x,o);
}
bool chk0(int l,int r) {if(l==r) return a[l];if(r-l==1) return (a[l]&&a[r])||(S[r]==T[l]);if(E.qry(r-2)>E.qry(l-1)) return 1;int o=(C.qry(r-2)-C.qry(l-1))%2;if(!o) return chk0(r-1,r);return (S[r-1]=='W'&&S[r]=='B')||S[r]!=T[r-1];
}
struct info { int a[2],z[2]; } I={0,1,0,0},W[3],tr[N<<1|5];
info operator+(const info&u,const info&v) { return {v.a[u.a[0]],v.a[u.a[1]],u.z[0]+v.z[u.a[0]],u.z[1]+v.z[u.a[1]]}; }
void upd(int x) { for(tr[x+N]=W[a[x]],x=(x+N)>>1;x;x>>=1) tr[x]=tr[x<<1]+tr[x<<1|1]; }
int qry(int l,int r) {info sl=I,sr=I;for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {if(~l&1) sl=sl+tr[l^1];if(r&1) sr=tr[r^1]+sr;}return (sl+sr).z[0];
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>S>>T>>q,S=" "+S,T=" "+T,fill(tr,tr+(N<<1),I);W[0]={0,0,1,1},W[1]={1,0,0,1},W[2]={0,0,0,1};for(int i=1;i<=n;++i) a[i]=qc(i),add(i,1),upd(i);for(int o,l,r,c;q--;) {cin>>o>>l;if(o==2) {cin>>r>>c;if(c==0) cout<<(chk0(l,r)?"Yes\n":"No\n");else {int z=qry(l,r);if(c>z) cout<<"No\n";else cout<<(E.qry(r-1)>E.qry(l-1)||c%2==z%2?"Yes\n":"No\n");}} else add(l,-1),cin>>S[l]>>T[l],a[l]=qc(l),add(l,1),upd(l);}return 0;
}
*M. [P15992] 原题加强 2 (7)
Problem Link
相当于求 \(\max_{p,k} \{\sum_{x\in S}[x\bmod p=k]\}\)。
显然取 \(p=2\) 就能得到 \(\ge \dfrac n2\) 的答案，对于剩余的情况，我们就是要找大小超过一半的最大团。
首先我们可以把 \(p^3\le n\) 的 \((p,k)\) 暴力维护，复杂度 \(q\pi(\sqrt[3]n)\)，这样任意 \(|a_x-a_y|\) 只有 \(\le 2\) 个 \(>\sqrt[3]n\) 的质因子。
设元素个数为 \(m\)，我们只要考虑出现总数 \(\ge \dfrac{m^2}8\) 的每个质因子，然后 \(\mathcal O(m)\) 暴力统计即可。
考虑如何快速找到这些质因子，显然的做法就是只取特殊的一些 \((x,y)\)，一种较好的方法就是 \(4\) 个元素分一组，然后只考虑组内的元素对，根据凸性，出现次数最少的情况肯定是每组平分，此时出现次数 \(\ge \dfrac m4\)，不过出现次数总和 \(\le 3m\)，因此只有 \(\mathcal O(1)\) 个要检验的 \(p\)。
对于动态问题，我们考虑到集合变化量较小的时候要检验的 \(p\) 应该不会变化太大。
由于找一次 \(p\) 是 \(\mathcal O(m)\) 的，因此尝试一次性覆盖覆盖 \(\mathcal \Theta(m)\) 个操作。
具体来说，处理 \(p\) 的时候，那么进行接下来的 \(\dfrac m4\) 个操作期间，任何时候的最优解都有至少 \(\dfrac {3m}8\) 个元素在当前集合中。
\(8\) 个元素分一组，要求该质因子出现次数 \(\ge \dfrac {3m}8\)，出现次数总和 \(\le 7m\)，所以只有 \(\mathcal O(1)\) 个。
注意我们实际上要找的是包含 \(\ge \dfrac{3m}8\) 个元素的 \((p,k)\)，对每个 \(p\) 重新 \(\mathcal O(m)\) 暴力一下就行。
动态维护所有元素可以用双向链表。
时间复杂度 \(\mathcal O(n+q(\pi(\sqrt[3]V)))\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXV=1e7+5,MAXN=1e6+5,B=46;
int n,m,K,ct[B+5][B*10],st[B*10][3],pr[MAXN],pc,ic[MAXN],mx,q,tc,mp[MAXV][2];
int in[MAXV],L[MAXN],R[MAXN],w[MAXN],a[MAXN],vs[MAXV],vl[MAXV];
bool is[MAXV];
void upd(int&x,int o) {if(o>0) --ic[x],++ic[++x],mx=max(mx,x);else --ic[x],++ic[--x],mx-=!ic[mx];
}
void add(int x,int o) {q+=o;for(int i=1;i<=B;++i) upd(ct[i][x%pr[i]],o);for(int i=1;i<=K;++i) if(x%st[i][0]==st[i][1]) upd(st[i][2],o);
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=2;i<MAXV;++i) {if(!is[i]) pr[++pc]=i;for(int j=1;j<=pc&&i*pr[j]<MAXV;++j) {is[i*pr[j]]=1;if(i%pr[j]==0) break;}}for(int i=1;i<=B;++i) ic[0]+=pr[i];for(int i=B+1;i<=pc;++i) for(int j=pr[i];j<MAXV;j+=pr[i]) mp[j][!mp[j][1]]=i;vector<int>ys;cin>>n>>m,ys.reserve(B*10);for(int i=1,h=1,x,e;i<=m;++i) {cin>>x,w[i]=--x;if(in[x]) add(x,-1),L[R[in[x]]]=L[in[x]],R[L[in[x]]]=R[in[x]],in[x]=0;else add(x,1),in[x]=i,L[R[i]=R[0]]=i,L[R[0]=i]=0;if(i==h) {for(int j=1;j<=K;++j) --ic[st[j][2]],st[j][2]=0;h=i+max(1,q/4),e=max(1,q*3/8),q=K=0,++tc,ys.clear();for(int u=R[0];u;u=R[u]) a[++q]=w[u];for(int o=1;o<=q;o+=8) for(int l=min(o+7,q);l>=o;--l) for(int r=l-1;r>=o;--r) {for(int v:mp[abs(a[r]-a[l])]) if(v>B) {if(vs[v]<tc) vs[v]=tc,vl[v]=0;if(++vl[v]==e) ys.push_back(pr[v]);}}for(int o:ys) {++tc,e=max(e,2);for(int j=1,v;j<=q;++j) {if(vs[v=a[j]%o]<tc) vs[v]=tc,vl[v]=0;if(++vl[v]==e) st[++K][0]=o,st[K][1]=v;}for(int j=K;j&&st[j][0]==o;--j) ++ic[st[j][2]=vl[st[j][1]]],mx=max(mx,st[j][2]);}}cout<<mx<<"\n";}return 0;
}
N. [P16379] 后台 (2)
Problem Link
建图后变成能否从 \(u\to v\)，其中路径上边的 \(\sum x=X,\sum y=Y\)。
建出一棵生成树，然后取出加入每条非树边得到的环，我们要用这些环的边权和凑出一个指定的值。
考虑维护二维向量线性基，可以证明只要两个向量 \((a,b),(0,c)\) 即可，插入 \((x,y)\) 时用 exgcd 令 \(x\gets \gcd(a,x)\) 即可。
时间复杂度 \(\mathcal O(nm\log V+q)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
ll exgcd(ll a,ll b,ll&x,ll&y) {if(!b) return x=1,y=0,a;ll g=exgcd(b,a%b,y,x);return y-=a/b*x,g;
}
struct Bas {ll a,b,c;void ins(ll x,ll y) {if(!x) return c=__gcd(c,abs(y)),void();if(x<0) x=-x,y=-y;if(!a) return a=x,b=y,void();ll i,j,g=exgcd(a,x,i,j);c=abs(__gcd(c,(y*a-b*x)/g)),a=g,b=i*b+j*y;if(c) b=(b%c+c)%c;}bool qry(ll x,ll y) {if(!a) return !x&&(c?y%c==0:!y);if(x%a) return 0;y-=x/a*b;return c?y%c==0:!y;}
} B[MAXN];
char a[1005][1005];
int n,m,q,k,h,b[1005][1005];
void dfs1(int x,int y) {if(x<0||y<0||x>=n||y>=m||a[x][y]!='.'||b[x][y]) return ;b[x][y]=k,dfs1(x-1,y),dfs1(x+1,y),dfs1(x,y-1),dfs1(x,y+1);
}
struct Edge { int v,x,y; };
vector <Edge> G[MAXN];
int c[MAXN],dx[MAXN],dy[MAXN];
void dfs2(int u) {c[u]=h;for(auto e:G[u]) {if(!c[e.v]) dx[e.v]=dx[u]+e.x,dy[e.v]=dy[u]+e.y,dfs2(e.v);else B[h].ins(dx[u]+e.x-dx[e.v],dy[u]+e.y-dy[e.v]);}
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>m>>n;for(int i=m-1;~i;--i) for(int j=0;j<n;++j) cin>>a[j][i];for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(!b[i][j]&&a[i][j]=='.') ++k,dfs1(i,j);for(int i=0;i<n;++i) if(a[i][0]=='.'&&a[i][m-1]=='.') {G[b[i][0]].push_back({b[i][m-1],0,-1}),G[b[i][m-1]].push_back({b[i][0],0,1});}for(int i=0;i<m;++i) if(a[0][i]=='.'&&a[n-1][i]=='.') {G[b[0][i]].push_back({b[n-1][i],-1,0}),G[b[n-1][i]].push_back({b[0][i],1,0});}for(int i=1;i<=k;++i) if(!c[i]) ++h,dfs2(i);cin>>q;for(ll sx,sy,ex,ey;q--;) {cin>>sx>>sy>>ex>>ey;int si=(sx%n+n)%n,sj=(sy%m+m)%m,ei=(ex%n+n)%n,ej=(ey%m+m)%m;sx=(sx-si)/n,sy=(sy-sj)/m,ex=(ex-ei)/n,ey=(ey-ej)/m;int u=b[si][sj],v=b[ei][ej];cout<<(c[u]==c[v]&&B[c[u]].qry(ex-sx+dx[u]-dx[v],ey-sy+dy[u]-dy[v])?"Yes\n":"No\n");}return 0;
}
O. [P15949] JOI 国的节日 3 (2.5)
Problem Link
先算根的激活时间，那么每个点只要考虑被儿子激活的最早时间，这是经典 DDP 问题，平衡树维护轻儿子第 \(c-1,c\) 小元素，信息是 \(v\to \min(z,\max(v+x,y))\)。
如果要算上父亲的贡献就用类似换根的手法来计算，同样可以 DDP，把重儿子的答案用父亲算出，然后对每条重链就能快速算结果了。
时间复杂度 \(\mathcal O(q\log^2n)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1.5e5+5,N=1<<18;
const ll inf=1e18;
mt19937 rnd;
struct info { ll x,y,z; } O={0,0,inf}; //min(max(x+*,y),z)
info operator+(const info&u,const info&v) { return {u.x+v.x,min(inf,max(u.y+v.x,v.y)),min(max(v.y,u.z+v.x),v.z)}; }
struct Edge { int v,w,i; };
vector <Edge> E[MAXN];
int n,q,a[MAXN],fa[MAXN],siz[MAXN],hson[MAXN],rt[MAXN],fw[MAXN];
int top[MAXN],dfn[MAXN],rk[MAXN],bt[MAXN],at[MAXN],dc,st[MAXN];
ll f[MAXN];
struct Treap {int pr[MAXN],sz[MAXN],ls[MAXN],rs[MAXN],st[MAXN],tp;ll vl[MAXN];void psu(int p) { sz[p]=sz[ls[p]]+1+sz[rs[p]]; }void spiv(int u,ll k,int&x,int&y) {if(!u) return x=y=0,void();if(vl[u]<=k) return x=u,spiv(rs[u],k,rs[x],y),psu(x);else return y=u,spiv(ls[u],k,x,ls[y]),psu(y);}int mrg(int x,int y) {if(!x||!y) return x|y;if(pr[x]<pr[y]) return rs[x]=mrg(rs[x],y),psu(x),x;else return ls[y]=mrg(x,ls[y]),psu(y),y;}void ins(int&u,ll z) {int v=st[tp--],x,y;pr[v]=rnd(),sz[v]=1,ls[v]=rs[v]=0,vl[v]=z;spiv(u,z,x,y),u=mrg(x,mrg(v,y));}void ers(int&u,ll z) {int x,y,o,v;spiv(u,z-1,x,o),spiv(o,z,v,y);u=mrg(x,mrg(mrg(ls[v],rs[v]),y)),st[++tp]=v;}ll qry(int u,int k) {if(!k) return 0;if(k>sz[u]) return inf;while(1) {if(k<=sz[ls[u]]) u=ls[u];else if(k-=sz[ls[u]]+1) u=rs[u];else return vl[u];}}
} S;
struct zkw1 {info tr[N<<1|5];void init() { fill(tr,tr+(N<<1),O); }void upd(int x,info o) { for(tr[x+=N]=o,x>>=1;x;x>>=1) tr[x]=tr[x<<1|1]+tr[x<<1]; }info qry(int l,int r) {info sl=O,sr=O;for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {if(~l&1) sl=tr[l^1]+sl;if(r&1) sr=sr+tr[r^1];}return sr+sl;}
} F;
struct zkw2 {info tr[N<<1|5];void init() { fill(tr,tr+(N<<1),O); }void upd(int x,info o) { for(tr[x+=N]=o,x>>=1;x;x>>=1) tr[x]=tr[x<<1]+tr[x<<1|1]; }info qry(int l,int r) {info sl=O,sr=O;for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {if(~l&1) sl=sl+tr[l^1];if(r&1) sr=tr[r^1]+sr;}return sl+sr;}
} G;
ll qf(int x) { return F.qry(dfn[x],dfn[bt[x]]).z; }
void mf(int x) {ll w=fw[hson[x]],l,r;if(!a[x]) F.upd(dfn[x],{0,0,0}),G.upd(dfn[x],{w,w,w});else F.upd(dfn[x],{w,l=S.qry(rt[x],a[x]-1),r=S.qry(rt[x],a[x])}),G.upd(dfn[x],{w,l+w,r+w});
}
void dfs1(int u) {siz[u]=1;for(auto e:E[u]) if(e.v!=fa[u]) {fa[e.v]=u,fw[e.v]=e.w,at[e.i]=e.v,dfs1(e.v),siz[u]+=siz[e.v];if(siz[e.v]>siz[hson[u]]) hson[u]=e.v;}
}
void dfs2(int u,int up) {top[u]=up,dfn[u]=++dc,rk[dc]=u;if(hson[u]) dfs2(hson[u],up),bt[u]=bt[hson[u]];else bt[u]=u;for(auto e:E[u]) if(e.v!=hson[u]&&e.v!=fa[u]) {dfs2(e.v,e.v),S.ins(rt[u],f[e.v]=qf(e.v)+fw[e.v]);}mf(u);
}
void psh(int x) { if(x!=hson[fa[x]]) S.ers(rt[fa[x]],f[x]),S.ins(rt[fa[x]],f[x]=qf(x)+fw[x]); }
void upd(int x) { for(mf(x),x=top[x];x>1;x=fa[x],mf(x),x=top[x]) psh(x); }
ll qg(int x) {int tp=0;for(int u=x;u;u=fa[top[u]]) st[++tp]=u;ll z=inf;for(int u,v,i=tp;i;--i) {u=st[i];auto o=G.qry(dfn[top[u]],dfn[u]-1);z=min(o.z,max(z+o.x,o.y));if(u==x) break;S.ers(rt[u],f[v=top[st[i-1]]]);ll t=qf(hson[u])+fw[hson[u]],c=a[u]?min(S.qry(rt[u],a[u]),max(min(z,t),S.qry(rt[u],a[u]-1))):0;if(a[u]>1) c=min(c,max({z,t,S.qry(rt[u],a[u]-2)}));z=c+fw[v],S.ins(rt[u],f[v]);}return z;
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n,F.init(),G.init();for(int i=1;i<=n;++i) S.pr[i]=rnd(),S.st[++S.tp]=i;for(int i=1,u,v,w;i<n;++i) cin>>u>>v>>w,E[u].push_back({v,w,i}),E[v].push_back({u,w,i});for(int i=1;i<=n;++i) cin>>a[i];dfs1(1),dfs2(1,1),cin>>q;for(int o,x;q--;) {cin>>o>>x;if(o==1) cin>>a[x],upd(x);else if(o==2) cin>>fw[at[x]],psh(at[x]),upd(fa[at[x]]);else {ll h=qg(x),t=hson[x]?qf(hson[x])+fw[hson[x]]:inf;ll z=a[x]?min(S.qry(rt[x],a[x]),max(min(h,t),S.qry(rt[x],a[x]-1))):0;if(a[x]>1) z=min(z,max({h,t,S.qry(rt[x],a[x]-2)}));cout<<(z<inf?z:-1)<<"\n";}}return 0;
}