\(\text{By DaiRuiChen007}\)
Round #5 - 2024.9.14
A. [P9906] Cover
Problem Link
题目大意
给定长度为 \(k\) 的序列，从一个点出发，每次向左或向右一步，共走 \(n\) 步，每个位置上显示最后一次被经过的时刻，求能生成多少合法序列。
数据范围：\(n,k\le 5000\)。
思路分析
注意到能到达的点一定是一段区间，可以倒序 dp，设 \(f_{i,j}\) 表示最后 \(n\sim j\) 步经过的范围是一个长度为 \(i\) 的区间，并且我们钦定第 \(j\) 步在某个位置上显示。
那么最后这一步一定在这个长度为 \(i\) 的区间的左端点或右端点上，因此 \(f_{i,j}\to f_{i+1,j-1},f_{i+1,j-i}\) 表示向哪个方向拓展一步。
但是我们可以走来回，因此 \(f_{i,j}\to f_{i+1,j'}\) 的转移实际上转移到了 \(f_{i+1,j'},f_{i+1,j'-2}\dots\)，后缀和一下即可。
答案就是 \(\sum (k-i+1)f_{i,j}\)，注意 \(i=1\) 时不能走来回。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5005,MOD=1e9+7;
ll f[MAXN],g[MAXN];
inline void add(ll &x,ll y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
signed main() {int n,k;scanf("%d%d",&n,&k);ll ans=0; f[n]=1;for(int i=1;i<k;++i) {memset(g,0,sizeof(g));for(int j=n;j>=1;--j) {add(g[j-1],f[j]);if(j>=i) add(g[j-i],f[j]);}memcpy(f,g,sizeof(f));for(int j=n;j>=1;--j) {if(i>1) add(f[j],f[j+2]);ans=(ans+f[j]*(k-i))%MOD;}}printf("%lld\n",ans);return 0;
}
B. [P10829] Tuple
Problem Link
题目大意
定义一个图是好的，当且仅当图上恰有一个点，或可以由三个大小相等的好图各选出一个点连出三元环得到。
给定一个 \(n\) 个点 \(m\) 条边的无向图，判定该图是否是好的。
数据范围：\(n\le 2\times 10^5,m\le 3\times 10^5\)。
思路分析
考虑如何刻画好的图，在无向图上不好处理问题，注意到这张图是边仙人掌，可以建出圆方树。
那么原图上的每个环对应一个方点，最特殊的显然是最后一次加入的环，即某个方点删去后整棵树变成大小相同的三部分，且每部分都是好的。
那么这个方点显然就是圆方树的重心，容易证明一张图是好的当且仅当其圆方树的点分树是完美三叉树。
实现的时候可以在建圆方树时直接判断每个边双联通分量大小是否为 \(3\)，点分治的时候要维护一下深度方便判定大小相等。
时间复杂度 \(\mathcal O(n+m)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int n,m,tot,dfn[MAXN],low[MAXN],dcnt,stk[MAXN],tp;
vector <int> G[MAXN],E[MAXN];
void link(int u,int v) { E[u].push_back(v),E[v].push_back(u); }
void tarjan(int u) {dfn[u]=low[u]=++dcnt,stk[++tp]=u;for(int v:G[u]) {if(!dfn[v]) {tarjan(v),low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]) {int k,c=1; link(u,++tot);do ++c,link(k=stk[tp--],tot); while(k^v);if(c!=3) puts("ne"),exit(0);}} else low[u]=min(low[u],dfn[v]);}
}
int qk(int x) {int c=0;for(;x>1;x/=3,++c) if(x%3) puts("ne"),exit(0);return c;
}
int siz[MAXN],cur[MAXN];
bool vis[MAXN];
bool dfs1(int u,int k) {int cnt=0; vis[u]=true;for(int v:E[u]) cnt+=!vis[v];if(cnt!=(k?3:0)) puts("ne"),exit(0);function<void(int,int)> dfs2=[&](int x,int fz) {siz[x]=1;for(int y:E[x]) if(!vis[y]&&y!=fz) dfs2(y,x),siz[x]+=siz[y];};dfs2(u,0);for(int v:E[u]) if(!vis[v]) {int rt=0,mx=siz[v];function<void(int,int)> dfs3=[&](int x,int fz) {cur[x]=mx-siz[x];for(int y:E[x]) if(!vis[y]&&y!=fz) {dfs3(y,x),cur[x]=max(cur[x],siz[y]);}if(!rt||cur[x]<cur[rt]) rt=x;};dfs3(v,u);if(!dfs1(rt,k-1)) puts("ne"),exit(0);}return true;
}
signed main() {scanf("%d%d",&n,&m),tot=n;for(int i=1,u,v;i<=m;++i) {scanf("%d%d",&u,&v);G[u].push_back(v),G[v].push_back(u);}for(int i=1;i<=n;++i) {sort(G[i].begin(),G[i].end());if(unique(G[i].begin(),G[i].end())!=G[i].end()) return puts("ne"),0;}tarjan(1);for(int i=1;i<=n;++i) if(!dfn[i]) return puts("ne"),0;int rt=0,mx=tot;function<void(int,int)> dfs3=[&](int x,int fz) {siz[x]=1;for(int y:E[x]) if(!vis[y]&&y!=fz) {dfs3(y,x),cur[x]=max(cur[x],siz[y]),siz[x]+=siz[y];}cur[x]=max(cur[x],mx-siz[x]);if(!rt||cur[x]<cur[rt]) rt=x;};dfs3(1,0);puts(dfs1(rt,qk(n))?"da":"ne");return 0;
}
C. [P10822] Subset
Problem Link
题目大意
给定 \(a_1\sim a_n\)，\(q\) 次询问 \([l,r]\) 有多少子区间本质不同颜色数为奇数。
数据范围：\(n,q\le 5\times 10^5\)。
思路分析
设 \(a_I\) 上一次出现为 \(pre_i\)，那么扫描线 \(i-1\to i\) 时就会把 \(l\in(pre_i,i]\) 范围的区间颜色数 \(+1\)。
维护奇偶性，我们要支持区间反转区间历史和。
类似区间加区间历史和，构造一个历史和标记，每个线段树节点维护：每次打历史标记时，当前节点的懒标记是处于反转还是未反转状态，对这两种情况分别记录次数即可。
信息合并和标记下传都是容易的。
时间复杂度：\(\mathcal O((n+q)\log n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+5;
int n,q;
struct SegmentTree {int sum[MAXN<<2],len[MAXN<<2];bool tg[MAXN<<2];int t0[MAXN<<2],t1[MAXN<<2];ll hsum[MAXN<<2];void adt(int p,int z0,int z1,int rv) {hsum[p]+=1ll*z0*sum[p]+1ll*z1*(len[p]-sum[p]);if(tg[p]) t0[p]+=z1,t1[p]+=z0;else t0[p]+=z0,t1[p]+=z1;if(rv) tg[p]^=1,sum[p]=len[p]-sum[p];}void psd(int p) { adt(p<<1,t0[p],t1[p],tg[p]),adt(p<<1|1,t0[p],t1[p],tg[p]),t0[p]=t1[p]=tg[p]=0; }void psu(int p) { sum[p]=sum[p<<1]+sum[p<<1|1],hsum[p]=hsum[p<<1]+hsum[p<<1|1]; }void init(int l=1,int r=n,int p=1) {len[p]=r-l+1;if(l==r) return ;int mid=(l+r)>>1;init(l,mid,p<<1),init(mid+1,r,p<<1|1);}void upd(int ul,int ur,int l=1,int r=n,int p=1) {if(ul<=l&&r<=ur) return adt(p,0,0,1),void();int mid=(l+r)>>1; psd(p);if(ul<=mid) upd(ul,ur,l,mid,p<<1);if(mid<ur) upd(ul,ur,mid+1,r,p<<1|1);psu(p);}ll qry(int ul,int ur,int l=1,int r=n,int p=1) {if(ul<=l&&r<=ur) return hsum[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);}
} T;
ll ans[MAXN];
int a[MAXN],p[MAXN];
vector <array<int,2>> Q[MAXN];
signed main() {ios::sync_with_stdio(false);cin>>n,T.init();for(int i=1;i<=n;++i) cin>>a[i];cin>>q;for(int i=1,l,r;i<=q;++i) cin>>l>>r,Q[r].push_back({l,i});for(int i=1;i<=n;++i) {T.upd(p[a[i]]+1,i),p[a[i]]=i,T.adt(1,1,0,0);for(auto z:Q[i]) ans[z[1]]=T.qry(z[0],i);}for(int i=1;i<=q;++i) cout<<ans[i]<<"\n";return 0;
}
*D. [P10882] Triangle
Problem Link
题目大意
给定 \(a_1\sim a_n\)，\(q\) 次询问 \(l,r\)，找出一组 \(l\le i<j<k\le r\) 满足存在三角形以 \(a_i,a_j,a_k\) 为三边边长，并最小化 \(a_i+a_j+a_k\)。
数据范围：\(n\le2.5\times 10^5,q\le5\times 10^5,V\le 10^7\)。
思路分析
考虑对值域倍增分块。
对于每个块 \(B_k=[2^k,2^{k+1})\)，处理每个询问 \(l,r\)，如果区间 \([l,r]\) 中有 \(\ge 3\) 个 \(B_k\) 中的元素，那么取出任意三个都能构成三角形，我们只要取出最小的三个即可。
对每个 \([l,r]\) 我们找出最小的 \(k\)，更新答案后弹出，如果其他情况想要更优，一定至少包含一个 \(<2^k\) 的元素。
我们发现，对于 \(i\in [0,k)\)，\([l,r]\) 中至多有 \(2\) 个 \(B_i\) 中的元素，因此 \([l,r]\) 中 \(<2^k\) 的元素数量是 \(\mathcal O(\log V)\) 级别的。
我们考虑最终的三角形中有多少个元素 \(<2^k\)。
如果有 \(\ge 2\) 个元素 \(<2^k\)，那么我们可以枚举中间的数，显然最大的数没有下界，一定是越小越好。
因此三角形最长的两条边排序后一定是相邻的，因此最长边的范围也在 \([0,2^k)\) 间，或者是 \(B_k\) 在 \([l,r]\) 中的最小元素。
那么我们只要考虑 \(\mathcal O(\log V)\) 个元素，设他们从小到大排序之后为 \(t_1\sim t_m\)，枚举 \(i\)，找到最小的 \(t_j>t_{i+1}-t_i\)，那么 \((t_i,t_{i+1},t_j)\) 构成三角形。
注意到 \(i\) 变大时，若 \(t_{i+1}-t_i\) 也变大，那么 \(t_j\) 也变大，三条边都不优，所以我们只要考虑 \(t_{i+1}-t_i\) 的前缀最小值，可以双指针线性维护。
实现代码的时候我们可以按 \(k\) 从小到大扫描，前缀和计算区间中有多少 \(\in B_k\) 的数，如果 \(\ge 3\) 个就要求区间前三小值，可以线段树维护，由于每个区间询问后直接弹出，这部分复杂度 \(\mathcal O(n\log V+q\log n)\)。
这样的数如果 \(\le 2\) 个，那么我们要把他们全找出来，找出 \(\ge l\) 的最小的一个，和 \(\le r\) 最大的一个，一定能找出所有的数，先加入较小值，最终的序列就已经有序了。
这部分总的复杂度为 \(\mathcal O((n+q)\log V)\)。
然后考虑 \(<2^k\) 的元素恰好有一个的情况，显然此时这个元素是最小值。
不妨设这个元素为 \(a_x\)，我们枚举这个 \(a_x\) ，反向考虑什么样的区间会枚举到 \(x\)。
设 $a_x $属于 \(B_i\)，容易发现如果某个询问区间 \([l,r]\) 经过 \(B_i\) 时没有找到 \(\ge 3\) 个数，\(a_x\) 才会 \(<2^k\)。
因此对每个 \(a_x\)，找出他左边和右边第二个和 \(a_x\) 同属 \(B_i\) 的元素 \(a_L,a_R\)，一个询问区间 \([l,r]\) 会枚举到 \(a_x\)，一定有 \(L<l\le r<R\)，所以对于 \(a_x\)，只要考虑 \([L,R]\) 这个区间即可。
对每个块 \(B_i\) 逐块处理，容易发现对于同一个块，每个 \(a_x\) 对应的区间大小总和是 \(\mathcal O(n)\) 级别的。
因此所有 \(a_x\) 对应的区间大小总和是 \(\mathcal O(n\log V)\) 级别的。
对于每个 \(a_x\)，我们就是要在 \([L,R]\) 中选出两个 \(>a_x\) 的数 \(a_i,a_j\)，满足 \(|a_i-a_j|<a_x\)，然后把 \((i,j,x)\) 看成一组支配对，最后从左到右扫描线一遍维护每个询问区间里面的最小支配对即可。
那么现在我们只需要将支配对数量优化到一个可以接受的量级，我们设 \(b_i=\left\lfloor\dfrac {a_i}{a_x}\right\rfloor\)，那么 \(|a_i-a_j|<a_x\) 的必要条件是 \(|b_i-b_j|\le 1\)。
如果 \(b_i=b_j\)，此时任意的一对 \(a_i,a_j\) 都是满足限制的，相当于最小的 \(a_i+a_j\)，这是经典支配对结论，我们对每个 \(b_i\) 维护后缀最小值单调栈。
考虑插入 \(a_i\) 时，栈内每个元素 \(a_j\) 是否会与 \(a_i\) 形成支配对，如果 \(a_j\ge a_i\)，那么 \(a_j\) 会被 \(a_i\) 弹出，可以把他们视为支配对，这样的支配对总数和区间长度成线性。
然后考虑所有 \(a_j<a_i\) 的点，由于他们在单调栈上，因此 \(a_j<a_k<a_i\) 时也有 \(j<k<i\)，那么 \((i,j)\) 显然不如 \((j,k)\)。
因此只有 \(a_j<a_i\) 且 \(j\) 最大的 \(a_j\) 可以与 \(a_i\) 形成支配对，这就是弹栈后剩余的栈顶，这样的支配对总数和区间长度也成线性。
然后考虑 \(|b_i-b_j|=1\) 的情况。
还是考虑支配对，不妨设 \(j<i\) 且 \(b_j=b_i-1\)，剩余的情况可以翻转区间 \([L,R]\) 做。
那么如果有两个 \(j,k\) 同时满足 \(b_j=b_k=b_i-1\)，那么 \(a_j,a_k\) 一定合法且更优。
因此支配对一定是 \([L,i)\) 中第一个 \(b_j=b_i-1\) 的 \(j\) 对应的 \(a_j\)。
这部分支配对总数和区间长度依然成线性。
因此所有支配对数量的总和是 \(\mathcal O(n\log V)\) 级别的，树状数组维护扫描线即可。
时间复杂度 \(\mathcal O(n\log V\log n+q\log V)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
typedef array<int,3> info;
const int MAXN=2.5e5+5,MAXQ=5e5+5,MAXV=1e7+5,inf=1e9;
const void chkmin(int &x,const int &y) { x=x<y?x:y; }
info operator +(info f,info g) {for(int x:f) for(int &y:g) if(y>x) swap(x,y);return g;
}
int n,q,a[MAXN],bl[MAXN],ql[MAXQ],qr[MAXQ],ans[MAXQ],cnt[MAXN],pre[MAXN],nxt[MAXN];
bool vis[MAXQ];
vector <int> arr[MAXQ];
struct zkwSegt {static const int N=1<<18;info tr[N<<1];void init(int k) {for(int i=0;i<N;++i) tr[i+N].fill(inf);for(int i=1;i<=n;++i) if(bl[i]==k) tr[i+N][0]=a[i];for(int i=N-1;i;--i) tr[i]=tr[i<<1]+tr[i<<1|1];}info qry(int l,int r) {info s{inf,inf,inf};for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {if(~l&1) s=s+tr[l^1];if(r&1) s=s+tr[r^1];}return s;}
} S;
void calc(int &s,const vector<int>&w) {int k=w.size(),i=1;while(i+1<k&&w[i-1]+w[i]<=w[i+1]) ++i;if(i+1>=k) return ;int j=i-1,lst=w[i+1]-w[i];while(j>0&&w[j-1]>lst) --j;chkmin(s,w[j]+w[i]+w[i+1]);for(++i;i+1<k;++i) if(w[i+1]-w[i]<lst) {for(lst=w[i+1]-w[i];j>0&&w[j-1]>lst;--j);chkmin(s,w[j]+w[i]+w[i+1]);}
}
vector <array<int,2>> M[MAXN],Q[MAXN];
void ins(int x,int y,int z) { M[max({x,y,z})].push_back({min({x,y,z}),a[x]+a[y]+a[z]}); }
vector <int> stk[MAXV];
int b[MAXN],pos[MAXV];
void gen(int id,int l,int r) {int x=a[id];for(int i=l;i<=r;++i) if(a[i]>x) b[i]=a[i]/x,stk[b[i]].clear();for(int i=l;i<=r;++i) if(a[i]>x) {vector<int>&s=stk[b[i]];while(s.size()&&a[s.back()]>=a[i]) ins(s.back(),id,i),s.pop_back();if(s.size()) ins(s.back(),id,i);s.push_back(i);}for(int i=l;i<=r;++i) if(a[i]>x) pos[b[i]]=pos[b[i]-1]=0;for(int i=l;i<=r;++i) if(a[i]>x) {int j=pos[b[i]-1];if(j&&x+a[j]>a[i]) ins(id,j,i);pos[b[i]]=i;}for(int i=l;i<=r;++i) if(a[i]>x) pos[b[i]]=pos[b[i]-1]=0;for(int i=r;i>=l;--i) if(a[i]>x) {int j=pos[b[i]-1];if(j&&x+a[j]>a[i]) ins(id,j,i);pos[b[i]]=i;}
}
struct FenwickTree {int tr[MAXN],s;void init() { fill(tr,tr+n+1,inf); }void upd(int x,int v) { for(;x;x&=x-1) tr[x]=min(tr[x],v); }int qry(int x) { for(s=inf;x<=n;x+=x&-x) s=min(s,tr[x]); return s; }
} T;
signed main() {ios::sync_with_stdio(false);cin>>n>>q;for(int i=1;i<=n;++i) cin>>a[i],bl[i]=__lg(a[i]);for(int i=1;i<=q;++i) cin>>ql[i]>>qr[i],ans[i]=inf;for(int k=0;k<24;++k) {vector <int> idx;S.init(k),memset(cnt,0,sizeof(cnt));for(int i=1;i<=n;++i) if(bl[i]==k) cnt[i]=1,idx.push_back(i);;for(int i=1;i<=n;++i) pre[i]=(bl[i]==k?i:pre[i-1]);for(int i=n;i>=1;--i) nxt[i]=(bl[i]==k?i:nxt[i+1]);for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1];for(int i=1;i<=q;++i) if(!vis[i]) {int w=cnt[qr[i]]-cnt[ql[i]-1];if(w<3) {if(w>1) {int x=nxt[ql[i]],y=pre[qr[i]];if(a[x]>a[y]) swap(x,y);arr[i].push_back(a[x]),arr[i].push_back(a[y]);} else if(w) arr[i].push_back(a[nxt[ql[i]]]);} else {info z=S.qry(ql[i],qr[i]);arr[i].push_back(z[0]),vis[i]=true;chkmin(ans[i],z[0]+z[1]+z[2]);}}int m=idx.size();for(int i=0;i<m;++i) gen(idx[i],i>1?idx[i-2]+1:1,i+2<m?idx[i+2]-1:n);}for(int i=1;i<=q;++i) calc(ans[i],arr[i]),Q[qr[i]].push_back({ql[i],i});T.init();for(int i=1;i<=n;++i) {for(auto z:M[i]) T.upd(z[0],z[1]);for(auto z:Q[i]) chkmin(ans[z[1]],T.qry(z[0]));}for(int i=1;i<=q;++i) {if(ans[i]==inf) cout<<"yumi!\n";else cout<<ans[i]<<"\n";}return 0;
}
Round #6 - 2024.9.15
A. [P10884] Increase
Problem Link
题目大意
给定 \(n\) 个元素，每个元素有高度和权值，求有多少个高度单调不降的子序列满足元素权值和 \(\ge k\)。
数据范围：\(n\le 40\)。
思路分析
考虑折半搜索，从前往后搜出在 \(x\) 处结尾的 LIS，从后往前搜出在 \(y\) 处开始的 LIS。
那么查询答案相当于在 \(a_x\le a_y\) 的 LIS 上查询有多少权值 \(\ge k-w\) 的序列。
可以离线下来二维数点，但直接暴力排序二分也能通过。
时间复杂度 \(\mathcal O(n^22^{n/2})\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=45,inf=1e9;
int n,m,a[MAXN],w[MAXN];
ll k,ans=0;
vector <ll> s[MAXN];
void dfs1(int i,int x,ll c) {if(i>n/2) return s[x].push_back(c);dfs1(i+1,x,c);if(a[i]>=a[x]) dfs1(i+1,i,c+w[i]);
}
void dfs2(int i,int x,ll c) {if(i<=n/2) {for(int j=0;j<=n/2;++j) if(a[j]<=a[x]) {ans+=s[j].end()-lower_bound(s[j].begin(),s[j].end(),k-c);}return ;}dfs2(i-1,x,c);if(a[i]<=a[x]) dfs2(i-1,i,c+w[i]);
}
signed main() {scanf("%d%lld",&n,&k);for(int i=1;i<=n;++i) scanf("%d%d",&a[i],&w[i]);dfs1(1,0,0);for(int i=1;i<=n/2;++i) sort(s[i].begin(),s[i].end());a[n+1]=inf;dfs2(n,n+1,0);printf("%lld\n",ans);return 0;
}
B. [P10240] Backpack
Problem Link
题目大意
给定 \(n\) 个元素，每个元素有权重 \(a_i\)，进行若干轮操作，每次选出最多的元素使得 \(\sum a_i\le m\)，多种方案选字典序最大一组方案，选出的元素都删除，求多少轮后所有元素被删空。
数据范围：\(n\le 50000\)。
思路分析
首先考虑怎么选出最多元素，显然会按从小到大的顺序贪心取出前 \(k\) 个元素。
然后考虑怎么确定一组解，可以逐位贪心，即先最大化标号最小元素的位置，可以二分一个 \(x\)，那么我们就要求 \([x,n]\) 范围内前 \(k\) 小元素和 \(\le m\)。
由于我们要动态删除元素，因此可以树状数组套值域线段树树，求出一组解的复杂度 \(\mathcal O(k\log^3n)\)。
由于 \(\sum k=n\)，因此总复杂度 \(\mathcal O(n\log ^3n)\)。
从小到大贪心求 \(k\) 可以直接 std::multiset 维护。
时间复杂度：\(\mathcal O(n\log^3n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=50005;
const ll inf=1e18;
int n,m,a[MAXN],id[MAXN],rk[MAXN],vals[MAXN];
struct Segt {static const int MAXS=MAXN*200;int ls[MAXS],rs[MAXS],siz[MAXS],tot;ll sum[MAXS];void ins(int u,int op,int l,int r,int &p) {if(!p) p=++tot;siz[p]+=op,sum[p]+=op*vals[u];if(l==r) return ;int mid=(l+r)>>1;if(u<=mid) ins(u,op,l,mid,ls[p]);else ins(u,op,mid+1,r,rs[p]);}ll qry(int k,int l,int r,vector<int>&P) {if(l==r) return vals[l];int mid=(l+r)>>1,c=0;for(int p:P) c+=siz[ls[p]];if(k<=c) {for(int&p:P) p=ls[p];return qry(k,l,mid,P);} else {ll s=0;for(int&p:P) s+=sum[ls[p]],p=rs[p];return qry(k-c,mid+1,r,P)+s;}}int rt[MAXN];void ins(int x,int u,int op) { for(;x;x&=x-1) ins(u,op,1,n,rt[x]); }ll qry(int k,int x) {int s=0; vector <int> P;for(;x<=n;x+=x&-x) s+=siz[rt[x]],P.push_back(rt[x]);if(s<k) return inf;return qry(k,1,n,P);}
} T;
multiset <int> A;
int solve() {int s=0,c=0;for(int i:A) {if(s+i>m) return c;s+=i,++c;}return c;
}
signed main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) scanf("%d",&a[i]),id[i]=i;sort(id+1,id+n+1,[&](int x,int y){ return a[x]<a[y]; });for(int i=1;i<=n;++i) rk[id[i]]=i,vals[i]=a[id[i]];for(int i=1;i<=n;++i) A.insert(a[i]),T.ins(i,rk[i],1);int cnt=0;for(;A.size();++cnt) {int k=solve(),rem=m;for(int i=1;i<=k;++i) {int l=1,r=n,p=0;while(l<=r) {int mid=(l+r)>>1;ll z=T.qry(k-i+1,mid);if(z<=rem) p=mid,l=mid+1;else r=mid-1;}A.erase(A.find(a[p])),T.ins(p,rk[p],-1),rem-=a[p];}}printf("%d\n",cnt);return 0;
}
C. [P10241] Subpath
Problem Link
题目大意
给定 \(n\) 个点的树，点有权值，求出路径上最长严格递增子序列的长度。
数据范围：\(n\le 10^5\)。
思路分析
先考虑如何求 \(u\) 子树内以 \(u\) 为结尾 / 开头的 LIS 长度 \(f_u,g_u\)。
可以考虑线段树合并，对每个 \(v\)，把 \(f_v/g_v\) 插在 \(a_v\) 上，线段树维护值域区间 \(\max\)，那么 \(f_u\) 就是子树 \([1,a_u)\) 范围内最大 \(f\) 再 \(+1\)，\(g\) 可以同理维护。
然后考虑如何在路径 \(\mathrm{LCA}\) 处维护最长 LIS。
假如 \(\mathrm{LCA}\) 并不在 LIS 上，相当于对每个 \(x\)，然后取出 \([1,x]\) 中最大的 \(f\) 和 \((x,\infty)\) 中最大的 \(g\) 加起来更新答案，可以看成 CDQ 分治的过程，那么只要在线段树合并时一边取左子树，一边取右子树更新即可。
如果 \(\mathrm{LCA}\) 在 LIS 上，那么相当于在两个子树内各查询出 \(f_u/g_u\) 再合并，这也是容易的。
时间复杂度 \(\mathcal O(n\log V)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int ans=0;
struct SegmentTree {int tot,ls[MAXN*32],rs[MAXN*32],f[MAXN*32],g[MAXN*32];void ins(int u,int x,int y,int l,int r,int &p) {if(!p) p=++tot;f[p]=max(f[p],x),g[p]=max(g[p],y);if(l==r) return ;int mid=(l+r)>>1;u<=mid?ins(u,x,y,l,mid,ls[p]):ins(u,x,y,mid+1,r,rs[p]);}void merge(int l,int r,int q,int &p) {if(!q||!p) return p|=q,void();f[p]=max(f[p],f[q]),g[p]=max(g[p],g[q]);if(l==r) return ;ans=max({ans,f[ls[p]]+g[rs[q]],f[ls[q]]+g[rs[p]]});int mid=(l+r)>>1;merge(l,mid,ls[q],ls[p]),merge(mid+1,r,rs[q],rs[p]);}int qry(int ul,int ur,int op,int l,int r,int p) {if(ul<=l&&r<=ur) return op?g[p]:f[p];int mid=(l+r)>>1,s=0;if(ul<=mid) s=max(s,qry(ul,ur,op,l,mid,ls[p]));if(mid<ur) s=max(s,qry(ul,ur,op,mid+1,r,rs[p]));return s;}
} T;
vector <int> G[MAXN];
int n,f[MAXN],g[MAXN],a[MAXN],rt[MAXN],V=1e9+1;
void dfs(int u,int fz) {f[u]=g[u]=1;for(int v:G[u]) if(v^fz) {dfs(v,u);int tf=T.qry(0,a[u]-1,0,0,V,rt[v])+1;int tg=T.qry(a[u]+1,V,1,0,V,rt[v])+1;ans=max({ans,tf+T.qry(a[u]+1,V,1,0,V,rt[u]),T.qry(0,a[u]-1,0,0,V,rt[u])+tg}); f[u]=max(f[u],tf),g[u]=max(g[u],tg);T.merge(0,V,rt[v],rt[u]);}T.ins(a[u],f[u],g[u],0,V,rt[u]);
}
signed main() {scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d",&a[i]);for(int i=1,u,v;i<n;++i) {scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);}dfs(1,0);ans=max({ans,T.f[rt[1]],T.g[rt[1]]});printf("%d\n",ans);return 0;
}
*D. [P8340] Express
Problem Link
题目大意
求 \(\{1,2,3,\dots,n\}\) 有多少个子集能用其子集和表出 \(1\sim n\) 中所有数。
数据范围：\(n\le 5\times 10^5\)。
思路分析
首先考虑如何求出一个集合中最小不可表示的元素，这是经典问题，找到排序后第一个 \(s_{i}+1<a_{i+1}\) 的位置，其中 \(s_i\) 是前缀和，那么答案就是 \(s_i+1\)。
因此我们可以考虑容斥，枚举 \(x\) 为第一次出现过这种情况的 \(s_i\)，那么相当于 \([1,x]\) 中元素的和为 \(x\)，并且其他元素在 \([x+2,n]\) 中选择，然后用一定的容斥使得 \(1\sim x\) 中不存在这样的不合法 \(s_i\)。
先考虑如何算出总方案数 \(f_x\) 表示 \([1,x]\) 中元素和为 \(x\) 的子集数量。
由于每个元素都不能相同，因此子集大小至多是 \(\mathcal O(\sqrt x)\) 级别的。
我们考虑把一个方案对应成一个杨表，即从大到小排列，第 \(k\) 行的宽度就是第 \(k\) 大元素的值。
那么这个杨表一共有 \(x\) 个网格，但至多 \(\mathcal O(\sqrt x)\) 行，那么每列的高度都只有 \(\mathcal O(\sqrt x)\) 种可能。
从大到小枚举列高 \(h\)，然后 \(f_i\to f_{i+kh}\)，其中 \(k>0\)，可以用完全背包的方式处理，由于 \(h\) 是 \(\mathcal O(\sqrt n)\) 级别，那么总复杂度是 \(\mathcal O(n\sqrt n)\)，可以在这个复杂度内求出 \(f_1\sim f_n\)。
然后考虑如何容斥，即我们要钦定所有 \(<x\) 的数 \(y\) 都不满足 \([1,y]\) 的和 \(=y\) 且 \(y+1\) 未被选。
那么对于 \(y<x\)，\(f_y\to f_x\) 的容斥系数就是 \([y+2,x]\) 中的元素组出 \(x-y\) 的方案数，再乘以 \(-1\)。
考虑类 CDQ 分治的过程维护贡献，但我们发现 \(2y>x\) 时 \(f_y\to f_x\) 的容斥系数一定为 \(0\)。
因此 CDQ 分治时 \(mid+1\sim r\) 的元素内部不存在贡献。
因此我们只要考虑 \([l,mid]\to (mid,r]\) 的转移。
维护在 \([y+2,x]\) 中选数的方案数，可以做一个类似上面的 dp。
枚举 \(h\) 即 \([y+2,x]\) 范围内的元素数量，那么加入的时候就是 \(g_{(y+1)h+y}\gets f_y\)，表示将 \([y+2,x]\) 范围内的元素都减去 \(y+1\)，然后在 \(g\) 上做类似 dp 过程即可。
最后 \(x\in (mid,r]\) 的 \(f_x\) 减去 \(g_x\) 就减去了这部分的贡献。
最终的答案是 \(2^n-\sum_{i<n} 2^{n-i-1}f_i\)。
时间复杂度 \(\mathcal O(n\sqrt n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5,B=1000;
int MOD,f[MAXN],g[MAXN],pw[MAXN];
inline void add(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
void dp(int n) {if(n==1) return ;dp(n>>1),memset(g,0,sizeof(g));for(int i=B;i;--i) {for(int j=0;j+(j+1)*i<=n;++j) add(g[j+(j+1)*i],f[j]);for(int j=n;~j;--j) g[j]=(j>=i?g[j-i]:0);for(int j=i;j<=n;++j) add(g[j],g[j-i]);}for(int j=n/2+1;j<=n;++j) if(g[j]) add(f[j],MOD-g[j]);
}
signed main() {int n;scanf("%d%d",&n,&MOD);for(int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*2%MOD;for(int i=B;i;--i) {for(int j=n;j>=i;--j) f[j]=f[j-i];f[i]=1;for(int j=i;j<=n;++j) add(f[j],f[j-i]);}f[0]=1,dp(n);int ans=pw[n];for(int i=0;i<n;++i) ans=(ans-1ll*f[i]*pw[n-i-1])%MOD;printf("%d\n",(ans+MOD)%MOD);return 0;
}
E. [P10103] Permutation
Problem Link
题目大意
\(q\) 组询问给定 \(n,m\)，求有多少 \(n\) 阶排列 \(p\) 满足 \(p_1\sim p_m>m\) 且所有 \(p_i\ne i\)。
数据范围：\(n,m,q\le 2\times 10^5\)。
思路分析
先在 \(m+1\sim n\) 中选出 \(m\) 个放到 \(p_1\sim p_m\) 上，变成一个子问题：剩下 \(n-m\) 个位置，\(n-2m\) 个元素不能放在自己对应的位置上，\(m\) 个元素没有任何限制。
因此可以设计状态 dp：\(f_{n,m}\) 表示 \(n\) 个不能放在自己对应位置上的元素，\(m\) 个无位置限制的元素，排列的方案数。
考虑分别消去一个有限制的元素和一个无限制的元素，根据组合意义处理。
先考虑一个无限制的元素如何填：
- 如果填在自己对应的位置上，那么转移到 \(f_{n,m-1}\)。
- 否则相当于这个元素被钦定了“不能放在自己位置上”的限制，变成一个有限制的元素，转移到 \(f_{n+1,m-1}\)。
因此 \(f_{n,m}=f_{n,m-1}+f_{n+1,m-1}\)，类似杨辉三角的递推，考虑 \(f_{n',m-k}\to f_{n,m}\) 的转移系数，我们得到：
然后考虑一个有限制的元素如何填：
- 填在一个无限制元素对应的位置上，那么这个无限制元素依然可以任意填，转移到 \(m\times f_{n-1,m}\)。
- 填在一个有限制元素对应的位置上，变成经典错拍，考虑这个元素是否和当前元素互换位置，转移到 \((n-1)(f_{n-1,m}+f_{n-2,m})\)。
因此 \(f_{n,m}=(m+n-1)f_{n-1,m}+(n-1)f_{n-2,m}\)。
那么考虑对 \(m\) 分块回答询问，取块长为 \(B\)，对于 \(m=kB\)，用第二个递推式，求出整行的 \(f_{0,m}\sim f_{n,m}\)。
然后对于一个 \(m=kB+r\) 其中 \(r\in[0,B)\) 的询问，用第一个递推式 \(\mathcal O(r)\) 计算答案。
时间复杂度 \(\mathcal O\left(qB+\dfrac{V^2}B\right)\)，取 \(B=\dfrac{V}{\sqrt q}\) 时最优。
时间复杂度 \(\mathcal O(V\sqrt q)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace FastMod {
typedef unsigned long long ull;
typedef __uint128_t uLL;
ull b,m;
inline void init(ull B) { b=B,m=ull((uLL(1)<<64)/B); }
inline ull mod(ull a) {ull q=((uLL(m)*a)>>64),r=a-q*b;return r>=b?r-b:r;
}
};
#define o FastMod::mod
const int MAXN=2e5+5,B=450,MOD=998244353,N=2e5;
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=o(a*a),b>>=1) if(b&1) s=o(s*a); return s; }
ll fac[MAXN],ifac[MAXN],f[MAXN],C[B+5][B+5],ans[MAXN];
vector <array<int,3>> Q[MAXN];
signed main() {FastMod::init(MOD);for(int i=fac[0]=ifac[0]=1;i<=N;++i) ifac[i]=ksm(fac[i]=o(fac[i-1]*i));int q; scanf("%d",&q);for(int i=1,n,m;i<=q;++i) {scanf("%d%d",&n,&m);if(n-m<m) ans[i]=0;else ans[i]=o(fac[n-m]*ifac[n-2*m]),Q[m/B].push_back({n-2*m,m,i});}for(int i=0;i<=B;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=o(C[i-1][j]+C[i-1][j-1]);for(int x=0;x*B<=N;++x) if(Q[x].size()) {int M=x*B;f[0]=fac[M],f[1]=o(M*fac[M]);for(int n=2;n<=N;++n) f[n]=o((n+M-1)*f[n-1]+(n-1)*f[n-2]);for(auto z:Q[x]) {int n=z[0],m=z[1],k=m-M; ll s=0;for(int i=0;i<=k;++i) s=o(s+f[n+i]*C[k][i]);ans[z[2]]=o(ans[z[2]]*s)%MOD;}}for(int i=1;i<=q;++i) printf("%lld\n",ans[i]);return 0;
}
*F. [P10107] Distance
Problem Link
题目大意
给定 \(n\) 个点的有根树，点有点权，\(q\) 次询问 \(u,k\)，求出所有 \(u\) 子树内距离 \(u\) 不超过 \(k\) 的点 \(v\)，\(a_v\oplus\mathrm{dis}(u,v)\) 的和。
数据范围：\(n,q\le 10^6\)。
思路分析
考虑刻画子问题，注意到这个问题的子问题不太可能被一个子树内的信息描述，而是形如同层内一些节点的子树信息的合并。
又因为这题要处理的信息和距离的二进制异或有关，这启示我们用倍增一类自带二进制结构的算法刻画信息。
因此我们可以考虑 \(f(u,k)\) 表示所有和 \(u\) 同层且 dfn 序小于等于 \(u\) 的点的子树中，深度 \(\le d_u+2^k\) 的点的答案和。
那么 \(f(u,k)\gets f(u,k-1)+f(dw_{u,k-1},k-1)\)，其中 \(dw_{u,k-1}\) 表示深度为 \(d_u+2^{k-1}\) 的节点中，dfn 序 \(<\mathrm{dfn}(u)+\mathrm{siz}(u)\) 的最后一个点，也可以简单理解为 \(u\) 子树内最“靠右”的节点。
由于 \(f(u,k)\) 自带二进制位上的信息，因此我们只要处理距离的第 \(2^{k-1}\) 位上的变化量，即给每个 \(f(dw_{u,k-1},k-1)\) 里的元素贡献异或上 \(2^{k-1}\)。
那么我们要计数 \(f(dw_{u,k-1},k-1)\) 对应的这个范围内，有多少个 \(a_v\) 的 \(2^{k-1}\) 位为 \(0\)，多少个为 \(1\)，事实上我们只关心这两种元素的数量差。
如果暴力设 \(G(u,k,d)\) 表示 \(f(u,k)\) 对应范围内，\(a_v\) 的第 \(d\) 个二进制位为 \(0\) 的元素数量减去为 \(1\) 的元素数量，这可以类似倍增转移，但此时信息总量是 \(\mathcal O(n\log^2n)\) 级别的。
考虑优化，很显然 \(u,d\) 三维是必须记录的，那么考虑去除 \(k\) 一维的影响。
记 \(g(u,d)=G(u,\infty,d)\)，即和 \(u\) 同层且 dfn 序不超过 \(u\) 的每个点的整个子树中，\(a_v\) 的第 \(d\) 位等于 \(0\) 的数量减去等于 \(1\) 的数量。
那么原本的 \(G(u,k,d)=g(u,d)-g(dw_{u,k},d)\)，即一个类似差分的过程。
那么 \(g\) 的转移可以看成一个类似二维前缀和的过程，记 \(pre_u\) 表示和 \(u\) 同层的点中最后一个 dfn 序小于 \(u\) 的。
那么不难得到转移：\(g(u,d)=g(dw_{u,0},d)+g(pre_u,d)-g(dw_{pre_u,0},d)+[a_u\operatorname{AND} 2^d=z]\)，即分别从 \(u\) 的“下方”和“右方”转移，然后容斥。
查询答案可以做一些类似的过程，每次考虑最高位的影响，实际上每个最高位都只会影响深度的一段后缀，也可以用 \(g\) 算出其贡献。
时间复杂度 \(\mathcal O((n+q)\log n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
vector <int> G[MAXN];
int n,q,a[MAXN],lst[MAXN],dep[MAXN],pre[MAXN],dw[MAXN][20],g[MAXN][20];
ll f[MAXN][20];
void dfs(int u,int fz) {dep[u]=dep[fz]+1,pre[u]=lst[dep[u]],lst[dep[u]]=u;dw[u][0]=dw[pre[u]][0];for(int v:G[u]) if(v^fz) dfs(v,u),dw[u][0]=v;for(int k=1;k<20;++k) dw[u][k]=dw[dw[u][k-1]][k-1];for(int k=0;k<20;++k) {g[u][k]=g[dw[u][0]][k]+g[pre[u]][k]-g[dw[pre[u]][0]][k]+(a[u]>>k&1?-1:1);}f[u][0]=a[u]+f[pre[u]][0];for(int k=1;k<20;++k) {int v=dw[u][k-1];f[u][k]=f[u][k-1]+f[v][k-1]+(1ll<<(k-1))*(g[v][k-1]-g[dw[u][k]][k-1]);}
}
ll qf(int u,int z) {int v=u; ll s=0; ++z;for(int k=19;~k;--k) if(z>>k&1) v=dw[v][k];for(int k=19;~k;--k) if(z>>k&1) {s+=f[u][k]+(1ll<<k)*(g[dw[u][k]][k]-g[v][k]),u=dw[u][k];}return s;
}
signed main() {ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;++i) cin>>a[i];for(int u=2,v;u<=n;++u) cin>>v,G[u].push_back(v),G[v].push_back(u);dfs(1,0),cin>>q;for(int x,k;q--;) cin>>x>>k,cout<<qf(x,k)-qf(pre[x],k)<<"\n";return 0;
}
Round #7 - 2024.9.16
A. [P10812] Factor
Problem Link
题目大意
给定 \(1\sim n\) 数轴，每个位置至多经过一次，不可超出 \([1,n]\)，每次可以从 \(u\) 走到 \(u-1,u+1\) 或 \(u\) 的因子，求有多少 \(n\to 1\) 的路径。
数据范围：\(n\le 5000\)。
思路分析
如果不存在 \(u\to u+1\) 的操作，那么直接 dp 并没有后效性。
如果存在这种操作，我们就要将若干操作合并，我们以每次 \(u\) 能使减少的操作为状态分段进行 dp。
即 \(f_{u,v}\) 表示当前路径上一步是 \(v\to u\)，并且 \(v>u\) 的方案数。
那么转移要么直接向 \(u-1\) 移动成 \(f_{u-1,u}\)，要么枚举 \(x\in[u,v)\) 并转移到 \(x\) 的因数上。
我们可以对所有 \(u\) 做后缀和，那么每个从 \(x\) 向因数移动的所有转移都可以一次性处理掉，那么总转移数是均摊调和的。
时间复杂度 \(\mathcal O(n^2\log n)\) 。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
vector <int> fac[MAXN];
int n,MOD,f[MAXN][MAXN];
inline void add(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
signed main() {scanf("%d%d",&n,&MOD);for(int i=1;i<=n;++i) for(int j=i;j<=n;j+=i) fac[j].push_back(i);f[n][n+1]=1;for(int i=n;i>1;--i) {int s=0;for(int j=n;j>=i;--j) {add(s,f[i][j+1]);for(int k:fac[j]) if(k<i) add(f[k][i],s);}add(f[i-1][i],s);}int s=0;for(int i=1;i<=n+1;++i) add(s,f[1][i]);printf("%d\n",s);return 0;
}
B. [P10674] Subgraph
Problem Link
题目大意
给定 \(n\) 个点 \(m\) 条边的无向图，求有多少点集对 \((S,T)\) 使得每个 \(S\) 中元素都在某两个 \(T\) 中元素的某条简单路径上。
数据范围：$n\le 5\times 105,m\le106 $。
思路分析
对每个 \(T\)，求出其内部所有路径并构成的点集 \(V(T)\)，那么 \(S\) 的选法就是 \(2^{|V(T)|}\) 种方案。
考虑刻画 \(f(T)\)，容易发现建出原图的圆方树，那么所有 \(T\) 中节点所在的方点生成的斯坦纳树上的点都在 \(V(T)\) 中，如果是方点，那么其对应的所有圆点都在 \(V(T)\) 中。
考虑在方点处统计权值，对于一个大小为 \(C\) 的点双连通分量，设其权值为 \(2^{C-1}\)，即圆方树上儿子个数。
那么对于斯坦纳树的根，如果其是圆点，那么没有将这个点考虑在 \(V(T)\) 中，否则没有将其父亲对应的圆点考虑进 \(V(T)\) 中，因此答案最后 \(\times 2\) 再加上 \(T=\varnothing\) 的情况即可。
dp 时设 \(f_u\) 表示 \(u\) 子树内至少有一个点被选入 \(T\) 时的权值和，即钦定 \(u\) 子树外选点后的答案。
但是我们在统计点 \(u\) 作为树根的权值的时候要钦定至少两棵子树被选，做一个简单背包即可。
时间复杂度 \(\mathcal O(n+m)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
ll dp[MAXN],ans,pw[MAXN];
vector <int> G[MAXN],E[MAXN];
void link(int x,int y) { E[x].push_back(y),E[y].push_back(x); }
int n,m,k,low[MAXN],dfn[MAXN],dcnt,stk[MAXN],tp,w[MAXN];
bool ins[MAXN];
void tarjan(int u) {ins[stk[++tp]=u]=true,dfn[u]=low[u]=++dcnt;for(int v:G[u]) {if(!dfn[v]) {tarjan(v),low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]) {link(++k,u);while(ins[v]) link(stk[tp],k),++w[k],ins[stk[tp--]]=false;}} else low[u]=min(low[u],dfn[v]);}
}
void dfs(int u,int fz) {if(E[u].size()==1&&fz!=0) return ++ans,dp[u]=1,void();ll g[3]={1,0,0};for(int v:E[u]) if(v^fz) {dfs(v,u),g[2]=(g[2]*(dp[v]+1)+g[1]*dp[v])%MOD,g[1]=(g[1]+g[0]*dp[v])%MOD;}if(u>n) ans=(ans+g[2]*pw[w[u]])%MOD,dp[u]=(g[2]+g[1])*pw[w[u]]%MOD;else ans=(ans+2*g[2]+g[1]+g[0])%MOD,dp[u]=(2*g[2]+2*g[1]+g[0])%MOD;
}
signed main() {scanf("%d%d",&n,&m),k=n;for(int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*2%MOD;for(int i=1,u,v;i<=m;++i) {scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);}tarjan(1),dfs(1,0);printf("%lld\n",(2*ans+1)%MOD);return 0;
}
C. [P10682] Xor
Problem Link
题目大意
给定 \(n\) 个点 \(m\) 条边的 DAG，求有多少种给每条边赋 \(0/1\) 权值的方式使得任意两条起终点相同的路径权值和 \(\bmod 2\) 都同余。
数据范围：\(n,m\le 400\)。
思路分析
很显然题目的要求就是对于任意两条 \(u\to v\) 的路径，路径上所有边权异或和为 \(0\)，可以用高斯消元求解。
由于本题全填 \(0\) 肯定是一组解，因此可以直接维护，不需要特判一些 Corner Case。
那么我们只要优化限制组数即可。
对每个起点 \(u\) 分别考虑，根据经典结论，先求出一棵以 \(u\) 为根的外向 dfs 树，设树上 \(u\to v\) 的路径为 \(T_u\)，那么只要考虑恰经过一条非树边的环。
即对于一条非树边 \(x\to y\)，我们只要求 \(T_x\oplus T_y\oplus w(x\to y)=0\)，并且不难证明这是充分的。
对于任意一条路径，找到其中的第一条非树边 \(x\to y\)，根据限制，可以把到 \(y\) 的路径等效成 \(T_y\)，递归进行此过程即可证明该路径合法。
那么此时总共只有 \(\mathcal O(nm)\) 条限制，暴力插入并用 bitset 优化高斯消元维护。
时间复杂度 \(\mathcal O\left(\dfrac{nm^3}\omega\right)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=405,MOD=1e9+7;
int n,m;
struct Edge { int v,id; };
vector <Edge> G[MAXN];
bool vis[MAXN];
bitset <MAXN> w,d[MAXN],x[MAXN];
void ins() {for(int i=1;i<=m;++i) if(w[i]) {if(!x[i].any()) return x[i]=w,void();else w^=x[i];}
}
void dfs(int u) {vis[u]=true;for(auto e:G[u]) {if(!vis[e.v]) d[e.v]=d[u],d[e.v].set(e.id),dfs(e.v);else w=d[u],w^=d[e.v],w.flip(e.id),ins();}
}
signed main() {scanf("%d%d",&n,&m);for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back({v,i});for(int i=1;i<=n;++i) {for(int u=1;u<=n;++u) d[u].reset(),vis[u]=false;dfs(i);}int ans=1;for(int i=1;i<=m;++i) if(!x[i].any()) ans=ans*2%MOD;printf("%d\n",ans);return 0;
}
*D. [P11051] Range
Problem Link
题目大意
给定 \(n\) 个点的树，每个点有点权 \(w_i\)，\(q\) 次询问 \(L,R\)，构造一组 \(c_i\) 使得每个子树内 \(c_i\) 的和都在 \([0,1]\) 之间，最小化 \(\sum|c_i|w_i\)。
数据范围；\(n\le 2\times 10^5,q\le 10^5\)。
思路分析
先从 \(w_i=1\) 的情况开始分析，此时在哪里填 \(c\) 没有区别，只关心总和。
自下而上地开始填 \(c_i\)，首先在每个叶子上都有 \(c_i=L\)，在此之后，每个点的子树和都 \(\ge L\)，我们只要给一些非叶子结点的 \(c\) 设为负数以保证其总和 \(\le R\)，容易证明减到 \(<L\) 是不优的。
观察根节点处的变化量，设原有 \(k\) 个叶子，那么要让根节点合法，整棵树的变化量至少为 \(\max(0,kL-R)\)。
不难证明这个界是可以取到的，可以每个 \(>R\) 的节点处减到 \(R\)，可以证明这样不会有冗余操作。
然后考虑 \(w_i\in\{0,1\}\) 的情况，容易发现此时我们能在 \(w_i=0\) 的点上任意操作，因此我们一定能在每个 \(w_i=0\) 的点上把子树和调整到 \(L\)。
这相当于把每个 \(w_i=0\) 的点看成叶子，然后对每个连通块分别求解答案再求和。
设有 \(k\) 个叶子的连通块有 \(f_k\) 个，答案就是 \(\sum_k f_k\times \max(0,kL-R)\)，求出第一个 \(kL>R\) 的位置维护 \(f_k\) 和 \(k\times f_k\) 的后缀和即可快速计算答案。
然后考虑一般的情况，由于我们已经会解决 \(w_i\in\{0,1\}\) 的情况了，因此不妨猜测更一般的情况可以向这种情况规约。
对每个 \(x\)，将 \(w_i>x\) 的点看成 \(1\)，\(w_i\le x\) 的点看成 \(0\)，然后对每个 \(x\) 求出答案再相加，可以根据本题的直接贪心过程证明之。
依然考虑维护 \(\sum f_k\)，设 \(w_1\sim w_n\) 是递增的，那么我们就要依次删除 \(1\sim n\)，删除 \(1\sim i\) 后的一个叶子数为 \(k\) 的连通块对 \(f_k\) 的贡献就是 \(w_{i+1}-w_i\)。
首先我们肯定转成倒序插入节点，可以用并查集维护产生和删除的每个连通块。
并且可以考虑差分，即一个连通块在插入 \(x\) 时刻生成，就对 \(f_k\) 产生 \(+w_x\) 贡献，在插入 \(y\) 时刻消失，就对 \(f_k\) 产生 \(-w_y\) 贡献。
那么这样就可以维护出所有 \(f_k\) 并计算答案，最终答案记得加上 \(L\) 倍叶子权值的和。
时间复杂度 \(\mathcal O(n\log n+q)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
vector <int> G[MAXN];
int n,w[MAXN],fa[MAXN],dsu[MAXN],siz[MAXN];
bool vis[MAXN];
ll cnt[MAXN],s1[MAXN],s2[MAXN],clf;
int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
void add(int x,int c,int v) { cnt[siz[x]]-=v,cnt[siz[x]+=c]+=v; }
void merge(int x,int y,int v) { dsu[y]=x,cnt[siz[y]]-=v,add(x,siz[y],v); }
void ins(int x) {vis[x]=true;if(fa[x]&&vis[fa[x]]) add(find(fa[x]),-1,w[x]);for(int y:G[x]) {if(!vis[y]) add(x,1,w[x]);else merge(x,y,w[x]);}if(vis[fa[x]]) merge(find(fa[x]),x,w[x]);
}
void init(vector <int> P,vector <int> W) {n=W.size(); vector <int> ord;for(int i=1;i<=n;++i) w[i]=W[i-1],ord.push_back(i),dsu[i]=i;for(int i=2;i<=n;++i) G[fa[i]=P[i-1]+1].push_back(i);for(int i=1;i<=n;++i) if(G[i].empty()) G[i].push_back(0),clf+=w[i];sort(ord.begin(),ord.end(),[&](int x,int y){ return w[x]>w[y]; });for(int u:ord) ins(u);for(int i=n;i>=1;--i) s1[i]=s1[i+1]+cnt[i],s2[i]=s2[i+1]+cnt[i]*i;
}
ll query(int L,int R) {int x=min(n,R/L)+1;return clf*L+s2[x]*L-s1[x]*R;
}
*E. [P11054] Connect
Problem Link
题目大意
给定一张 \(n\) 个点 \(m\) 条边的无向图，交互器中每个点有一个 \([0,n)\) 的颜色。
每次交互时，你可以把若干个点染成 \([0,n]\) 中的任意颜色，交互器会告诉你新图中的同色连通块数量。
请在 \(2750\) 次交互之内确定每个点的颜色。
数据范围：\(n\le 250\)。
思路分析
先从链入手。
将所有奇数下标的点全部染成某种颜色 \(c\)，如果此时得到的连通块数 \(<n\)，说明下标为偶数的点中有颜色为 \(c\) 的，否则说明没有。
以此为依据二分，可以求出每个颜色为 \(c\) 的点，对每种颜色进行此过程即可还原下标为偶数的点，对于下标为奇数的点也做一遍即可求解，操作次数 \(2n+n\log n\)。
然后考虑推广，我们可以对链上所有下标为计数的点一次性检验，那么在图上我们可以对一个独立集状物一次性检验。
具体来说，选定一个独立集 \(S\)，将 \(\overline S\) 中的点染成 \(c\)，如果返回值小于 \(|S|\) 加上 \(\overline{S}\) 导出子图的连通块数，那么说明 \(S\) 中存在颜色 \(c\)，可以 \(n+|S|\log n\) 还原。
考虑进一步优化，观察我们用到了独立集的什么性质。
首先要求 \(S\) 内部的连通块数量为 \(S\)，也即 \(S\) 中没有同色点相连，那么我们可以将同色且相邻的点缩成一个连通块。
其次要求每个 \(S\) 中的点都至少和一个 \(\overline S\) 中的点相连，这样才能在一个点颜色为 \(c\) 的时候减少连通块数量。
这是容易的，取出一棵生成树并黑白染色得到两个集合分别作为 \(S\) 求解即可。
最终我们只要求出每个同色连通块即可，也就是本题 \(50\%\) 分数的子任务。
这个不难，考虑增量法构造，依次加入每个点 \(u\) 并求出已加入的点中哪些与其同色。
将 \(u\) 的邻域和 \(u\) 自己保留原先颜色，其他点染颜色 \(n\)，设保留原颜色的点集是 \(V\) 那么 \(u\) 的邻域中有与 \(u\) 同色的点当且仅当实际同色连通块数小于 \(|V|\) 加 \(\overline V\) 导出子图中的连通块数量。
注意到每次二分实际上都减少了一个点（和其他点并成同色连通块，或确定一个连通块的颜色），那么我们在 \(3n+n\log n\) 次询问内解决了此问题。
实际上由于元素数的不断减少，询问次数不超过 \(3n+\sum_{i=1}^n\log_2i\)，可以通过。
注意特判全部点颜色相同的 Corner Case。
时间复杂度 \(\mathcal O(n^2\log n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
int perform_experiment(vector<int>E);
const int MAXN=255;
vector <int> G[MAXN],E[MAXN],R[MAXN];
int n;
struct DSU {int dsu[MAXN];void init() { iota(dsu,dsu+n,0); }int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }bool merge(int x,int y) {x=find(x),y=find(y),dsu[x]=y;return x^y;}
} F,T;
int count(const vector<int>&V) {static bitset<MAXN> inq;inq.reset(),T.init();for(int i:V) inq.set(i);int s=V.size();for(int i:V) for(int j:G[i]) if(inq[j]) s-=T.merge(i,j);return s;
}
int col[MAXN];
void solve(vector<int> S) {for(int c=0;c<n;++c) {vector <int> X;while(S.size()) {auto chk=[&](int k) {vector <int> q(n,c),r;for(int i=0;i<=k;++i) for(int u:R[S[i]]) q[u]=-1;for(int i=0;i<n;++i) if(~q[i]) r.push_back(i);int z=perform_experiment(q);return z<count(r)+k+1;};int l=0,r=S.size()-2,x=S.size()-1;if(!chk(x)) {X.insert(X.end(),S.begin(),S.end());break;}while(l<=r) {int mid=(l+r)>>1;if(chk(mid)) x=mid,r=mid-1;else l=mid+1;}col[S[x]]=c;X.insert(X.end(),S.begin(),S.begin()+x);S.erase(S.begin(),S.begin()+x+1);}S.swap(X);}
}
vector<int> find_colours(int N,vector<int>X,vector<int>Y) {n=N,F.init();for(int i=0;i<(int)X.size();++i) G[X[i]].push_back(Y[i]),G[Y[i]].push_back(X[i]);for(int u=0;u<n;++u) {static bitset <MAXN> vis;vis.reset();vector <int> Ne,C;for(int v:G[u]) if(v<u&&!vis[F.find(v)]) {Ne.push_back(F.find(v)),vis.set(F.find(v));}while(Ne.size()) {auto chk=[&](int k) { //qry Ne[0,k]vector <int> q(n,n),r;vis.reset(),q[u]=-1;for(int i=0;i<=k;++i) vis.set(Ne[i]);for(int i=0;i<u;++i) if(vis[F.find(i)]) q[i]=-1;for(int i=0;i<n;++i) if(~q[i]) r.push_back(i);int z=perform_experiment(q);return count(r)+k+2>z;};int l=0,r=Ne.size()-2,x=Ne.size()-1;if(!chk(x)) break;while(l<=r) {int mid=(l+r)>>1;if(chk(mid)) x=mid,r=mid-1;else l=mid+1;}C.push_back(Ne[x]);Ne.erase(Ne.begin(),Ne.begin()+x+1);}for(int v:C) F.merge(u,v);}vector <int> bl(n);for(int i=0;i<n;++i) R[bl[i]=F.find(i)].push_back(i);F.init();for(int i=0;i<n;++i) for(int j:G[i]) if(F.merge(bl[i],bl[j])) {E[bl[i]].push_back(bl[j]),E[bl[j]].push_back(bl[i]);}vector <int> S[2];function<void(int,int,int)> dfs=[&](int u,int fz,int c) {S[c].push_back(u);for(int v:E[u]) if(v^fz) dfs(v,u,c^1);};dfs(bl[0],-1,0);if(S[1].empty()) {vector <int> q(n,-1);for(q[0]=0;q[0]<n;++q[0]) if(perform_experiment(q)==1) {return vector<int>(n,q[0]);}}solve(S[0]),solve(S[1]);vector <int> cols(n);for(int i=0;i<n;++i) cols[i]=col[bl[i]];return cols;
}
Round #8 - 2024.9.19
A. [P11053] Grid
Problem Link
题目大意
给定 \(n\times n\) 的 01 矩阵 \(A\) 的第一行和第一列，定义 \(A_{i,j}=1-A_{i-1,j}\times A_{i,j-1}\)，\(q\) 次询问 \(A\) 的某个子矩阵的元素和。
数据范围：\(n,q\le 2\times 10^5\)。
思路分析
观察这个矩阵，发现如果 \(A_{i,j}=1\) 那么 \(A_{i+1,j},A_{i,j+1}=0\)，从而 \(A_{i+1,j+1}=1\)，因此所有的 \(1\) 构成若干向右下方的射线。
并且我们发现如果 \(A_{i,j}=1,A_{i-1,j-1}=0\)，那么可以推出 \(A_{i,j}\) 左上角的矩形一定形如 \(\begin{bmatrix}x&y&1\\z&0&0\\1&0&1\end{bmatrix}\)。
此时 \(y,z\) 中至少有一个 \(1\)，又因为连续的两个 \(1\) 显然不能出现在第一行或第一列以外的地方。
因此这种情况只能出现在 \(\min(i,j)\le 3\) 的位置，也就是前三行或前三列，那么暴力求出第三行和第三列，其中的每个 \(1\) 都对应一条向右下方的射线，且不存在其他的 \(1\)。
对子矩形询问差分成一个以 \((1,1)\) 为左上角的询问 \((x,y)\)，对于一条射线的起点 \((i,j)\)，其对询问的贡献就是 \(\max(0,\min(x-i,y-j))\)。
先求出 \(\sum \min(x-i,y-j)\)，\(\min(x-i,y-j)<0\) 的点一定是 \(A_{3,j+1\sim n}\) 和 \(A_{i+1\sim n,3}\) 范围内的点，后缀和即可。
时间复杂度 \(\mathcal O((n+q)\log n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef vector<int> vi;
const int MAXN=2e5+5;
int n,q,a[4][MAXN],b[MAXN][4],cl[MAXN],cr[MAXN];
ll dl[MAXN],dr[MAXN];
bool cmp(array<int,2> i,array<int,2> j) { return i[0]-i[1]<j[0]-j[1]; }
vector<ll> mosaic(vi X,vi Y,vi T,vi B,vi L,vi R) {n=X.size(),q=T.size();if(n<=3) {vector <vi> M(n,vi(n));M[0]=X;for(int i=1;i<n;++i) {M[i][0]=Y[i];for(int j=1;j<n;++j) M[i][j]=(M[i-1][j]|M[i][j-1])^1;}for(int i=0;i<n;++i) for(int j=1;j<n;++j) M[i][j]+=M[i][j-1];for(int i=1;i<n;++i) for(int j=0;j<n;++j) M[i][j]+=M[i-1][j];vector <ll> ans(q);for(int i=0;i<q;++i) {ans[i]=M[B[i]][R[i]];if(T[i]) ans[i]-=M[T[i]-1][R[i]];if(L[i]) ans[i]-=M[B[i]][L[i]-1];if(T[i]&&L[i]) ans[i]+=M[T[i]-1][L[i]-1];}return ans;}for(int i=1;i<=n;++i) a[1][i]=X[i-1],b[i][1]=Y[i-1];a[2][1]=Y[1],a[3][1]=Y[2],b[1][2]=X[1],b[1][3]=X[2];for(int o:{2,3}) for(int i=2;i<=n;++i) {a[o][i]=(a[o-1][i]|a[o][i-1])^1;b[i][o]=(b[i][o-1]|b[i-1][o])^1;}vector <array<int,2>> Z;for(int i=3;i<=n;++i) if(a[3][i]) Z.push_back({3,i}),++cl[i],dl[i]+=i;for(int i=4;i<=n;++i) if(b[i][3]) Z.push_back({i,3}),++cr[i],dr[i]+=i;for(int i=n;i>=1;--i) cl[i]+=cl[i+1],dl[i]+=dl[i+1],cr[i]+=cr[i+1],dr[i]+=dr[i+1];sort(Z.begin(),Z.end(),cmp);int k=Z.size();vector <ll> sl(k),sr(k);if(k) {sl[0]=Z[0][1];for(int i=1;i<k;++i) sl[i]=sl[i-1]+Z[i][1];sr[k-1]=Z[k-1][0];for(int i=k-2;~i;--i) sr[i]=sr[i+1]+Z[i][0];}for(int i=1;i<=3;++i) for(int j=1;j<=n;++j) a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];for(int i=1;i<=n;++i) for(int j=1;j<=3;++j) b[i][j]+=b[i][j-1]+b[i-1][j]-b[i-1][j-1];auto qry=[&](int x,int y) -> ll {if(x<=3) return a[x][y];if(y<=3) return b[x][y];ll s=a[3][y]+b[x][3]-a[3][3];int i=upper_bound(Z.begin(),Z.end(),array<int,2>{x,y},cmp)-Z.begin();if(i>0) s+=1ll*i*y-sl[i-1];if(i<k) s+=1ll*(k-i)*x-sr[i];s+=dl[y]-1ll*y*cl[y];s+=dr[x]-1ll*x*cr[x];return s;};vector <ll> ans(q);for(int i=0;i<q;++i) ans[i]=qry(B[i]+1,R[i]+1)-qry(T[i],R[i]+1)-qry(B[i]+1,L[i])+qry(T[i],L[i]);return ans;
}
B. [P10303] Function
Problem Link
题目大意
给定 \(n\) 个函数和初值 \(x_0\)，每个函数 \(F_i(x)\) 形如 \(a_i|x|+b_ix+c_i\)，求一个排列 \(p_1\sim p_n\) 使得 \(F_{p_1}(F_{p_2}(\cdots F_{p_n}(x_0)))\) 最大。
数据范围：\(n,|x_0|,|a_i|,|b_i|,|c_i|\le 15\)。
思路分析
暴力 dp \(f_{s,v}\) 表示使用 \(s\) 中函数后能否得到 \(v\)，但 \(v\) 值域过大，需要优化状态。
先考虑 \(c_i=0\) 的情况，那么 \(F_i(x)\) 只会根据 \(x\) 的符号不同形成两种情况，并且两个同号的人操作后依然同号。
那么我们显然只关心绝对值最大和最小的正数和负数，此时只要对每个 \(f_s\) 记录这四种状态即可。
回到 \(c_i\ne 0\) 的情况，\(F_i(x)\) 可能会把一些绝对值较小的元素通过 \(c_i\) 变号，不难发现这样的变号若发生，\(x\) 初值一定 \(\le nV\)，其中 \(V\) 是值域，那么对每个 \(f_s\) 特殊记录 \([-nV,nV]\) 范围内的数能否得到即可。
时间复杂度 \(\mathcal O(2^nn^2V)\)。
代码呈现
#include<bits/stdc++.h>
#define LL __int128
using namespace std;
const int V=250;
const LL inf=1e36;
struct info {LL xl,xr,yl,yr;bitset <505> q;info() { xl=0,xr=-inf,yl=inf,yr=0; }void ins(LL x) {if(-V<=x&&x<=V) q.set(x+V);if(x<0) xl=min(xl,x),xr=max(xr,x);else yl=min(yl,x),yr=max(yr,x);}void gen(vector <LL> &v) {if(xl<=xr) v.push_back(xl),v.push_back(xr);if(yl<=yr) v.push_back(yl),v.push_back(yr);for(int i=-V;i<=V;++i) if(q[i+V]) v.push_back(i);}
} f[1<<15];
int n,o,a[15],b[15],c[15];
LL val(LL x,int i) {return (x<0?b[i]-a[i]:b[i]+a[i])*x+c[i];
}
int ow=0;
char obuf[105];
void write(LL x) {if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');
}
signed main() {scanf("%d%d",&n,&o),f[0].ins(o);for(int i=0;i<n;++i) scanf("%d%d%d",&a[i],&b[i],&c[i]);for(int s=0;s<(1<<n);++s) {vector <LL> z; f[s].gen(z);for(LL x:z) for(int i=0;i<n;++i) if(!(s>>i&1)) {f[s|1<<i].ins(val(x,i));}if(s==(1<<n)-1) write(*max_element(z.begin(),z.end()));}puts("");return 0;
}
C. [P10304] Delete
Problem Link
题目大意
给定一张 \(n\) 个点 \(m\) 条边的 DAG，求出以 \(1\) 为根的 dfs 生成树 \(T\)，\(q\) 次询问给定 \(a,b\)，其中 \(a\) 在 \(T\) 中是 \(b\) 的祖先，查询若删 $a\to b $ 在 \(T\) 上路径的边后，\(b\) 在 \(T\) 上的子树中有多少个点不能从 \(1\) 出发到达。
数据范围：\(n,q\le 10^5,m\le 1.5\times 10^5\)。
思路分析
先考虑 \(b\) 是否可达，这个事情显然对 \(a\) 的深度有单调性，因此我们求出 \(f_b\) 表示如果存在 \(1\to b\) 路径，\(dep_a\) 至少是多少。
初始 \(f_b=dep_b\)，转移时逆拓扑序考虑每条非树边，对于非树边 \(u\to v\)，那么就会把 \(f_v\) 用 \(u\to\mathrm{LCA}(u,v)\) 路径上最小的 \(f\) 更新，可以倍增维护。
然后考虑 \(b\) 子树内的某个点 \(c\)，容易发现 \(c\) 能到达的条件就是 \(b\to c\) 路径上存在一个 \(f_u\le dep_a\)。
离线下来维护 \(v\) 到当前节点 \(u\) 的路径最小 \(f\)，更新就是求出 \((f_u,n]\) 内的节点数加到 \(f_u\) 上并清空 \((f_u,n]\)，查询就是后缀求和，不难用值域线段树合并维护。
时间复杂度 \(\mathcal O((n+m+q)\log n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m,dep[MAXN],dfn[MAXN],dcnt,st[MAXN][20],deg[MAXN],up[MAXN][20];
vector <int> G[MAXN],E[MAXN],ord,O[MAXN];
void dfs0(int u,int fz) {dep[u]=dep[fz]+1,dfn[u]=++dcnt,st[dcnt][0]=fz,up[u][0]=fz;for(int k=1;k<20;++k) up[u][k]=up[up[u][k-1]][k-1];for(int v:G[u]) {if(!dfn[v]) E[u].push_back(v),dfs0(v,u);else O[u].push_back(v);}
}
int bit(int x) { return 1<<x; }
int cmp(int x,int y) { return dfn[x]<dfn[y]?x:y; }
int LCA(int x,int y) {if(x==y) return x;int l=min(dfn[x],dfn[y])+1,r=max(dfn[x],dfn[y]),k=__lg(r-l+1);return cmp(st[l][k],st[r-bit(k)+1][k]);
}
int f[MAXN],mn[MAXN][20];
int qry(int x,int r) {int s=f[r];for(int k=19;~k;--k) if(dep[up[x][k]]>=dep[r]) s=min(s,mn[x][k]),x=up[x][k];return s;
}
struct SegmentTree {int tot,tr[MAXN*20],ls[MAXN*20],rs[MAXN*20];void ins(int u,int x,int l,int r,int &p) {if(!p) p=++tot;tr[p]+=x;if(l==r) return ;int mid=(l+r)>>1;u<=mid?ins(u,x,l,mid,ls[p]):ins(u,x,mid+1,r,rs[p]);}void merge(int l,int r,int q,int &p) {if(!q||!p) return p|=q,void();tr[p]+=tr[q];if(l==r) return ;int mid=(l+r)>>1;merge(l,mid,ls[q],ls[p]),merge(mid+1,r,rs[q],rs[p]);}int qry(int ul,int ur,int l,int r,int p) {if(ul<=l&&r<=ur) return tr[p];int mid=(l+r)>>1,s=0;if(ul<=mid) s+=qry(ul,ur,l,mid,ls[p]);if(mid<ur) s+=qry(ul,ur,mid+1,r,rs[p]);return s;}void del(int ul,int ur,int l,int r,int &p) {if(ul<=l&&r<=ur) return tr[p]=0,p=0,void();int mid=(l+r)>>1;if(ul<=mid) del(ul,ur,l,mid,ls[p]);if(mid<ur) del(ul,ur,mid+1,r,rs[p]);tr[p]=tr[ls[p]]+tr[rs[p]];}
} T;
int rt[MAXN],ans[MAXN];
vector <array<int,2>> qys[MAXN];
void dfs1(int u) {T.ins(f[u],1,1,n,rt[u]);for(int v:E[u]) dfs1(v),T.merge(1,n,rt[v],rt[u]);if(f[u]<n) {int w=T.qry(f[u]+1,n,1,n,rt[u]);T.ins(f[u],w,1,n,rt[u]),T.del(f[u]+1,n,1,n,rt[u]);}for(auto z:qys[u]) if(z[0]<n) ans[z[1]]=T.qry(z[0]+1,n,1,n,rt[u]);
}
signed main() {int q;scanf("%d%d%d",&n,&m,&q);for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back(v),++deg[v];for(int i=1;i<=n;++i) sort(G[i].begin(),G[i].end());queue <int> Q;for(int i=1;i<=n;++i) if(!deg[i]) Q.push(i);while(Q.size()) {int u=Q.front(); Q.pop(),ord.push_back(u);for(int v:G[u]) if(!--deg[v]) Q.push(v);}dfs0(1,0);for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=dcnt;++i) {st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);}for(int i=1;i<=n;++i) if(dfn[i]) f[i]=dep[i];for(int u:ord) if(dfn[u]) {mn[u][0]=f[u];for(int k=1;k<20;++k) mn[u][k]=min(mn[u][k-1],mn[up[u][k-1]][k-1]);for(int v:O[u]) if(dfn[v]) f[v]=min(f[v],qry(u,LCA(u,v)));}for(int i=1,a,b;i<=q;++i) scanf("%d%d",&a,&b),qys[b].push_back({dep[a],i});dfs1(1);for(int i=1;i<=q;++i) printf("%d\n",ans[i]);return 0;
}
D. [P8499] Equal
Problem Link
题目大意
给定两棵有根树 \(G,H\)，记 \(n=|G|,k=|H|-|G|\)，求是否能在 \(H\) 上删除 \(k\) 个节点使得 \(G,H\) 同构。
数据范围：\(n\le 5\times 10^5,k\le 5\)。
思路分析
直接 dp 状态难以接受，考虑自上而下地搜索设 \(f_{i,j}\) 表示能否使得 \(G\) 中 \(i\) 子树和 \(H\) 中 \(j\) 子树同构。
用树哈希判断子树同构，当 \(H\) 是叶子时返回，否则相当于对 \(i,j\) 的所有儿子对应子树求完美匹配。
我们发现如果有两个子树 \(x,y\) 已经同构，那么直接匹配这两个子树肯定可以，否则我们可以用 \(y\) 匹配的子树匹配上 \(x\) 匹配的子树从而调整出一组 \(x,y\) 匹配的解。
那么 \(i\) 剩下未匹配的子树 \(\le k\) 棵，\(\mathcal O(k!)\) 爆搜每种匹配并记搜优化即可。
可以证明被访问到的 \(f_{i,j}\) 总量是 \(\mathcal O(n2^k)\) 的。
时间复杂度 \(\mathcal O(n2^kk!)\)。
代码呈现
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=1e5+5;
struct Tree {int n,rt,fa[MAXN],siz[MAXN];vector <int> E[MAXN];ull f[MAXN];ull P(ull x) {x^=x<<13,x^=x>>7,x^=x<<17;return x*x*29+x*13+37;}void dfs(int u) {f[u]=siz[u]=1;for(int v:E[u]) dfs(v),siz[u]+=siz[v],f[u]+=P(f[v]);sort(E[u].begin(),E[u].end(),[&](int x,int y){ return f[x]<f[y]; });}void init() {cin>>n;for(int i=1;i<=n;++i) E[i].clear(),siz[i]=f[i]=0;for(int i=1;i<=n;++i) {cin>>fa[i];if(~fa[i]) E[fa[i]].push_back(i);else rt=i;}dfs(rt);}
} G,H;
int k;
map <array<int,2>,bool> DP;
bool dp(int x,int y) {if(H.siz[y]==1) return true;if(DP.count({x,y})) return DP[{x,y}];if(G.siz[x]<H.siz[y]) return false;vector <int> &g=G.E[x],&h=H.E[y],s,t;auto ig=g.begin(),ih=h.begin();while(ig!=g.end()&&ih!=h.end()) {if(G.f[*ig]==H.f[*ih]) ++ig,++ih;else if(G.f[*ig]<H.f[*ih]) s.push_back(*ig++);else t.push_back(*ih++);}s.insert(s.begin(),ig,g.end()),t.insert(t.begin(),ih,h.end());if(s.size()<t.size()||s.size()>k) return false;int z=s.size();vector <int> p(z);iota(p.begin(),p.end(),0),t.resize(z,0);do {bool ok=true;for(int i=0;i<z;++i) {ok&=dp(s[i],t[p[i]]);if(!ok) break;}if(ok) return DP[{x,y}]=true;} while(next_permutation(p.begin(),p.end()));return DP[{x,y}]=false;
}
void solve() { DP.clear(),G.init(),H.init(),cout<<(dp(G.rt,H.rt)?"Yes\n":"No\n"); }
signed main() {ios::sync_with_stdio(false);int T,C; cin>>C>>T>>k;while(T--) solve();return 0;
}
E. [P9481] Edge
Problem Link
题目大意
给定 \(2^n-1\) 个节点的完全二叉树，每个点向父亲连一条带权有向边，除此之外还有 \(m\) 条从祖先到后代的额外边，求所有点对之间的最短路长度之和。
数据范围：\(n\le 18,m\le 2^{18}\)。
思路分析
考虑把所有边方向取反，此时 \(u\to v\) 的路径必然过 \(\mathrm{LCA}(u,v)\)，那么对每个 \(u\)，到其子树的最短路容易求，只要对每个祖先求出最短路，到该祖先的其他子树的最短路就能算出了。
对每个祖先求最短路，可以先预处理祖先之间的最短路，都当成边连接，然后把 \(u\) 的祖先和后代全部拿出来跑 Dijkstra。
注意到树高 \(\mathcal O(n)\)，因此每个点和边只会被计算 \(\mathcal O(n)\) 次。
时间复杂度 \(\mathcal O(mn\log m)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=(1<<18)+5,MOD=998244353;
const ll inf=1e18;
struct Edge { int v; ll w; };
vector <Edge> G[MAXN];
int n,m,d[MAXN],to[MAXN];
ll a[MAXN],f[MAXN],dis[MAXN],ans;
bool vis[MAXN];
void dfs(int u) {if(d[u]==1) return ;for(int v:{u<<1,u<<1|1}) d[v]=d[u]>>1,dfs(v),f[u]=(f[u]+f[v]+a[v]*d[v])%MOD;
}
void init(int x) {vis[x]=false,dis[x]=inf;if(d[x]>1) init(x<<1),init(x<<1|1);
}
void solve(int s) {for(int x=s;x;x>>=1) to[x>>1]=x,vis[x]=false,dis[x]=inf;init(s);priority_queue <array<ll,2>,vector<array<ll,2>>,greater<array<ll,2>>> Q;Q.push({dis[s]=0,s});while(Q.size()) {int u=Q.top()[1]; Q.pop();if(vis[u]) continue;vis[u]=true,ans=(ans+dis[u])%MOD;for(auto e:G[u]) if(dis[e.v]>dis[u]+e.w) Q.push({dis[e.v]=dis[u]+e.w,e.v});auto ext=[&](int v) {if(dis[v]>dis[u]+a[v]) Q.push({dis[v]=dis[u]+a[v],v});};if(u<s) ext(to[u]);else if(d[u]>1) ext(u<<1),ext(u<<1|1);}G[s].clear();for(int x=s>>1;x;x>>=1) if(vis[x]) {G[s].push_back({x,dis[x]});int y=to[x]^1;ans=(ans+f[y]+(dis[x]+a[y])*d[y])%MOD;}
}
signed main() {scanf("%d%d",&n,&m);for(int i=2;i<(1<<n);++i) scanf("%lld",&a[i]);for(int i=1,u,v,w;i<=m;++i) scanf("%d%d%d",&u,&v,&w),G[v].push_back({u,w});d[1]=(1<<n)-1,dfs(1);for(int u=1;u<(1<<n);++u) solve(u);printf("%lld\n",ans);return 0;
}
F. [P9482] String
Problem Link
题目大意
给定长度为 \(n\) 的字符串 \(S\)，\(q\) 次询问给定 \(x,k\)，求有多少 \(i\in[1,k]\) 满足 \(S[x,x+i-1]<\mathrm{rev}(S[x+i,x+2i-1])\)，\(<\) 表示字典序比较。
数据范围：\(n,q\le 10^5\)。
思路分析
考虑如何判定一组 \((x,i)\) 合法，首先可以比较后缀 \(S[x,n]\) 和前缀 \(S[1,x+2i-1]\)，可以对 \(S+\mathrm{rev}(S)\) 建后缀数组处理出每个后缀 \(S[i,n]\) 的排名 \(R_i\) 和前缀的排名 \(L_{x+2i-1}\)。
那么一组 \((x,i)\) 合法当且仅当 \(R_x<L_{x+2i-1}\) 并且 \(S[x,x+2i-1]\) 不是回文串。
先考虑怎么对满足第一个条件的点计数，对 \(L\) 降序扫描线，相当于求 \([x,x+2k)\) 中有多少被已插入的元素和 \(x\) 奇偶性不同，对奇数和偶数分别建树状数组维护即可。
然后我们要去掉 \(R_x<L_{x+2i-1}\) 且 \(S[x,x+2i-1]\) 回文的情况，设以 \((i,i+1)\) 为回文中心的最长回文半径为 \(d_i\)，那么第二个条件就是 \(d_{i+x-1}\ge i\)。
第一个条件不好处理，但我们发现 \(S[x,x+i-1]=S[x+i,x+2i-1]\) 时一定有 \([R_x<L_{x+2i-1}]=[R_{i+x}<L_{i+x-1}]\)，事实上就是给两个串的开头删去相等的一段字符。
那么我们只要把不满足 \(R_{i+1}<L_i\) 的 \(d_i\) 设成 \(-\infty\)，然后只要数 \(i\in [x,x+k-1]\) 中有多少 \(i-d_i+1\le x\)，注意到 \(i< x\) 的时候只要 \(d_i\ne-\infty\) 恒成立，因此可以预处理前缀和解决一半。
时间复杂度 \(\mathcal O((n+q)\log n)\)。
代码呈现
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=2e5+5;
mt19937_64 rnd(time(0));
char str[MAXN];
int sa[MAXN],rk[MAXN],wt[MAXN],len[MAXN],ht[MAXN][20];
int bit(int x) { return 1<<x; }
void init(int n) {iota(sa+1,sa+n+1,1);sort(sa+1,sa+n+1,[&](int x,int y){ return str[x]<str[y]; });for(int i=1,j;i<=n;) {for(j=i;j<n&&str[sa[j+1]]==str[sa[i]];++j);len[i]=j-i+1;while(i<=j) rk[sa[i++]]=j;}for(int k=1;k<n;k<<=1) {for(int l=1,r;l<=n;++l) if(len[l]>1) {r=l+len[l]-1;for(int i=l;i<=r;++i) wt[sa[i]]=(sa[i]+k>n?0:rk[sa[i]+k]);sort(sa+l,sa+r+1,[&](int x,int y){ return wt[x]<wt[y]; });for(int i=l,j;i<=r;) {for(j=i;j<r&&wt[sa[j+1]]==wt[sa[i]];++j);len[i]=j-i+1;while(i<=j) rk[sa[i++]]=j;}l=r;}}for(int i=1,k=0;i<=n;++i) {k=max(k-1,0);while(str[i+k]==str[sa[rk[i]-1]+k]) ++k;ht[rk[i]][0]=k;}for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=n;++i) {ht[i][k]=min(ht[i][k-1],ht[i+bit(k-1)][k-1]);}
}
int lcp(int x,int y) {int l=min(rk[x],rk[y])+1,r=max(rk[x],rk[y]),k=__lg(r-l+1);return min(ht[l][k],ht[r-bit(k)+1][k]);
}
int n,q,L[MAXN],R[MAXN],id[MAXN],ans[MAXN],d[MAXN],cnt[MAXN];
bool mk[MAXN];
vector <array<int,3>> Q1[MAXN],Q2[MAXN];
struct FenwickTree {int tr[MAXN],s;void init() { memset(tr,0,sizeof(tr)); }void add(int x) { for(;x<=n;x+=x&-x) ++tr[x]; }int qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
} T[2];
void solve() {scanf("%d%d%s",&n,&q,str+1);str[n+1]='#',str[2*n+2]='|';for(int i=1;i<=n;++i) str[2*n+2-i]=str[i];init(2*n+2);for(int i=1;i<=n;++i) R[i]=rk[i],L[i]=rk[2*n+2-i];for(int i=1;i<n;++i) {d[i]=lcp(i+1,2*n+2-i);mk[i]=(R[i+1]<L[i]),cnt[i]=cnt[i-1]+mk[i];}iota(id+1,id+n+1,1);sort(id+1,id+n+1,[&](int x,int y){ return L[x]<L[y]; });for(int i=1,x,k;i<=q;++i) {scanf("%d%d",&x,&k),ans[i]=0;int l=1,r=n,p=n+1;while(l<=r) {int m=(l+r)>>1;if(R[x]<L[id[m]]) p=m,r=m-1;else l=m+1;}if(p<=n) {Q1[p].push_back({x,k,i});ans[i]+=cnt[x-1];Q2[x+k-1].push_back({x,k,i});}}T[0].init(),T[1].init();for(int i=n;i>=1;--i) {T[id[i]&1].add(id[i]);for(auto z:Q1[i]) {int x=z[0],k=z[1],r=(x^1)&1;ans[z[2]]+=T[r].qry(x+2*k-1)-T[r].qry(x-1);}}T[0].init();for(int i=1;i<=n;++i) {if(mk[i]) T[0].add(i-d[i]+1);for(auto z:Q2[i]) ans[z[2]]-=T[0].qry(z[0]);}for(int i=1;i<=q;++i) printf("%d\n",ans[i]);for(int i=1;i<=n;++i) Q1[i].clear(),Q2[i].clear();
}
signed main() {int C,O; scanf("%d%d",&C,&O);while(O--) solve();return 0;
}
G. [P9479] Tree
Problem Link
题目大意
给定 \(n\) 个节点的树，保证父亲节点编号小于儿子，求有多少 \(n+m\) 个节点的树（根节点为 \(1\)），使得：
- 对于所有 \(i,j\in[1,n]\)，在两棵树上 \(\mathrm{LCA}(i,j)\) 的标号相同。
- 对于所有 $ i,j$，在新树上 \(\mathrm{LCA}(i,j)\le \max(i,j)+k\)。
数据范围：\(n\le 3\times 10^4,m\le 3000,k\le 10\)。
思路分析
考虑 \(k=0,m=1\) 如何做，不难发现第一个条件等价于 \(1\sim n\) 的虚树不变，因此只需要在原树上插入一个点，可以插在边中间或者挂在节点下面，方案数 \(2n-1\)。
对于 \(k=0\) 的一般情况，此时要求每个前缀的虚树都不包含更大的节点，从 \(n+1\sim n+m\) 依次插入每个节点，方案数 \(\prod_{i=n}^{n+m-1}(2i-1)\)。
对于原问题，我们依然考虑依次插入 \(i=n+1\sim n+m\)，但是插入 \(i\) 时 \(i\) 可以不在 \(1\sim i-1\) 的虚树上，而是通过一个 \(\mathrm{LCA}\) 挂上去，而这个 \(\mathrm{LCA}\) 一定在 \([i+1,i+k]\) 范围内。
因此对于每个 \(i\)，要么直接将插入树上，有 \(2(i-1)-1\) 种方案，要么在 \([i+1,i+k]\) 中另选择一个节点插在某条边中间，然后把 \(i\) 挂在该节点下面。
不难设计出一个 dp，\(f_{i,s}\) 表示当前已经插入 \(1\sim i\)，\([i+1,i+k]\) 中已经被插入的元素是集合 \(s\)，转移时如果 \(0\in s\) 就跳过，否则按上述过程转移，注意此时树的大小是 \(i+|s|\)。
时间复杂度：\(\mathcal O(n+mk2^k)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=1e9+7;
int n,m,k,f[1<<10],pc[1<<10];
ll g[1<<10];
void solve() {scanf("%d%d%d",&n,&m,&k);for(int i=1;i<n;++i) scanf("%*d");memset(f,0,sizeof(f)),memset(g,0,sizeof(g));if(!k) {ll s=1;for(int i=n;i<n+m;++i) s=s*(2*i-1)%MOD;return printf("%lld\n",s),void();}for(int i=1;i<(1<<k);++i) pc[i]=pc[i>>1]+(i&1);f[0]=1;for(int i=n;i<n+m;++i) {for(int s=0;s<(1<<k);++s) {if(s&1) g[s>>1]+=f[s];else {int z=i+pc[s],t=s>>1;g[t]+=1ll*f[s]*(2*z-1);for(int j=0;j<k;++j) if(!(t>>j&1)) g[t|(1<<j)]+=1ll*f[s]*(z-1);}}for(int s=0;s<(1<<k);++s) f[s]=g[s]%MOD,g[s]=0;}printf("%d\n",f[0]);
}
signed main() {int c,T; scanf("%d%d",&c,&T);while(T--) solve();return 0;
}
*H. [P9483] Merge
iProblem Link
题目大意
给定 \(n\) 个元素，每个元素有 \(w,d\) 两个属性，初始第 \(i\) 个元素为 \((w_i,0)\)，合并元素 \(i\to j\) 的代价为 \(w_i+d_i+d_j\)，合并后形成新元素 \((w_i+w_j,2\max(d_i,d_j)+1)\)，求把所有元素合并成一个的最小代价。
数据范围：\(n\le 100\)。
思路分析
考虑把元素的合并看成一棵二叉树，记每个点 \(u\) 子树的最大深度为 \(d(u)\)，那么所有 \(d\) 的贡献就是所有非根节点的 \(\sum 2^{d(u)}-1\)。
而 \(w\) 的贡献可以看成二叉树上每个点选一个子树系数 \(+1\)，每个叶子的系数就表示该叶子对应 \(w_i\) 对答案的贡献系数。
容易发现每个叶子的具体排列不重要，确定二叉树结构后把权值最大的放到系数最小的位置上即可。
因此我们只关心 \(n\) 个系数构成的每一种可重集 \(C\)。
可以暴力 dp，\(f_{d,C}\) 表示子树内最大深度为 \(d\)，构成系数可重集为 \(C\) 时，\(\sum 2^{d(u)}-1\) 贡献的最小值。
转移时枚举两个状态合并，但这样复杂度太高，无法通过。
我们考虑自上而下地维护这棵二叉树：即从根节点开始，每次把树上的一个叶子分裂出两个儿子节点。
但是每次分裂的时候会影响树上原有节点的 \(d(u)\)，这就需要记录一些和树形态有关的信息，这是完全不能接受的。
考虑优化，注意到一个子树最大深度为 \(d(u)\) 的点，我们可以钦定他在倒数第 \(d(u)\) 次操作时才进行第一次分裂，那么此后的每一次分裂他的最大深度都 \(+1\)，很显然这个过程不改变最优解。
因此存在一种分裂的方式，使得每次分裂后每个非叶节点的最大深度都 \(+1\)，那么 \(\sum 2^{d(u)}\) 就会翻倍，也容易求出分裂后的 \(\sum 2^{d(u)}-1\)。
但是这么做还不足以通过，首先发现答案不超过 \(1.7\times 10^{11}\)，可以用来优化 \(\sum 2^{d(u)}-1\) 的上界。
其次我们发现按照上述钦定的过程分裂，前一次分裂过的节点的两个儿子中至少有一个这次操作也会分裂，因此每次分裂的节点数单调不降，记录上一次分裂的节点个数即可。
时间复杂度 \(\mathcal O(n^2Q_n+nS_n)\)，其中 \(Q\) 表示叶子数 \(1\sim n\) 时的总状态数，\(S\) 表示叶子数 \(=n\) 时的总状态数，\(n=100\) 时 \(Q_n=44039,S_n=1745\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1.7e11;
typedef vector<int> vi;
map <vi,array<ll,2>> f[105];
//[tree size][leaf coef] {min val,low}
ll a[105];
void solve() {int n; scanf("%d",&n);for(int i=0;i<n;++i) scanf("%lld",&a[i]);sort(a,a+n,greater<ll>());ll ans=inf;for(auto &it:f[n]) {const vi&c=it.first;ll s=it.second[0];for(int i=0;i<n;++i) s+=c[i]*a[i];ans=min(ans,s);}printf("%lld\n",ans);
}
signed main() {const int n=100;f[1][{0}]={0,1};for(int i=1;i<=n;++i) for(auto &it:f[i]) {const vi&c=it.first;vi d=it.first;ll w=it.second[0],lim=it.second[1];for(int j=1;j<=i&&i+j<=n;++j) {d.insert(upper_bound(d.begin(),d.end(),c[j-1]+1),c[j-1]+1);if(j>=lim) {ll nw=2*w+(i+j-2);if(nw>inf) break;if(!f[i+j].count(d)) f[i+j][d]={nw,j};else {auto &z=f[i+j][d];z=min(z,array<ll,2>{nw,j});}}}}int T; scanf("%d",&T);while(T--) solve();return 0;
}
*I. [P8500] Inverse
Problem Link
题目大意
给定序列 \(a_1\sim a_n\)，有 \(m\) 个限制，形如 \(\min a[l,r]=V\)，求一个满足条件的序列 \(a\) 最小化逆序对数。
数据范围：\(n,m\le 10^6\)。
思路分析
首先发现我们填的所有数一定是某个 \(V\)，否则换成小于等于当前数的一个 \(V\) 一定严格更优。
先从所有 \(l=r\) 开始，此时相当于一个被确定了若干位的序列，很显然可以任意填的位置一定是单调不降的，否则排序后肯定更优。
从前往后确定每个位置，我们只需要最小化未填元素和已填元素之间的逆序对，这个问题和未填元素之间的取值无关，只需要每个未填元素填贪心最优解即可（多解取最小）。
容易发现越靠后的位置填的数一定更大，因为代价函数上填更小的数代价会严格变大。
然后考虑所有 \([l,r]\) 都不交的情况，很显然我们要在每个 \([l,r]\) 中选一个位置填 \(V\)，我们可以对每个区间内部升序排列，不影响对外部的逆序对。
因此注意到区间所有位置填的都 \(\ge V\)，那么最小值 \(V\) 一定恰好落在 \(a_l\) 上。
然后就是要解决一个有下界限制的问题，依然考虑贪心，从前往后动态维护每个位置上填数的代价函数，每个位置都贪心取最优解，如果有多个则取最小值。
很显然我们不会选一个比贪心解 \(x\) 更大的值，因为更大的值对后续代价函数的增加量也更大，我们要说明取的数 \(y\) 不会小于贪心解。
如果 \(y<x\)，那么直接把值域在 \([y,x]\) 中的元素推平成 \(x\)，这些元素内部的逆序对数会减少，而这些元素和已确定元素之间的逆序对数也会变少，因为每个位置的最优解一定 \(\ge x\)。
因此我们可以依然可以用贪心解决这个问题。
接下来回到原问题，我们要考虑如何确定每个区间中填 \(V\) 的数的位置，然后又转化为前一个特殊性质的贪心问题。
倒序扫描 \(V\)，先去除所有有包含关系的限制，然后我们要贪心使得填 \(V\) 的数越靠左越好。
从后往前扫描即可，每个区间如果未满足就把 \(V\) 放在左端点，容易证明此时对后续区间的选取也是最优的。
注意删去被标记为 \(\ge V\) 的位置，用线段树维护剩下的贪心即可。
时间复杂度 \(\mathcal O((n+m)\log n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef array<int,2> pii;
const int MAXN=1e6+5;
int n,m,q;
struct SegmentTree {pii tr[MAXN<<2];int tg[MAXN<<2];void adt(int p,int k) { tr[p][0]+=k,tg[p]+=k; }void psd(int p) { adt(p<<1,tg[p]),adt(p<<1|1,tg[p]),tg[p]=0; }void psu(int p) { tr[p]=min(tr[p<<1],tr[p<<1|1]); }void init(int l=1,int r=q,int p=1) {tr[p]={0,l},tg[p]=0;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 k,int l=1,int r=q,int p=1) {if(ul>ur) return ;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);}pii qry(int ul,int ur,int l=1,int r=q,int p=1) {if(ul<=l&&r<=ur) return tr[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 min(qry(ul,ur,l,mid,p<<1),qry(ul,ur,mid+1,r,p<<1|1));}
} T;
struct info { int l,r,v; };
vector <info> I[MAXN];
int a[MAXN],dsu[MAXN];
bool up[MAXN];
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
void solve() {scanf("%d%d",&n,&m);vector <info> lims(m);vector <int> vals;for(auto &e:lims) scanf("%d%d%d",&e.l,&e.r,&e.v),vals.push_back(e.v);sort(vals.begin(),vals.end());vals.erase(unique(vals.begin(),vals.end()),vals.end());q=vals.size(),T.init();for(auto &e:lims){e.v=lower_bound(vals.begin(),vals.end(),e.v)-vals.begin()+1;I[e.v].push_back(e);}iota(dsu+1,dsu+n+2,1);for(int i=q;i>=1;--i) {vector <int> idx;for(auto o:I[i]) for(int x=find(o.l);x<=o.r;x=find(x)) {idx.push_back(x),a[x]=i,dsu[x]=x+1;}sort(idx.begin(),idx.end()),idx.push_back(n+1);sort(I[i].begin(),I[i].end(),[&](info x,info y){ return x.l^y.l?x.l>y.l:x.r<y.r; });int lst=n+1;vector <info> J;for(auto o:I[i]) if(o.r<lst) J.push_back(o),lst=o.r;sort(J.begin(),J.end(),[&](info x,info y){ return x.l>y.l; }),lst=n+1;for(auto o:J) if(lst>o.r) {lst=*lower_bound(idx.begin(),idx.end(),o.l);if(lst<=o.r) up[lst]=true;else return puts("-1"),void();}}ll ans=0;for(int i=n;i;--i) if(up[i]) ans+=T.qry(a[i],a[i])[0],T.add(a[i]+1,q,1);for(int i=1;i<=n;++i) {if(up[i]) T.add(a[i]+1,q,-1),T.add(1,a[i]-1,1);else {auto z=T.qry(max(a[i],1),q,1);ans+=z[0],T.add(1,z[1]-1,1);}}printf("%lld\n",ans);
}
signed main() {int cs; scanf("%d",&cs);while(cs--) {solve();for(int i=1;i<=n;++i) a[i]=up[i]=0;for(int i=1;i<=q;++i) I[i].clear();}return 0;
}
*J. [P10881] Cycle
Problem Link
题目大意
给定 \(n\) 个点的完全图，每个点有点权 \(a_i\)，\(i,j\) 之间的边权为 \(a_i+a_j\)，求图上所有生成的基环树的边权乘积之和。
数据范围：\(n\le 1000\)。
思路分析
先从树上边权乘积之和开始，这显然是一个矩阵树定理，我们所求就是 \(\det(D-G)\)，其中 \(D_{i,i}=A+na_i\)，其中 \(A=\sum a_i\)，\(G_{i,j}=a_i+a_j\)。
暴力带入得到：\(\det(D-G)=\sum_p(-1)^{\mathrm{inv}(p)}\prod(D_{i,p_i}-G_{i,p_i})\)。
考虑暴力拆开后面的括号，即把原矩阵分成两部分分别求出 \(D\) 上和 \(G\) 上的行列式，又因为 \(\mathrm{rank}(G)\le 2\)，因此我们只要考虑选择 \(\le 2\) 个 \(G\) 中行的情况。
又因为 \(D\) 时对角线矩阵，因此在 \(D\) 上的行列式只有全取对角线时有贡献，那么原式可以化成：
记 \(A_i=A+na_i\)，进一步化简就是：
此时我们就有了一个较好的表达式来计算矩阵行列式。
然后考虑基环树的情况，我们可以暴力枚举一个环，然后把环缩成一个点后求矩阵树定理的行列式。
先考虑如果确定一个环上的点集 \(S\) 后，如何求出每种情况下环上边权乘积之和，即 \(\sum_p\prod_i (a_i+a_{p_i})\)。
考虑经典做法，拆系数，即把答案表示成 \(\prod a_i^{c_i}\) 的线性组合，对每组 \(\{c_i\}\) 算出对应的系数，查询时只需要求出每种给 \(a_i\) 分配 \(c_i\) 的方案权值和即可。
容易发现这个式子中每个 \(a_i\) 出现 \(2\) 次，那么 \(c_i\in\{0,1,2\}\) 且 \(\sum c_i=|S|\)，则 \(c_i=0\) 的元素和 \(c_i=2\) 的元素一样多。
不妨枚举有 \(x\) 个 \(c_i=0\) 的元素，\(y\) 个 \(c_i=1\) 的元素，我们要求的就是分配方案数，可以把这个问题看成给环定向，\(c_i\) 表示出度。
我们可以先插入 \(c_i=0\) 和 \(c_i=2\) 的点，这部分方案数 \(\dfrac{x!^2}{x}\)，然后插入 \(c_i=1\) 的点，可以插在当前环上任意两点中间，会被两侧的点自然定向，方案数 \((2x)^{\overline y}\)，总方案数 \(\dfrac{x!^2\times (2x+y-1)!}{(2x)!}\)。
然后考虑原问题，我们现在要处理的就是 \(\det(D-G)\) 这部分的贡献。
首先矩阵树定理要在原矩阵上去掉一行一列，自然的想法就是把环缩成的虚点对应的行列给删掉。
然后观察 \(\det(D-G)\) 的形式，可以用类似的手法考虑拆系数，再一次发现这部分每个 \(a_i\) 最终的系数 \(\in\{0,1,2\}\)，枚举是这几种情况中的哪一种，也不难算出系数。
那么我们可以把两部分合起来，综合算出 \(f_{x,y}\) 表示 \(x\) 个 \(c_i=0\)，\(y\) 个 \(c_i=1\)，\(n-x-y\) 个 \(c_i=2\) 时对答案的贡献系数。
具体我们依然先枚举环上 \(c_i=0,1\) 的点数 \(x,y\)，剩余不在环上的点只有 \(n-2x-y\) 个，分讨属于上式的哪个部分，需要枚举的只有后面的 \(\prod\) 号上取了几个 \(A\) 和个 \(na_i\)，总的枚举量是三次方的。
时间复杂度 \(\mathcal O(n^3)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005,MOD=998244353;
inline void add(ll&x,const ll&y) { x=(x+y)%MOD; }
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
int n;
ll a[N],A,pwn[N],pwA[N],fac[N],ifac[N],C[N][N],rC[N][N];
ll f[N][N],g[N][N];
//f: coef, g: dp
signed main() {scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%lld",&a[i]),A=(A+a[i])%MOD;pwn[0]=pwA[0]=ifac[0]=fac[0]=1;for(int i=1;i<=n;++i) {pwn[i]=pwn[i-1]*n%MOD,pwA[i]=pwA[i-1]*A%MOD;ifac[i]=ksm(fac[i]=fac[i-1]*i%MOD);}for(int i=0;i<=n;++i) {for(int j=C[i][0]=1;j<=i;++j) {C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;}for(int j=0;j<=i;++j) rC[j][i]=C[i][j];}for(int i=0;i<=n;++i) for(int j=max(3-2*i,0);2*i+j<=n;++j) {//cycle with i a^0/a^2 and j a^1int c=n-2*i-j; ll *bi=rC[i],*bj=rC[j];ll w=fac[i]*fac[i]%MOD*ifac[2*i]%MOD*fac[2*i+j-1]%MOD;for(int x=0,y=c;y>=0;++x,--y) { //|S|=0, x a^0, y a^1add(f[i+x][j+y],w*bi[i+x]%MOD*bj[j+y]%MOD*pwA[x]%MOD*pwn[y]);}for(int x=0,y=c-1;y>=0;++x,--y) { //|S|=1, x a^0, y a^1 in Prodll z=w*(j+y+1)%MOD*bi[i+x]%MOD*bj[j+y]%MOD; add(f[i+x][j+y+1],2*(MOD-z)*pwA[x]%MOD*pwn[y]%MOD);}for(int x=0,y=c-2;y>=0;++x,--y) { //|S|=2, x a^0, y a^1 in Prodll z=w*bi[i+x]%MOD*bj[j+y]%MOD*pwA[x]%MOD*pwn[y]%MOD;add(f[i+x][j+y+2],z*(j+y+2)*(j+y+1));add(f[i+x+1][j+y],(MOD-z)*(i+x+1)*(i+1));}}g[0][0]=1;for(int o=1;o<=n;++o) {ll w1=a[o],w2=a[o]*a[o]%MOD;for(int i=o;i>=0;--i) for(int j=o-i;j>=0;--j) {g[i][j]=(g[i][j]*w2+(i?g[i-1][j]:0)+(j?g[i][j-1]*w1:0))%MOD;}}ll ans=0;for(int i=0;i<=n;++i) for(int j=0;i+j<=n;++j) ans=(ans+f[i][j]*g[i][j])%MOD;printf("%lld\n",ans);return 0;
}
*K. [P9371] Medium
Problem Link
题目大意
给定 \(a_1\sim a_n\)，求一个区间 \([l,r]\) 最大化其中位数的出现次数（长度为偶数可以在中间两个元素中任选一个）。
数据范围：\(n\le 5\times 10^5\)。
思路分析
考虑刻画中位数 \(x\)，要求 \(\ge x\) 的元素比 \(<x\) 的元素多，\(\le x\) 的元素比 \(>x\) 的元素多。
那么设 \(X_i\) 表示 \(2[a_i\ge x]-1\) 的前缀和，\(Y_i\) 表示 \(2[a_i\le x]-1\) 的前缀和。
那么一个区间 \([l,r]\) 中位数为 \(x\) 就要求 \(Y_r\ge Y_{l-1},X_r\ge X_{l-1}\)，这是一个二维偏序问题。
然后考虑对于每个 \(x\) 都解决此问题。
把所有 \((X_i,Y_i)\) 连成线，遇到 \(a_i=x\) 会往右上移动，\(a_i<x\) 往左上移动，\(a_i>x\) 往右上移动。
观察构成折线的结构，发现是若干连续的斜率为 \(-1\) 的线段，两条线段中间夹的一段就是一个 \(a_i=x\) 的点。
那么我们就是要求出距离最远的两条线段，使得在右边的线段上可以选出一个点包含左边线段上至少一个点。
设右侧线段 \(x,y\) 的最大值为 \(R_x,R_y\)，左边线段 \(x,y\) 的最小值为 \(L_x,L_y\)，那么我们可以证明这两条线段合法当且仅当 \(R_x\ge L_x,R_y\ge L_y\)。
那么这又变成了一个二维偏序问题，按 \(x\) 扫描树状数组维护前缀最大值即可。
由于线段树和当前 \(x\) 的出现次数成线性，因此二维数点的总点数是 \(\mathcal O(n)\) 的。
预处理每条线段的 \(L_x,L_y,R_x,R_y\) 可以直接线段树维护区间最大最小前缀和。
时间复杂度 \(\mathcal O(n\log n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5,inf=1e9,MAXV=2e6+5,V=1e6;
typedef array<int,2> pii;
pii operator +(pii x,pii y) { return {min(x[0],y[0]),max(x[1],y[1])}; }
int n,a[MAXN];
struct SegmentTree {pii tr[MAXN<<2]; int tg[MAXN<<2];void adt(int p,int k) { tr[p][0]+=k,tr[p][1]+=k,tg[p]+=k; }void psd(int p) { if(tg[p]) adt(p<<1,tg[p]),adt(p<<1|1,tg[p]),tg[p]=0; }void psu(int p) { tr[p]=tr[p<<1]+tr[p<<1|1]; }void add(int ul,int ur,int k,int l=0,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);}pii qry(int ul,int ur,int l=0,int r=n,int p=1) {if(ul<=l&&r<=ur) return tr[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);}
} X,Y; //X: >=k?1:-1, Y: <=k?1:-1
vector <int> ps[MAXN];
struct FenwickTree {int tr[MAXV]; vector <int> e;void build() { fill(tr,tr+MAXV,-inf); }void upd(int x,int w) { for(e.push_back(x);x<MAXV;x+=x&-x) tr[x]=max(tr[x],w); }int qry(int x) { int s=-inf; for(;x;x&=x-1) s=max(s,tr[x]); return s; }void init() { for(int x:e) for(;x<MAXV;x+=x&-x) tr[x]=-inf; e.clear(); }
} T;
int sequence(int N,vector<int>A) {n=N,T.build();for(int i=1;i<=n;++i) {ps[a[i]=A[i-1]].push_back(i);X.add(i,n,1),Y.add(i,n,-1);}int ans=0;for(int o=1;o<=n;++o) if(ps[o].size()) {vector <int> p{0};for(int z:ps[o]) p.push_back(z),Y.add(z,n,2);p.push_back(n+1);vector <array<int,3>> Q;for(int i=1;i<(int)p.size();++i) {pii x=X.qry(p[i-1],p[i]-1),y=Y.qry(p[i-1],p[i]-1);Q.push_back({x[0],y[0],-i});Q.push_back({x[1],y[1],i});}sort(Q.begin(),Q.end()),T.init();for(int i=0,j;i<(int)Q.size();i=j) {for(j=i;j<(int)Q.size()&&Q[i][0]==Q[j][0];++j) {if(Q[j][2]<0) T.upd(Q[j][1]+V,Q[j][2]);else ans=max(ans,Q[j][2]+T.qry(Q[j][1]+V));}}for(int z:ps[o]) X.add(z,n,-2);}return ans;
}
*L. [P10302] Distance
Problem Link
题目大意
给定 \(n\) 个点的树和参数 \(X\)，把树上距离 \(\le X\) 的点全连起来，\(q\) 次询问标号 \([l,r]\) 的点的导出子图中有多少连通块。
数据范围：\(n\le 3\times 10^5,q\le 6\times10^5\)。
思路分析
这种复杂连通块计数问题考虑找代表元。
一个很精妙的构造是取每个连通块中 bfs 序最小的点作为代表元，我们有一个优美的性质：一个点是代表元当且仅当其不存在 bfs 序小于其的邻居。
我们发现对于 bfs 序递增的三个节点 \(i,j,k\)，分讨他们的 \(\mathrm{LCA}\) 形状可以证明：\(\mathrm{dist}(i,k)\le X,\mathrm{dist}(j,k)\le X\) 时一定有 \(\mathrm{dist}(i,j)\le X\)。
根据这个结论，我们知道对于新图上任意一条路径 \(p_1\to p_2\to\cdots\to p_k\)，如果 \(p_i\) 的 bfs 序大于 \(p_{i-1}\) 和 \(p_{i+1}\)，那么 \(\mathrm{dist}(p_{i-1},p_{i+1})\le X\)，可以直接连边 \(p_{i-1}\to p_{i+1}\) 。
因此我们能把任意一条路径规约成 bfs 序先降后升的路径，那么如果一个点是代表元，bfs 序小于他的点一定至少对应该点的一条终点 bfs 序小于代表元的出边，这和假设不符。
因此我们证明了一个点 \(u\) 是代表元当且仅当点集内不存在 bfs 序小于 \(u\) 的点 \(v\) 满足 \(\mathrm{dist}(u,v)\le X\)。
那么我们只要求出每个点距离 \(\le X\) 的所有点中标号的前驱后继 \(L_u,R_u\)。
距离的限制较为棘手，考虑点分治转成 \(d_u+d_v\le X\)，容易发现这个条件是充分的。
那么我们按 bfs 序从小到大加，找到 \(d_v\le X-d_u\) 的前驱后继，可以用线段树上二分维护。
最终答案就变成数 \(l\in(L_u,u],r\in[u,R_u)\) 的 \(u\) 个数，直接二维数点。
时间复杂度 \(\mathcal O(n\log^2n+q\log n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5,MAXQ=6e5+5,inf=1e9;
int n,m,X,bfn[MAXN],dep[MAXN],siz[MAXN],cur[MAXN],L[MAXN],R[MAXN];
bool vis[MAXN];
vector <int> G[MAXN];
struct SegmentTree {static const int N=1<<19;int tr[N<<1];void init() {fill(tr,tr+(N<<1),inf);for(int i=N;i;i>>=1) tr[i]=0;for(int i=N+n+1;i;i>>=1) tr[i]=0;}void upd(int x,int v) { for(x+=N;x;x>>=1) tr[x]=min(tr[x],v); }void clr(int x) { for(x+=N;tr[x]<inf&&x;x>>=1) tr[x]=inf; }int qpre(int x,int v) {for(x+=N;x^1;x>>=1) if((x&1)&&tr[x^1]<=v) {for(x^=1;x<=N;x=x<<1|(tr[x<<1|1]<=v));return x-N;}return 0;}int qsuf(int x,int v) {for(x+=N;x^1;x>>=1) if((~x&1)&&tr[x^1]<=v) {for(x^=1;x<=N;x=x<<1|(tr[x<<1]>v));return x-N;}return n+1;}
} T;
void solve(int u) {vector <int> a;function<void(int,int)> dfs2=[&](int x,int fz) {siz[x]=1;if(dep[x]<=X) a.push_back(x);for(int y:G[x]) if(!vis[y]&&y!=fz) {dep[y]=dep[x]+1,dfs2(y,x),siz[x]+=siz[y];}};dep[u]=0,dfs2(u,0);sort(a.begin(),a.end(),[&](int x,int y){ return bfn[x]<bfn[y]; });for(int x:a) {L[x]=max(L[x],T.qpre(x,X-dep[x]));R[x]=min(R[x],T.qsuf(x,X-dep[x]));T.upd(x,dep[x]);}for(int x:a) T.clr(x);
}
void dfs1(int u) {vis[u]=true,solve(u);for(int v:G[u]) if(!vis[v]) {int rt=0,tot=siz[v];function<void(int,int)> dfs3=[&](int x,int fz) {cur[x]=tot-siz[x];for(int y:G[x]) if(!vis[y]&&y!=fz) {dfs3(y,x),cur[x]=max(cur[x],siz[y]);}if(!rt||cur[x]<cur[rt]) rt=x;};dfs3(v,u),dfs1(rt);}
}
struct FenwickTree {int tr[MAXN],s;void add(int x,int v) { for(;x;x&=x-1) tr[x]+=v; }int qry(int x) { for(s=0;x<=n;x+=x&-x) s+=tr[x]; return s; }
} F;
vector <array<int,2>> Q[MAXN],M[MAXN];
int ans[MAXQ];
signed main() {scanf("%d%d%d",&n,&m,&X);for(int u=2,v;u<=n;++u) {scanf("%d",&v),G[u].push_back(v),G[v].push_back(u);}for(int i=1;i<=n;++i) L[i]=0,R[i]=n+1;queue <int> q; q.push(1);for(int o=1;o<=n;++o) {int u=q.front(); q.pop(),bfn[u]=o;for(int v:G[u]) if(!bfn[v]) q.push(v);}T.init(),dfs1(1);for(int i=1;i<=n;++i) {M[i].push_back({L[i],-1}),M[i].push_back({i,1});M[R[i]].push_back({L[i],1}),M[R[i]].push_back({i,-1});}for(int i=1,l,r;i<=m;++i) scanf("%d%d",&l,&r),Q[r].push_back({l,i});for(int i=1;i<=n;++i) {for(auto z:M[i]) F.add(z[0],z[1]);for(auto z:Q[i]) ans[z[1]]=F.qry(z[0]);}for(int i=1;i<=m;++i) printf("%d\n",ans[i]);return 0;
}
