9.12 CSP 模拟 36
T1 博弈
如果路径上最小值数量为奇数，那么先手第一个取最小值必胜。如果是偶数，那么双方都尽量避免第一个取最小值，变成了删去最小值不能操作的必败，就是子问题，归纳发现先手必败当且仅当所有值的出现次数都是偶数。
关于偶数的统计想到异或哈希，由于重复路径异或后贡献消失，直接 DFS 而不是点分治。
哈希可以重编号后双哈希，使用哈希表代替 map 可以卡点分治的常数。
点击查看代码（正解）
int t;
int n;
struct edge{
int to,nxt,w;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v,int w){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,e[cnt].w=w;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt,e[cnt].w=w;
}
vector<int> V;
map<int,int> W;
int pw1[maxn],pw2[maxn];
int dis1[maxn],dis2[maxn];
map<pii,int> mp;
ll ans;
void dfs(int u,int fa){
ans-=mp[make_pair(dis1[u],dis2[u])];
++mp[make_pair(dis1[u],dis2[u])];
for(int i=head[u],v,w;i;i=e[i].nxt){
v=e[i].to,w=e[i].w;
if(v==fa) continue;
dis1[v]=dis1[u]^pw1[w],dis2[v]=dis2[u]^pw2[w];
dfs(v,u);
}
}
int main(){
srand((unsigned long long)&seed);
t=read();
while(t--){
n=read();
cnt=0;
for(int i=1;i<=n;++i) head[i]=0,dis1[i]=0,dis2[i]=0;
V.clear(),W.clear();
for(int i=1,u,v,w;i<n;++i){
u=read(),v=read(),w=read();
add_edge(u,v,w);
V.push_back(w);
}
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
random_shuffle(V.begin(),V.end());
pw1[0]=pw2[0]=1;
for(int i=0;i<V.size();++i){
W[V[i]]=i+1;
pw1[i+1]=1ll*pw1[i]*base1%mod,pw2[i+1]=1ll*pw2[i]*base2%mod;
}
for(int u=1;u<=n;++u){
for(int i=head[u];i;i=e[i].nxt){
e[i].w=W[e[i].w];
}
}
ans=1ll*n*(n-1)/2;
mp.clear();
dfs(1,0);
printf("%lld\n",ans);
}
return 0;
}
点击查看代码（卡常后点分治）
const int MOD=5e6+11;
int t;
int n;
struct edge{
int to,nxt,w;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v,int w){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,e[cnt].w=w;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt,e[cnt].w=w;
}
int cntW;
unordered_map<int,int> W;
int pw1[maxn],pw2[maxn];
ll ans;
int ct;
bool vis[maxn];
int siz[maxn],mxsiz[maxn],sumsiz;
void dfs_siz(int u,int fa){
siz[u]=1;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(vis[v]||v==fa) continue;
dfs_siz(v,u);
siz[u]+=siz[v];
}
}
inline void init(int u){
ct=0,sumsiz=siz[u];
}
void dfs_ct(int u,int fa){
mxsiz[u]=0;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(vis[v]||v==fa) continue;
dfs_ct(v,u);
mxsiz[u]=max(mxsiz[u],siz[v]);
}
mxsiz[u]=max(mxsiz[u],sumsiz-siz[u]);
if(!ct||mxsiz[u]<mxsiz[ct]) ct=u;
}
int dis1[maxn],dis2[maxn];
int hd[MOD+5],nxt[maxn];
ll Key[maxn];
int Val[maxn],tot;
int mark[MOD+5];
int NOW;
inline void insert(ll k){
int p=k%MOD+1;
hd[p]=(mark[p]==NOW)?hd[p]:0;
mark[p]=NOW;
for(int i=hd[p];i;i=nxt[i]){
if(Key[i]==k){
++Val[i];
return;
}
}
Key[++tot]=k,Val[tot]=1;
nxt[tot]=hd[p],hd[p]=tot;
}
inline int query(ll k){
int p=k%MOD+1;
hd[p]=(mark[p]==NOW)?hd[p]:0;
mark[p]=NOW;
for(int i=hd[p];i;i=nxt[i]){
if(Key[i]==k) return Val[i];
}
return 0;
}
ll st[maxn];
int top;
void calc(int u,int fa){
ans-=query(1ll*dis1[u]*mod+dis2[u]);
st[++top]=1ll*dis1[u]*mod+dis2[u];
for(int i=head[u],v,w;i;i=e[i].nxt){
v=e[i].to,w=e[i].w;
if(vis[v]||v==fa) continue;
dis1[v]=dis1[u]^pw1[w],dis2[v]=dis2[u]^pw2[w];
calc(v,u);
}
}
void solve(int u){
vis[u]=true;
tot=0,++NOW;
insert(0);
for(int i=head[u],v,w;i;i=e[i].nxt){
v=e[i].to,w=e[i].w;
if(vis[v]) continue;
dis1[v]=pw1[w],dis2[v]=pw2[w];
calc(v,0);
while(top){
insert(st[top]);
--top;
}
}
dfs_siz(u,0);
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(vis[v]) continue;
init(v);
dfs_ct(v,0);
solve(ct);
}
}
int main(){
pw1[0]=pw2[0]=1;
for(int i=1;i<=500000;++i) pw1[i]=1ll*pw1[i-1]*base1%mod,pw2[i]=1ll*pw2[i-1]*base2%mod;
t=read();
while(t--){
n=read();
ans=1ll*n*(n-1)/2;
cnt=0;
for(int i=1;i<=n;++i){
head[i]=0,vis[i]=false;
}
W.clear();
for(int i=1,u,v,w;i<n;++i){
u=read(),v=read(),w=read();
if(W[w]) w=W[w];
else{
++cntW;
W[w]=cntW,w=cntW;
}
add_edge(u,v,w);
}
dfs_siz(1,0);
init(1);
dfs_ct(1,0);
solve(ct);
printf("%lld\n",ans);
if(!t) exit(0);
}
return 0;
}
T2 跳跃
容易发现最后一定是在一个子段反复横跳，但可能无法一次到达这个子段，需要在前面一个子段反复横跳积累权值，以此类推，到达前面这个子段可能也需要在更前面反复横跳……
注意到上面这个操作的前提是每次横跳的子段和单调递增，那么只需要枚举最后一个子段就可以了，而固定了右端点，一定选择权值和最大的子段。
考虑一个 DP，设 \(f_i\) 为从 \(1\) 经过一系列操作到达 \(i\) 需要的最少次数，\(g_i\) 为在此基础上可以积累的最大权值和，注意由于每次横跳的子段和单调递增，因此越早到达后面的子段一定是更优的。
转移即枚举上一个子段右端点 \(j\)，设 \(s\) 为 \(j\) 作为右端点的最大子段和，设横跳了 \(p\) 次，\(sum\) 为从 \(j\) 对应子段的左端点移动到 \(i\) 的权值，那么要求 \(g_j+ps+sum\ge 0\)，可以解出 \(p\) 的最小值，同时要求 \(f_j+p\) 是偶数才可以下一次跳到 \(i\)。
有一些细节需要处理。
点击查看代码
int t;
int n,k;
int a[maxn],sum[maxn],mnid[maxn];
int f[maxn];
ll g[maxn];
ll ans;
int main(){
t=read();
while(t--){
n=read(),k=read();
for(int i=0;i<=n;++i) sum[i]=0,mnid[i]=0,f[i]=0,g[i]=0;
for(int i=1;i<=n;++i){
a[i]=read();
sum[i]=sum[i-1]+a[i];
if(sum[i]<=sum[mnid[i-1]]) mnid[i]=i;
else mnid[i]=mnid[i-1];
}
ans=0;
f[1]=0,g[1]=0;
for(int i=2;i<=n;++i){
if(sum[i]>=0) f[i]=1,g[i]=sum[i];
else{
f[i]=k+1,g[i]=0;
for(int j=1;j<mnid[i];++j){
if(f[j]==k+1) continue;
int now=sum[j]-sum[mnid[j]];
if(now<=0) continue;
if((f[j]&1)&&g[j]+now+sum[i]-sum[mnid[j]]>=0){
if(f[j]+2<f[i]) f[i]=f[j]+2,g[i]=g[j]+now+(sum[i]-sum[mnid[j]]);
else if(f[j]+2==f[i]) g[i]=max(g[i],g[j]+now+(sum[i]-sum[mnid[j]]));
}
else{
int p=(-(sum[i]-sum[mnid[j]])-g[j]-1)/now+1;
if((f[j]+p)&1) ++p;
if(f[j]+p+1<f[i]) f[i]=f[j]+p+1,g[i]=g[j]+1ll*p*now+(sum[i]-sum[mnid[j]]);
else if(f[j]+p+1==f[i]) g[i]=max(g[i],g[j]+1ll*p*now+(sum[i]-sum[mnid[j]]));
}
}
}
}
for(int i=1;i<=n;++i){
if(f[i]==k+1) continue;
ans=max(ans,g[i]+1ll*(k-f[i])*(sum[i]-sum[mnid[i]]));
}
printf("%lld\n",ans);
}
return 0;
}
T3 大陆
对每个节点 \(u\) 维护一个集合 \(S_u\) 表示还未分块的部分，每次枚举儿子 \(v\)，将 \(S_v\) 合并在一起，当合并后集合超过 \(B\) 后，将这部分划为一个块，首府设为 \(u\)，剩下的节点算上 \(u\) 上传到 \(u\) 的父亲。
这样每次上传的集合大小不超过 \(B\)，那么每个块大小不超过 \(2B\)。
最后根位置可能还剩余一些节点，也放入上一个首府为根的块，其大小不超过 \(3B\)。
点击查看代码
int n,B;
vector<int> E[maxn];
vector<int> S[maxn];
int a[maxn],b[maxn],tot;
void dfs(int u,int fa){
for(int v:E[u]){
if(v==fa) continue;
dfs(v,u);
for(int i:S[v]){
S[u].push_back(i);
}
S[v].clear();
S[v].shrink_to_fit();
if((int)S[u].size()>=B){
b[++tot]=u;
for(int i:S[u]) a[i]=tot;
S[u].clear();
S[u].shrink_to_fit();
}
}
S[u].push_back(u);
}
int main(){
n=read(),B=read();
for(int i=1,u,v;i<n;++i){
u=read(),v=read();
E[u].push_back(v),E[v].push_back(u);
}
dfs(1,0);
if(!tot) b[++tot]=1;
for(int i:S[1]) a[i]=tot;
printf("%d\n",tot);
for(int i=1;i<=n;++i) printf("%d ",a[i]);
printf("\n");
for(int i=1;i<=tot;++i) printf("%d ",b[i]);
printf("\n");
return 0;
}
T4 排列
循环移位操作等价于用 fhq-Treap 将两个区间拆出来交换顺序再合并进去。
那么就需要考虑如何维护子树信息。
思考一个更简单的问题：如何维护二元上升子序列？只需要维护每个子树的最小值 \(mn\) 和最大值 \(mx\)，合并时跨过子树产生的贡献就是左子树 \(mn\) 与根的较小值小于右子树 \(mx\) 与根的较大值。
那么维护三元上升子序列，就可能存在一侧子树贡献两个位置的情况，维护 \(pmn\) 表示子树内二元上升子序列中较大值的最小值，\(pmx\) 表示子树内二元上升子序列中较小值的最大值。
这样合并时跨过子树产生的贡献就是左子树的 \(pmn\) 小于右子树 \(mx\) 与根的较大值或是右子树的 \(pmx\) 大于左子树 \(mn\) 与根的较小值。
现在问题是如何维护 \(pmn\) 与 \(pmx\)，再继承两子树信息的基础上，需要考虑两子树各贡献一个的情况，注意到 \(pmn\) 一定是左子树 \(mn\) 与根的较小值贡献二元上升子序列中左侧的值，\(pmx\) 一定是是右子树 \(mx\) 与根的较大值贡献二元上升子序列中右侧的值，似乎是无法快速查找出另一个值的。
发现维护这两个信息的前提是子树内没有三元上升子序列，因此左子树中小于右子树 \(mx\) 与根的较大值的部分不存在二元上升子序列，同理，右子树中大于左子树 \(mn\) 与根的较小值的部分不存在二元上升子序列。换句话说，就是左子树中小于右子树 \(mx\) 与根的较大值的部分单调不升，右子树中大于左子树 \(mn\) 与根的较小值的部分也单调不升。
那么就可以直接进子树平衡树上二分了，对于 \(pmn\) 就是找右子树最右侧的大于的，\(pmx\) 就是找左子树最左侧的小于的。
时间复杂度 \(O(n\log^2 n)\)。
点击查看代码
int n,q;
struct fhq_Treap{
int rt,ch[maxn][2];
int val[maxn],pri[maxn];
int siz[maxn],mn[maxn],mx[maxn];
int pmn[maxn],pmx[maxn];
bool tag[maxn];
int st[maxn],top;
inline void input(){
val[1]=inf,val[n+2]=-inf;
for(int i=2;i<=n+1;++i) val[i]=read();
for(int i=1;i<=n+2;++i){
pri[i]=rand(1,1000000000);
siz[i]=1,mn[i]=mx[i]=val[i];
pmn[i]=inf,pmx[i]=-inf;
tag[i]=false;
}
}
inline int query_max(int x,int k){
while(1){
if(ch[x][0]&&mn[ch[x][0]]<k) x=ch[x][0];
else if(val[x]<k) return val[x];
else x=ch[x][1];
}
}
inline int query_min(int x,int k){
while(1){
if(ch[x][1]&&mx[ch[x][1]]>k) x=ch[x][1];
else if(val[x]>k) return val[x];
else x=ch[x][0];
}
}
inline void push_up(int x){
if(!ch[x][0]&&!ch[x][1]){
siz[x]=1,mn[x]=mx[x]=val[x];
pmn[x]=inf,pmx[x]=-inf;
tag[x]=false;
}
else if(!ch[x][1]){
siz[x]=siz[ch[x][0]]+1,mn[x]=min(mn[ch[x][0]],val[x]),mx[x]=max(mx[ch[x][0]],val[x]);
pmn[x]=pmn[ch[x][0]],pmx[x]=pmx[ch[x][0]];
tag[x]=tag[ch[x][0]]|(pmn[ch[x][0]]<val[x]);
if(!tag[x]){
if(mn[ch[x][0]]<val[x]){
pmn[x]=min(pmn[x],val[x]);
pmx[x]=max(pmx[x],query_max(ch[x][0],val[x]));
}
}
}
else if(!ch[x][0]){
siz[x]=siz[ch[x][1]]+1,mn[x]=min(mn[ch[x][1]],val[x]),mx[x]=max(mx[ch[x][1]],val[x]);
pmn[x]=pmn[ch[x][1]],pmx[x]=pmx[ch[x][1]];
tag[x]=tag[ch[x][1]]|(val[x]<pmx[ch[x][1]]);
if(!tag[x]){
if(val[x]<mx[ch[x][1]]){
pmn[x]=min(pmn[x],query_min(ch[x][1],val[x]));
pmx[x]=max(pmx[x],val[x]);
}
}
}
else{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1,mn[x]=min({mn[ch[x][0]],mn[ch[x][1]],val[x]}),mx[x]=max({mx[ch[x][0]],mx[ch[x][1]],val[x]});
pmn[x]=min(pmn[ch[x][0]],pmn[ch[x][1]]),pmx[x]=max(pmx[ch[x][0]],pmx[ch[x][1]]);
tag[x]=tag[ch[x][0]]|tag[ch[x][1]]|(pmn[ch[x][0]]<max(mx[ch[x][1]],val[x]))|(min(mn[ch[x][0]],val[x])<pmx[ch[x][1]]);
if(!tag[x]){
if(mn[ch[x][0]]<val[x]) pmn[x]=min(pmn[x],val[x]);
if(val[x]<mx[ch[x][1]]) pmx[x]=max(pmx[x],val[x]);
if(mn[ch[x][0]]<max(mx[ch[x][1]],val[x])){
pmx[x]=max(pmx[x],query_max(ch[x][0],max(mx[ch[x][1]],val[x])));
}
if(min(mn[ch[x][0]],val[x])<mx[ch[x][1]]){
pmn[x]=min(pmn[x],query_min(ch[x][1],min(mn[ch[x][0]],val[x])));
}
}
}
}
void dfs(int x){
if(!ch[x][0]&&!ch[x][1]) return;
if(ch[x][0]) dfs(ch[x][0]);
if(ch[x][1]) dfs(ch[x][1]);
push_up(x);
}
inline void build(){
top=0;
for(int i=1;i<=n+2;++i){
int now=top;
while(now&&pri[st[now]]>pri[i]) --now;
if(now) ch[st[now]][1]=i;
if(now!=top) ch[i][0]=st[now+1];
top=now;
st[++top]=i;
}
rt=st[1];
dfs(rt);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(pri[x]<pri[y]){
ch[x][1]=merge(ch[x][1],y);
push_up(x);
return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
push_up(y);
return y;
}
}
void split(int p,int k,int &x,int &y){
if(!p) x=0,y=0;
else{
if(siz[ch[p][0]]+1<=k) x=p,split(ch[p][1],k-(siz[ch[p][0]]+1),ch[x][1],y);
else y=p,split(ch[p][0],k,x,ch[y][0]);
push_up(p);
}
}
inline void solve(int l,int r,int k){
int a,b,c,d;
split(rt,r+1,c,d);
split(c,l,a,c);
split(c,r-l+1-k,b,c);
rt=merge(merge(merge(a,c),b),d);
if(tag[rt]) printf("YES\n");
else printf("NO\n");
}
}T;
int main(){
n=read();
T.input();
T.build();
q=read();
while(q--){
int l=read(),r=read(),k=read();
T.solve(l,r,k);
}
return 0;
}