2021 集训队互测题解 (Original)

~~题解丢失.jpg~~

然后找到了

但是只写了12个题

集训队互测 2021 题解

~~假做法/乱搞大集合~~

R1T1 #4 愚蠢的在线法官

Problem

给一棵 $n$ 个点的有根树，点有点权 $v_i$ 。

给一个长度为 $k$ 的序列 $a$ ，定义一个 $k\times k$ 的矩阵 $B$ ，其中 $B_{i,j}=v_{LCA(a_i,a_j)}$ 。

求矩阵的行列式值，模 $998244353$ 。

$n,k\leq 5\times 10^5$

$2s,512MB$

Sol

如果存在两个 $a_i$ 相同，则显然行列式为 $0$ 。

考虑消元求行列式的方式，先消根所在的行列，再依次消每个子树内部。

考虑根上的情况，显然根所在的行列全部相等，因此消元这一行会使得剩下的 $(n-1)\times(n-1)$ 的矩阵整体减去根的权值，答案乘上根的权值。

接着考虑消子树的情况，如果 $u,v$ 属于不同子树，则它们的LCA是根。设其中一个子树内部点编号为 $2\sim k$ ，则所有矩阵 $2\sim k$ 行的 $k+1\sim n$ 位置值相同，矩阵 $k+1\sim n$ 行的 $2\sim k$ 位置相同。

如果只考虑 $2\sim k$ 的行列，得到的子矩阵满秩，则对这部分消元后，这部分内部的第 $i$ 行在 $2\sim k$ 位置中只有位置 $i$ 有值，在 $k+1\sim n$ 位置的值相同。

因此，如果现在用 $2\sim k$ 的行去消去后面行的 $2\sim k$ 位置，则后面每一行减去的值相同，因此可以看成给后面整体减去一个值。

因此考虑求出 $f_u$ 表示只考虑 $u$ 子树内的行列，假设现在还有额外一行一列，这一行一列的元素都是 $1$ ，则对这行之外的部分消元后，对这一行消元时会减去多少。

假设当前在消 $u$ 的子树，当前整体减去的值为 $vl$ ，则如果根这一行存在，消去根之后，答案会乘上 $v_u-vl$ ，随后减去的值会变成 $v_u$ ，且 $f_u$ 会增加 $\frac 1{v_u-vl}$ 。

接着考虑消一个子树 $v$ 内部的情况，因为之前消去的部分和这个子树内部的点LCA都是根，因此用外部消子树内部时，内部会整体减去 $vl+f_u*v_u^2$ 。然后考虑 $f_u$ 改变的值。在消另外一行时，如果先消去前面部分，则后面部分的值为 $1-f_u$ 。但因为 $v$ 子树与之前部分之间的值为 $v_u$ ，因此现在 $v$ 子树内位置在这一行的值为 $1-v_uf_u$ 。且消元后， $v$ 子树内的行最后一个位置的值也会从 $1$ 变为 $1-v_uf_u$ 。

因此加入这个子树后 $f'_u=f_u+f_v(1-v_uf_u)^2$ 。因此 $O(n)$ dfs即可得到答案。

上述做法不能很好的处理根所在行为 $0$ 的情况，因为此时消元做法可能从外部找一行来交换，从而可能有解。但因为点权是随的，因此这样能过。

也有可能出现这种情况就意味着行列式一定是 $0$ ，但我不会分析。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 500050
#define mod 998244353
int n,k,v[N],s[N],a,b,head[N],cnt,is[N],as=1;
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
struct edge{int t,next;}ed[N*2];
void adde(int f,int t)
{
	ed[++cnt]=(edge){t,head[f]};head[f]=cnt;
	ed[++cnt]=(edge){f,head[t]};head[t]=cnt;
}
int dfs(int u,int fa,int vl)
{
	int sv=0,tp=pw(mod+v[u]-vl,2);
	if(is[u])
	{
		as=1ll*as*(mod+v[u]-vl)%mod;
		sv=pw(mod+v[u]-vl,mod-2);
	}
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)
	{
		int v1=dfs(ed[i].t,u,(vl+1ll*tp*sv)%mod);
		sv=(sv+1ll*v1*pw(mod+1-1ll*sv*(mod+v[u]-vl)%mod,2))%mod;
	}
	return sv;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&v[i]);
	for(int i=1;i<=k;i++)scanf("%d",&s[i]);
	sort(s+1,s+k+1);
	for(int i=1;i<k;i++)if(s[i]==s[i+1]){printf("0\n");return 0;}
	for(int i=1;i<=k;i++)is[s[i]]=1;
	for(int i=1;i<n;i++)scanf("%d%d",&a,&b),adde(a,b);
	dfs(1,0,0);
	printf("%d\n",as);
}

R1T2 #25 这是一道集训队胡策题

Problem

给一个 $n\times n$ 的 01 矩阵 $c$ ，求有多少个长度为 $n$ 的 01 序列对 $a,b$ ，满足 $\forall i,j$ ， $c_{i,j}=a_i,c_{i,j}=b_j$ 中至少有一者成立。答案模 $998244353$ 。

$n\leq 5000$

$2s,512MB$

Sol

暴力做法：dfs，每次枚举一个 $a_i$ 的值，把能确定的都确定下来。

注意到对于一行，如果 $c_{i,j}=1$ ，则 $a_i=0$ 时能确定这个 $b_j$ 。否则 $a_i=1$ 时能确定这个 $b_j$ 。因此每次枚举后将列分成了不相交的两部分。因此行*列的和不会增加。

而显然可以用行*列的复杂度进行枚举和确定，又因为dfs不会超过 $n$ 层，因此这样复杂度不超过 $O(n^3)$ ，可以得65分。

使用以下方式，可能可以做到 $O(\frac{n^3}{32})$ ：

使用bitset+_Find_Next
每次选择一行使得 $01$ 个数中最小的最大。

然后能卡过去。

正常做法：考虑两行的情况，如果存在一位使得第一行为 $1$ 第二行为 $0$ ，则如果第二行的 $a$ 为 $1$ ，则第一行的 $a$ 为 $1$ 。

因此如果没有相同的行，则任意两行一定满足如果某一行的 $a$ 为 $1$ ，则另外一行的 $a$ 也为 $1$ 。

此时所有这种关系可以看成有向边，图构成竞赛图。因此它缩强连通后形成一条链。链上满足前面的行的 $1$ 被后面的行的 $1$ 包含。

因此所有 $a_i$ 为 $1$ 的行是链的一段后缀，又因为链上后面的行 $1$ 个数更多，进一步可以得到一定存在一个 $k$ ，使得一行 $a_i=1$ 当且仅当这一行 $1$ 的个数大于等于 $k$ 。此时可以枚举 $k$ ，判断可以使用bitset前缀and预处理，复杂度 $O(\frac{n^2}{32})$

对于相同行的情况，如果两个相同行的 $a_i$ 不同，则可以发现所有的 $b_j$ 都等于 $c_{i,j}$ ，这种情况可以 $O(\frac{n^2}{32})$ 判断。否则所有 $a_i$ 相同，可以将它们合并，变为上述问题。复杂度 $O(\frac{n^3}{32})$ 。

也有另外一种处理方式：将所有行按照 $1$ 个数排序，然后依次看相邻两行会不会合并。合并当且仅当两行 $i,j$ 使得 $i\and j<i,j<i\or j$ ，然后可以记录合并的这些行的and和or，即可判断。合并时只需要依次考虑每一个位置，如果能合并，就向两侧依次判断能否合并，这样只会判断 $O(n)$ 次。合并后，一些相同行满足条件当且仅当它们没有被合并起来。

复杂度 $O(\frac{n^2}{32})$ （不考虑输入）。

Code

做法一：

#include<cstdio>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
using namespace std;
#define N 5050
#define mod 998244353
int n,f1[N],f2[N],as;
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
char s[N][N];
bitset<N> s0[N][2],s1[N][2],S0,S1,tr;
struct sth{int a,b;};
void solve(vector<int> v1,vector<int> v2)
{
	if(!v1.size()||!v2.size()){as=(as+pw(2,v1.size()+v2.size()))%mod;return;}
	int fg1=0,fg2=0,fg3=0;
	for(int i=0;i<v1.size();i++)
	{
		int f1=0,f2=0;
		for(int j=0;j<v2.size();j++)
		if(s[v1[i]][v2[j]]=='1')f1++;
		else f2++;
		int v3=min(f1,f2);
		if(v3>fg1)fg1=v3,fg2=v1[i],fg3=0;
	}
	for(int i=0;i<v2.size();i++)
	{
		int f1=0,f2=0;
		for(int j=0;j<v1.size();j++)
		if(s[v1[j]][v2[i]]=='1')f1++;
		else f2++;
		int v3=min(f1,f2);
		if(v3>fg1)fg1=v3,fg2=v2[i],fg3=1;
	}
	if(!fg1)
	{
		as=(as+1ll*pw(2,v1.size())+pw(2,v2.size())+mod-1)%mod;
		return;
	}
	for(int d=0;d<2;d++)
	{
		S0.reset();S1.reset();
		for(int i=0;i<v1.size();i++)f1[v1[i]]=0,S0.set(v1[i],1);
		for(int i=0;i<v2.size();i++)f2[v2[i]]=0,S1.set(v2[i],1);
		int fg=1;
		for(int i=0;i<v1.size();i++)f1[v1[i]]=0;
		for(int i=0;i<v2.size();i++)f2[v2[i]]=0;
		queue<sth> fu;
		if(!fg3)f1[fg2]=d+1,fu.push((sth){fg2,0});
		else f2[fg2]=d+1,fu.push((sth){fg2,1});
		while(!fu.empty()&&fg)
		{
			sth t1=fu.front();fu.pop();
			int d1=t1.a,d2=t1.b,vl=f1[d1]-1;
			if(!d2)
			{
				tr=S1&s0[d1][vl^1];
				int nw=0;
				while(1)
				{
					int nt=tr._Find_next(nw);
					if(nt==tr.size())break;
					if(f2[nt])fg|=f2[nt]!=f1[d1];
					else f2[nt]=3^f1[d1],fu.push((sth){nt,1});
					nw=nt;
				}
			}
			else
			{
				vl=f2[d1]-1;
				tr=S0&s1[d1][vl^1];
				int nw=0;
				while(1)
				{
					int nt=tr._Find_next(nw);
					if(nt==tr.size())break;
					if(f1[nt])fg|=f1[nt]!=f2[d1];
					else f1[nt]=3^f2[d1],fu.push((sth){nt,0});
					nw=nt;
				}
			}
		}
		if(!fg)continue;
		vector<int> t1,t2;
		for(int i=0;i<v1.size();i++)if(!f1[v1[i]])t1.push_back(v1[i]);
		for(int i=0;i<v2.size();i++)if(!f2[v2[i]])t2.push_back(v2[i]);
		solve(t1,t2);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)s0[i][s[i][j]-'0'].set(j,1);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)s1[i][s[j][i]-'0'].set(j,1);
	vector<int> v1,v2;
	for(int i=1;i<=n;i++)v1.push_back(i),v2.push_back(i);
	solve(v1,v2);
	printf("%d\n",as);
}

做法二有空再补

R1T3 #42 树上的孤独

Problem

给出一棵 $n$ 个点的有根树 $T_1$ 和 $m$ 个点的有根树 $T_2$ ，每个点有一个颜色 $c_i$ 。

$q$ 次操作，有两种类型：

给出 $u,c$ ，将 $T_1$ 中 $u$ 的颜色改为 $c$ 。
给出 $u,v,d_1,d_2$ ，求 $T_1$ 中 $u$ 子树内距离 $u$ 不超过 $d_1$ 的点和 $T_2$ 中 $v$ 子树内距离 $v$ 不超过 $d_2$ 的点中的颜色总数。

对 $c,d_1,d_2$ 强制在线。

$n\leq 20,m\leq 2\times 10^5,q\leq 10^6$

$2s,1024MB$

Sol

考虑只有 $T_2$ 的情况，对于每个点的子树，维护这个子树中每种颜色出现的最低深度。这可以通过对每个点维护动态开点线段树，dfs时线段树合并维护。

再对于每个点使用一棵权值线段树，维护对于每个深度有多少种颜色第一次出现是在这个深度。dfs时先合并这个线段树，随后合并颜色的线段树时，合并叶子时在这个线段树上修改即可。

两部分都可以可持久化，时间空间复杂度均为 $O(m\log m)$ 。询问在对应的答案线段树中查即可。

考虑原问题，修改不会改 $T_2$ ，因此可以先求出上面的部分。

对于一次询问， $T_1$ 中符合条件的点不超过 $n$ 个，因此答案最多在 $T_2$ 的答案上增加 $n$ ，相当于判断 $T_1$ 中的这些颜色是否在 $T_2$ 中对应部分出现。

这相当于询问 $v$ 子树内，距离 $v$ 最近的颜色为 $c$ 的点是否距离不超过 $d_2$ 。使用上面的线段树即可 $O(\log n)$ 回答询问。

这样的复杂度为 $O((nq+m)\log m)$ ，通过卡常（把询问线段树换成4/8叉,...）可以卡过去。

可以注意到强制在线不加密 $u,v$ ，因此可以每次询问时对于 $T_1$ 中的每个颜色都询问一次距离，然后变为离线的问题。

在离线的情况下，可以使用树链剖分+合并的做法，使用数组维护第一个线段树中的最近距离，对于一条重链使用同一个数组，然后将轻子树内的暴力加入。这样即可离线 $O(1)$ 回答询问，处理的复杂度为 $O(m\log m)$ 。

注意实现细节，即可在这种合并上合并答案线段树，总复杂度 $O(nq+m\log m)$ 。

Code

算法一：

//surrender
#include<cstdio>
#include<vector>
#include<algorithm>
#pragma GCC optimize("-Ofast")
using namespace std;
#define N 200500
#define M 15000500
#define S 25
int n,m,q,a,b,head[N],cnt,f[N],dep[N],ls,op,c,d;
struct edge{int t,next;}ed[N*2];
void adde(int f,int t)
{
	ed[++cnt]=(edge){t,head[f]};head[f]=cnt;
	ed[++cnt]=(edge){f,head[t]};head[t]=cnt;
}
void dfs(int u,int fa)
{
	f[u]=fa;
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs(ed[i].t,u);
}
int cl[S];
vector<int> sn[S];
int cr[N],id2[N],c3;
int rt1[N],ch1[M][2],su[M],c1,ss,vv,id;
int modify1(int x,int l,int r)
{
	int st=++c1;su[st]=su[x]+vv;ch1[st][0]=ch1[x][0];ch1[st][1]=ch1[x][1];
	if(l==r)return st;
	int mid=(l+r)>>1;
	if(mid>=ss)ch1[st][0]=modify1(ch1[x][0],l,mid);
	else ch1[st][1]=modify1(ch1[x][1],mid+1,r);
	return st;
}
int merge1(int x,int y,int le)
{
	if(!x||!y)return x+y;
	int st=++c1;su[st]=su[x]+su[y];
	if(le==1)return st;
	ch1[st][0]=merge1(ch1[x][0],ch1[y][0],le-(le>>1));
	ch1[st][1]=merge1(ch1[x][1],ch1[y][1],le>>1);
	return st;
}
int query1(int x,int l,int r,int l1,int r1)
{
	if(!x||(l==l1&&r==r1))return su[x];
	int mid=(l+r)>>1;
	if(r1<=mid)return query1(ch1[x][0],l,mid,l1,r1);
	else if(l1>mid)return query1(ch1[x][1],mid+1,r,l1,r1);
	else return query1(ch1[x][0],l,mid,l1,mid)+query1(ch1[x][1],mid+1,r,mid+1,r1);
}
int rt2[N],ch2[M][8],c2,vl[M];
void modify2(int x,int l,int r,int s,int v)
{
	if(l>r)return;
	if(l==r)
	{
		int ls=vl[x],nw=v;
		if(!ls)ls=1e9;
		if(ls<=nw)return;
		vl[x]=nw;
		if(ls<=m)ss=ls,vv=-1,rt1[id]=modify1(rt1[id],1,m);
		ss=nw,vv=1,rt1[id]=modify1(rt1[id],1,m);
		return;
	}
	int mid=(l+r)>>1,fg=mid<s;
	int l1,r1;
	if(!fg)l1=l,r1=mid;else l1=mid+1,r1=r;
	int mid1=(l1+r1)>>1,f2=mid1<s;
	int l2,r2;
	if(!f2)l2=l1,r2=mid1;else l2=mid1+1,r2=r1;
	int mid2=(l2+r2)>>1;
	int ls=fg*4+f2*2+(mid2<s);
	if(!ch2[x][ls])ch2[x][ls]=++c2;
	if(mid2>=s)modify2(ch2[x][ls],l2,mid2,s,v);
	else modify2(ch2[x][ls],mid2+1,r2,s,v);
}
int merge2(int x,int y,int l,int r)
{
	if(!x||!y)return x+y;
	int st=++c2;
	if(l==r)
	{
		int tp=max(vl[x],vl[y]);
		ss=tp,vv=-1;rt1[id]=modify1(rt1[id],1,m);
		vl[st]=min(vl[x],vl[y]);return st;
	}
	for(int i=0;i<8;i++)
	{
		int l1=l,r1=r;
		for(int j=2;j>=0;j--)
		{
			int mid=(l1+r1)>>1;
			if((i>>j)&1)l1=mid+1;else r1=mid;
		}
		ch2[st][i]=merge2(ch2[x][i],ch2[y][i],l1,r1);
	}
	return st;
}
void dfs1(int u,int fa)
{
	rt1[u]=++c1;rt2[u]=++c2;dep[u]=dep[fa]+1;
	id=u;
	modify2(rt2[u],1,c3,cr[u],dep[u]);
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)
	{
		dfs1(ed[i].t,u);
		rt1[u]=merge1(rt1[u],rt1[ed[i].t],m);
		id=u;
		rt2[u]=merge2(rt2[u],rt2[ed[i].t],1,c3);
	}
}
int fr[N][7];
void init_fr()
{
	for(int s=1;s<=m;s++)
	{
		int l=1,r=c3;
		for(int j=1;j<=6;j++)
		{
			int mid=(l+r)>>1,fg=mid<s;
			int l1,r1;
			if(!fg)l1=l,r1=mid;else l1=mid+1,r1=r;
			int mid1=(l1+r1)>>1,f2=mid1<s;
			int l2,r2;
			if(!f2)l2=l1,r2=mid1;else l2=mid1+1,r2=r1;
			int mid2=(l2+r2)>>1;
			int ls=fg*4+f2*2+(mid2<s);fr[s][j]=ls;
			if(mid2>=s)l=l2,r=mid2;
			else l=mid2+1,r=r2;
		}
	}
}
int que1(int x,int d){return query1(rt1[x],1,m,1,min(m,dep[x]+d-1));}
int que2(int x,int c)
{
	if(!id2[c])return 0;c=id2[c];
	int nw=rt2[x];
	for(int j=1;j<=6;j++)
	{
		nw=ch2[nw][fr[c][j]];
		if(!nw||vl[nw])return vl[nw];
	}
	return 0;
}
vector<int> fu;
void dfs2(int x,int d)
{
	if(!d)return;
	fu.push_back(cl[x]);
	for(int i=0;i<sn[x].size();i++)dfs2(sn[x][i],d-1);
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;i++)scanf("%d%d",&a,&b),adde(a,b);
	dfs(1,0);
	for(int i=2;i<=n;i++)sn[f[i]].push_back(i);
	for(int i=1;i<=n;i++)head[i]=0;cnt=0;
	for(int i=1;i<m;i++)scanf("%d%d",&a,&b),adde(a,b);
	for(int i=1;i<=n;i++)scanf("%d",&cl[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&cr[i]);
		if(!id2[cr[i]])id2[cr[i]]=++c3;
		cr[i]=id2[cr[i]];
	}
	dfs1(1,0);init_fr();
	while(q--)
	{
		scanf("%d",&op);
		if(op==2)scanf("%d%d",&a,&b),cl[a]=b;
		else
		{
			scanf("%d%d%d%d",&a,&b,&c,&d);
			c^=ls;d^=ls;c++;d++;
			fu.clear();
			dfs2(a,c);
			sort(fu.begin(),fu.end());
			vector<int> f2;f2.push_back(fu[0]);
			for(int i=1;i<fu.size();i++)if(fu[i]!=fu[i-1])f2.push_back(fu[i]);
			int as=que1(b,d);
			for(int i=0;i<f2.size();i++)
			{
				int c1=f2[i],ds=que2(b,c1);
				if(!ds||ds>=dep[b]+d)as++;
			}
			printf("%d\n",ls=as);
		}
	}
}

R2T1 #6 序列

Problem

你需要构造一个长度为 $n$ 的正整数序列 $a$ ，满足如下形式的 $m$ 个要求：

$a_x,a_y,a_z$ 的中位数为 $c$ 。

输出任意方案或输出无解。

$n,m\leq 10^5$

$1s,512MB$

Sol

考虑2-SAT，对每个 $i$ 和每种权值 $j$ ，记一个点 $s_{i,j}$ 表示 $a_i$ 是否小于等于 $j$ ，则有：

a_i\leq j+1 \to a_i\leq j\\ !(a_i\leq j)\to !(a_i\leq j+1)

可以发现这样的一条链就能表示 $a_i$ 的取值。

然后对于一个限制 $(x,y,z,c)$ ，可以发现这相当于如果有一个点权小于 $c$ ，则另外两个点都需要大于等于 $c$ 。如果有一个点权大于 $c$ ，则另外两个点都需要小于等于 $c$ 。因此这可以看成若干个2-SAT的限制。

对于每个点可以只保留和这个点有关的限制的权值，只保留这些权值构成的链。这样的总点数就是 $O(n+m)$ 的。

复杂度 $O(n+m)$

Code

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 100500
int n,m,s[N][4],lb[N],c2,id[3],as[N];
vector<int> st[N];
int head[N*10],cnt,dfn[N*10],low[N*10],fr[N*10],s1[N*10],ct,c1,ti;
struct edge{int t,next;}ed[N*30];
void adde(int f,int t){ed[++cnt]=(edge){t,head[f]};head[f]=cnt;}
void dfs(int u)
{
	s1[++ct]=u;dfn[u]=low[u]=++ti;
	for(int i=head[u];i;i=ed[i].next)
	if(!dfn[ed[i].t])dfs(ed[i].t),low[u]=min(low[u],low[ed[i].t]);
	else if(!fr[ed[i].t])low[u]=min(low[u],dfn[ed[i].t]);
	if(low[u]==dfn[u])
	{
		int tp=++c1;
		while(1)
		{
			fr[s1[ct]]=tp;ct--;
			if(s1[ct+1]==u)break;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<4;j++)scanf("%d",&s[i][j]);
		for(int j=0;j<3;j++)st[s[i][j]].push_back(s[i][3]);
	}
	for(int i=1;i<=n;i++)
	{
		st[i].push_back(1);st[i].push_back(1e9+1);
		sort(st[i].begin(),st[i].end());
		vector<int> ls;ls.push_back(st[i][0]);
		for(int j=1;j<st[i].size();j++)if(st[i][j]!=st[i][j-1])ls.push_back(st[i][j]);
		st[i]=ls;
	}
	for(int i=1;i<=n;i++)lb[i]=c2+1,c2+=st[i].size();
	for(int i=1;i<=n;i++)
	{
		adde(lb[i]+c2,lb[i]);adde(lb[i]+st[i].size()-1,lb[i]+st[i].size()-1+c2);
		for(int j=1;j<st[i].size();j++)adde(lb[i]+j,lb[i]+j-1),adde(lb[i]+j-1+c2,lb[i]+j+c2);
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<3;j++)id[j]=lower_bound(st[s[i][j]].begin(),st[s[i][j]].end(),s[i][3])-st[s[i][j]].begin()+lb[s[i][j]];
		for(int j=0;j<3;j++)for(int k=0;k<3;k++)if(j!=k)adde(id[j]+c2,id[k]),adde(id[j]+1,id[k]+1+c2);
	}
	for(int i=1;i<=c2*2;i++)if(!dfn[i])dfs(i);
	for(int i=1;i<=c2;i++)if(fr[i]==fr[i+c2]){printf("NO\n");return 0;}
	for(int i=1;i<=n;i++)for(int j=0;j<st[i].size();j++)if(fr[lb[i]+j]<fr[lb[i]+j+c2])as[i]=st[i][j];
	printf("YES\n");
	for(int i=1;i<=n;i++)printf("%d ",as[i]);
}

R2T2 #20 Imbalance

Problem

给定 $n$ 以及偶数 $k$ ，称一个长度为 $n$ 的 01 串是好的，当且仅当它的每一个长度为 $k$ 的连续子串中 $1$ 的数量不等于 $\frac k2$ 。

给一个长度为 $m(m<k)$ 的串 $s$ ，求有多少个长度为 $n$ 的好的串以 $s$ 开头。答案模 $998244353$ .

$n\leq 114$

$2s,512MB$

Sol

对于 $k$ 小的情况，可以直接状压dp，复杂度 $O(n2^k)$ 。

上面的做法也可以看成用轮廓线 $dp$ 的方式填一个宽度为 $k$ 的二维矩阵。因此在 $k$ 大的情况中考虑竖向 $dp$ 。

先考虑 $m=0$ 的情况，相当于一个 $\lceil\frac nk\rceil$ 行的方格，除去最后一行外每一行宽度为 $k$ ，要求对于每个位置，这一行这个位置之后的位置以及下一行这个位置及之前的位置中 $1$ 的数量不等于 $\frac k2$ 。这相当于这一行 $1$ 的个数加上下一行这个位置及之前的 $1$ 个数，再减去上一行这个位置及之前的 $1$ 个数。

因此考虑枚举除去最后一行外，每一行填的 $1$ 个数，这样的复杂度为 $O(k^{\frac nk})$ 。

同时可以注意到，如果有一行的个数大于 $\frac k2$ ，另外一行小于 $\frac k2$ ，则一定会不合法，因此可以分别计算所有 $c_i<\frac k2$ 的情况和大于的情况，这里考虑前者。

设第 $i$ 行填了 $c_i$ 个，且第 $i$ 行前 $j$ 个位置填了 $s_{i,j}$ 个，则相当于如下要求：

$s_{i,0}=0,s_{i,k}=c_i,0\leq s_{i,j+1}-s_{i,j}\leq 1$
$\forall i,j,s_{i+1,j}-s_{i,j}\neq \frac k2-c_i$ （如果 $s_{i+1,j}$ 存在）

因此暴力做法可以设 $dp_{i,s_j}$ 表示填了前 $i$ 列，当前最后一列的 $s$ 为 $s_j$ 的方案数，复杂度为 $O(k*(\frac k2)^{2*\frac nk})$ ，可以过 $n\leq 66$ 。

注意到每一行的变化是独立的，对于宽度为 $k$ 的行，可以看成从 $(0,0)$ 走到 $x=k$ ，每一步可以向右或者向右上走一步。

而相邻两个的限制可以看成，如果第 $i+1$ 条折线从 $(\frac k2-c_i,0)$ 开始，第 $i$ 条这些从 $(0,0)$ 开始，两条折线不相交。

因此多条直线可以放在一起，具体来说，设 $n=ak+b$ ，可以看成 $a+1$ 条折线，前 $a$ 条折线中，第 $i$ 条从 $(0,\sum_{j=i}^{a}\frac k2-c_j)$ 开始，走到 $(k,c_i+\sum_{j=i}^{a}\frac k2-c_j)$ ，最后一条折线从 $(0,0)$ 开始，走到 $(b,c_{a+1})$ ，求所有折线不相交的方案数。

因此考虑LGV引理，设 $f_{i,j}$ 表示从第 $i$ 个起点到第 $j$ 个终点的方案数，考虑计算 $f$ 的行列式。

但此时不一定只有对应位置的连线不相交，可能出现从最后一个终点的下方绕过去的情况。

此时可以钦定 $(b,c_{a+1})$ 右下角部分是不能走的，这样LGV引理算出来的就是所有对应位置连线且不相交的方案数。

考虑 $m$ 任意的情况，相当于给第一条折线一个上界。考虑看成所有路径都不能超过上界，在此基础上再用LGV引理。

此时LGV中的路径数相当于，给定起点 $s$ 和终点 $t$ ，从 $(0,s)$ 走到 $(k,t)$ 或者 $(b,t)$ ，满足：

不经过下界，即 $x>b$ 时 $y$ 不能小于 $c_{k+1}$ 。
不超过上界，即 $\forall i\in[k-m,k-1]$ ， $x=i$ 时 $y$ 不能大于 $(\sum_{i=1}^a\frac k2-c_j)+\frac k2$ 减去 $s$ 的后 $k-i$ 位中 $1$ 的个数的值。

这只和四个值 $s,t,c_{k+1},(\sum_{i=1}^a\frac k2-c_j)$ 有关，但枚举后两个值再 dp 是 $O(n^5)$ 的。

考虑先枚举最后一个值，可以 $dp$ 出 $x=0$ 到 $x=b$ 的答案，以及 $x=b$ 到 $x=k$ 的答案和总的答案，询问时考虑容斥掉经过下界的部分，因为下界不超过 $k$ ，询问复杂度不超过 $k$ 。

这样 $dp$ 的复杂度为 $O(n^4)$ ，总复杂度为 $O(n^4+(\frac k2)^{\frac nk}(\frac nk)^2(\frac k2+\frac nk))$ ，可以通过。

询问可以通过优先枚举 $c_{a+1}$ 把容斥的过程分到每一步或者前缀和做到 $O(1)$ ，这样复杂度为 $O(n^4+(\frac k2)^{\frac nk}(\frac nk)^3)$

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 120
#define M 1050000
#define mod 998244353
int n,m,k,li[N],as;
char t[N];
int dp[N][N],f[N][N][N],g[N][N][N],h[N][N][N];
int vl[N],l1[N],r1[N],s[N][N];
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
void doit()
{
	int sl=(n-1)/k+1,ls=n-(sl-1)*k;
	for(int i=sl;i>=1;i--)
	{
		r1[i]=l1[i]+vl[i-1];
		if(i)l1[i-1]=l1[i]+k/2-vl[i-2];
	}
	for(int i=1;i<=sl;i++)for(int j=1;j<sl;j++)s[i][j]=f[l1[1]][l1[i]][r1[j]];
	for(int i=1;i<=sl;i++)s[i][sl]=h[l1[1]][l1[i]][r1[sl]];
	int v1=1;
	for(int i=1;i<=sl;i++)
	{
		int tp=i;for(int j=sl;j>=i;j--)if(s[j][i])tp=j;
		if(i!=tp)
		{
			v1=mod-v1;
			for(int j=1;j<=sl;j++)swap(s[i][j],s[tp][j]);
		}
		v1=1ll*v1*s[i][i]%mod;
		int rv=pw(s[i][i],mod-2);
		for(int j=i+1;j<=sl;j++)
		{
			int tp=1ll*(mod-1)*s[j][i]%mod*rv%mod;
			for(int l=i;l<=sl;l++)s[j][l]=(s[j][l]+1ll*s[i][l]*tp)%mod;
		}
	}
	as=(as+v1)%mod;
}
void dfs(int d)
{
	if(d==(n-1)/k){doit();return;}
	for(int i=0;i<k/2;i++)vl[d]=i,dfs(d+1);
}
void solve()
{
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	memset(h,0,sizeof(h));
	for(int i=1;i<=k;i++)
	if(m<k-i)li[i]=-1;
	else
	{
		li[i]=k/2-1;
		for(int j=m-(k-i)+1;j<=m;j++)li[i]-=t[j]=='1';
		if(li[i]<0)return;
	}
	li[0]=-1;
	for(int i=k;i>=0;i--)if(li[i]==-1)li[i]=li[i+1];
	int hl=(n-1)/k,ls=n-k*hl;
	for(int s=0;s<=n/2;s++)
	{
		for(int i=0;i<=s+li[k];i++)
		{
			for(int j=0;j<=k;j++)for(int l=0;l<=s+li[k]+1;l++)dp[j][l]=0;
			dp[k][i]=1;
			for(int j=k-1;j>=0;j--)for(int l=0;l<=s+li[j];l++)dp[j][l]=(dp[j+1][l]+dp[j+1][l+1])%mod;
			for(int l=0;l<=s+li[0];l++)f[s][l][i]=dp[0][l];
			for(int l=0;l<=s+li[ls];l++)g[s][l][i]=dp[ls][l];
		}
		for(int i=0;i<=s+li[ls];i++)
		{
			for(int j=0;j<=ls;j++)for(int l=0;l<=s+li[ls]+1;l++)dp[j][l]=0;
			dp[ls][i]=1;
			for(int j=ls-1;j>=0;j--)for(int l=0;l<=s+li[j];l++)dp[j][l]=(dp[j+1][l]+dp[j+1][l+1])%mod;
			for(int l=0;l<=s+li[0];l++)h[s][l][i]=dp[0][l];
		}
	}
	for(int i=0;i<=ls;i++)
	{
		vl[hl]=i;dfs(0);
		for(int s=0;s<=n/2;s++)
		for(int x=0;x<=s+li[k]&&x<=i;x++)
		for(int y=x;y<=s+li[k];y++)
		f[s][x][y]=(f[s][x][y]+mod-1ll*h[s][x][i]*g[s][i][y]%mod)%mod;
	}
}
int dp2[2][M],is[M];
int solve1()
{
	for(int i=0;i<1<<k;i++)
	{
		int ct=0;
		for(int j=1;j<=k;j++)if((i>>(j-1))&1)ct++;
		if(ct==k/2)is[i]=1;
	}
	dp2[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int d=0;d<2;d++)if(i>m||t[i]-'0'==d)
		for(int j=0;j<1<<k;j++)
		{
			int nt=(j<<1|d)&((1<<k)-1);
			if(i<k||!is[nt])dp2[i&1][nt]=(dp2[i&1][nt]+dp2[~i&1][j])%mod;
		}
		for(int j=0;j<1<<k;j++)dp2[~i&1][j]=0;
	}
	int as=0;
	for(int j=0;j<1<<k;j++)as=(as+dp2[n&1][j])%mod;
	return as;
}
int main()
{
	scanf("%d%d%d",&n,&k,&m);
	if(m)scanf("%s",t+1);
	if(k<=20)
	{
		printf("%d\n",solve1());
		return 0;
	}
	n-=m;
	solve();
	for(int i=1;i<=m;i++)t[i]^=1;
	solve();
	printf("%d\n",as);
}

R2T3 #33 学姐买瓜

Problem

给定 $n,m$ ，进行 $n$ 次如下类型的操作：

加入一个区间，区间端点都是整数且在 $[1,m]$ 间。
询问 $[l,r]$ 中最多能选出多少个两两不相交的区间。

$n,m\leq 3\times 10^5$

$1s,256MB$

Sol

考虑贪心取区间，每次选出当前能选的中 $r$ 最小的，然后选这个区间，将 $l$ 移动到这个区间的 $r$ 右侧。

相当于记录 $nt_i$ 表示所有 $l\geq i$ 的区间 $[l,r]$ 中最小的 $r+1$ 。选区间的数量即为从 $l$ 开始每次令 $l'=nt_l$ ，不超过 $r$ 时能跳的步数。

那么可以维护一个单调栈，则加入一个区间相当于区间 $nt$ 赋值。

考虑用边权表示跳的次数，则将 $[l,r]$ 的 $nt$ 设为 $k$ 相当于将 $l$ 的父亲设为 $l+1$ ，边权为 $0$ ，...，将 $r-1$ 的父亲设为 $r$ ，边权为 $0$ ，将 $r$ 的父亲设为 $k$ ，边权为 $1$ 。

可以发现这样相当于区间清空再加入一个单点，总共只会修改 $O(n)$ 次，因此使用set维护所有连向父亲的边不是连向 $i+1$ 边权为 $0$ 的，然后LCT维护即可。

复杂度 $O((n+m)\log m)$

Code

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
#define N 300500
int n,q,a,b,c;
int ch[N][2],fa[N],vl[N],su[N];
bool nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void pushup(int x){su[x]=vl[x]+su[ch[x][0]]+su[ch[x][1]];}
void rotate(int x)
{
	int f=fa[x],g=fa[f],tp=ch[f][1]==x;
	fa[x]=g;if(nroot(f))ch[g][ch[g][1]==f]=x;
	fa[ch[x][!tp]]=f;ch[f][tp]=ch[x][!tp];
	fa[f]=x;ch[x][!tp]=f;
	pushup(f);pushup(x);
}
void splay(int x)
{
	while(nroot(x))
	{
		int f=fa[x],g=fa[f];
		if(nroot(f))rotate((ch[g][1]==f)^(ch[f][1]==x)?x:f);
		rotate(x);
	}
}
void access(int x)
{
	int tp=0;
	while(x){splay(x);ch[x][1]=tp;pushup(x);tp=x;x=fa[x];}
}
void link(int x,int y)
{
	access(x);splay(x);fa[x]=y;
}
void cut(int x,int y)
{
	access(x);splay(x);fa[ch[x][0]]=0;ch[x][0]=0;pushup(x);
}
int query(int x,int v)
{
	v++;
	access(x);splay(x);
	int as=0,ls=0,lb=x;
	while(x)
	{
		ls=x;
		if(x<=v)lb=x,as+=su[ch[x][1]]+vl[x],x=ch[x][0];
		else x=ch[x][1];
	}
	if(vl[lb])as--;
	splay(ls);return as;
}
int rs[N];
set<int> fu;
void modify(int l,int r)
{
	r++;
	int tp=*fu.lower_bound(l);
	if(rs[tp]<=r)return;
	while(1)
	{
		set<int>::iterator it=fu.lower_bound(l);
		if(it==fu.begin())break;
		it--;
		int t1=*it;
		if(rs[t1]<r)break;
		cut(t1,rs[t1]);link(t1,t1+1);rs[t1]=0;
		access(t1);splay(t1);vl[t1]=0;pushup(t1);
		fu.erase(t1);
	}
	if(rs[l])cut(l,rs[l]),link(l,r),rs[l]=r;
	else cut(l,l+1),link(l,r),rs[l]=r,access(l),splay(l),vl[l]=1,pushup(l),fu.insert(l);
}
int main()
{
	scanf("%d%d",&q,&n);
	rs[n+1]=n+2;fu.insert(n+1);
	for(int i=1;i<=n;i++)fa[i]=i+1;
	while(q--)
	{
		scanf("%d%d%d",&a,&b,&c);
		if(a==1)modify(b,c);
		else printf("%d\n",query(b,c));
	}
}

R3T1 #9 Lovely Dogs

Problem

给出 $n,d$ ，以及一棵 $n$ 个点的有根树，树有点权 $v_i$ 。

定义函数 $f_d(x)$ ，设 $x$ 的质因数分解为 $p_1^{q_1}*...*p_k^{q_k}$ ，则：

$f_d(x)=\prod_{i=1}^k(-1)^{q_k}[q_k\leq d]$

对于每个点 $i$ ，求出：

as_i=\sum_{i,j\in subtree(u)}f_d(v_iv_j)

$n\leq 2\times 10^5,d\leq 20$ ， $v_i$ 构成一个 $1$ 到 $n$ 的排列。

$1s,256MB$

Sol

考虑算 $f_d(v_iv_j)$ ，如果只有乘积的第一部分，则记 $f(\prod p_i^{q_i})=\prod(-1)^{q_i}$ ，显然如果 $v_iv_j$ 有一个质因子次数大于 $p$ ，则 $f_d$ 为 $0$ ，否则为 $f(v_i)*f(v_j)$ 。

考虑有一些数 $v_i$ ，对于一个数 $v$ 计算 $\sum_if_d(v*v_i)$ 。考虑容斥，枚举次数大于 $p$ 的质因子集合。注意到如果一个数自身有一个质因子次数大于 $p$ ，则这个数乘上任何一个数的 $f_d$ 都是 $0$ ，可以在整个过程中不考虑这种数。对于剩下的数，它们不存在一个质因子次数大于 $p$ ，因此如果两个数乘积存在一个质因子次数大于 $p$ ，则两个数都是这个质因子的倍数。因此容斥时只需要枚举 $v$ 的质因子集合中的质因子。

设 $v=\prod_{i=1}^kp_i^{q_i}$ ，设枚举的集合为 $p_{a_1},...,p_{a_l}$ ，则满足和 $v$ 的乘积这些质因子次数都大于 $p$ 的数是所有是 $\prod_{i=1}^lp_{a_i}^{p-q_{a_i}+1}$ 的倍数的数。

因此，对于一个数 $v_i$ 的容斥可以看成一个二元组集合 $S_{v_i}=\{(d_i,r_i),...\}$ ，使得 $f_d(x*v_i)=f(x)*f(v_i)*(\sum[d_i|x]r_i)$ 。由于所有权值构成一个排列，而枚举质因子集合不超过枚举约数，因此元素个数不超过 $O(n\log n)$ 。

再考虑 $x$ 的约数集合 $D_x$ ，则 $d_i|x$ 相当于 $[d_i\in D_x]$ ，则上式相当于 $f(x)*f(v_i)*(\sum[d_i\in D_x]r_i)$ ，最后一部分等价于 $\sum_{d=1}^n\sum_{r\in\{-1,1\}}([(d,r)\in S_{v_i}][d\in D_x]r)$ 。

考虑设 $a_{d,v},b_{d,v}$ 。如果存在一个 $(d,r)\in S_v$ ，则 $a_{d,v}=r*f(v)$ ，否则 $a_{d,v}=0$ 。如果 $d\in D_v$ ，则 $b_{d,v}=f(v)$ ，否则 $b_{d,v}=0$ 。则可以发现 $f_d(xy)=\sum_{d=1}^na_{d,x}*b_{d,y}$ 。由之前的分析，所有值非零的位置只有 $O(n\log n)$ 个，可以考虑枚举每一个 $d$ ，计算这个 $d$ 的贡献。

在计算一个 $d$ 的贡献时，可以发现一个点的贡献为 $\sum_{i,j\in subtree(u)}a_{d,v_i}*b_{d,v_j}$ ，相当于将两部分分别求和再相乘。因此考虑对所有 $a_{d,v_i},b_{d,v_i}$ 至少一个非零的位置求虚树，则虚树上每一条边对于原树的链在这个 $d$ 时的贡献相同。在树上前缀和即可维护修改。

上述计算的过程实际上可以在求虚树的过程中直接完成，不需要求出虚树后再dfs一次。

如果直接建虚树，复杂度为 $O(n\log^2 n)$ 。但可以通过按照dfs序预处理 $a,b$ 去掉虚树时的排序，再ST表预处理LCA做到 $O(n\log n)$ ~~但是2log0.9s 1log0.6s~~

Code

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 200500
#define ll long long
int n,d,a,b,head[N],cnt,lb[N],tid[N],ct1,v[N],fg[N],st[N][18],lg[N],dep[N],f[N];
ll as[N],as2[N];
vector<pair<int,int> > qu[N];
struct edge{int t,next;}ed[N*2];
void adde(int f,int t){ed[++cnt]=(edge){t,head[f]};head[f]=cnt;ed[++cnt]=(edge){f,head[t]};head[t]=cnt;}
void dfs(int u,int fa)
{
	lb[u]=++ct1;dep[u]=dep[fa]+1;tid[ct1]=u;f[u]=fa;
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs(ed[i].t,u);
}
int s1[10][2],s2[10],ct;
void dfs1(int d,int vl,int tp)
{
	if(d==ct+1){qu[vl].push_back(make_pair(tp,1));return;}
	dfs1(d+1,vl,tp);
	if(1ll*vl*s2[d]<=n)dfs1(d+1,vl*s2[d],-tp);
}
void dfs2(int d,int vl,int tp)
{
	if(d==ct+1){qu[vl].push_back(make_pair(tp,0));return;}
	for(int i=0;i<=s1[d][1];i++)dfs2(d+1,vl,tp),vl*=s1[d][0];
}
void rmq_init()
{
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int i=1;i<n;i++)
	{
		int v1=tid[i],v2=tid[i+1];
		while(v1!=v2)if(dep[v1]>dep[v2])v1=f[v1];else v2=f[v2];
		st[i][0]=v1;
	}
	for(int j=1;j<18;j++)
	for(int i=1;i+(1<<j)-1<n;i++)
	{
		int v1=st[i][j-1],v2=st[i+(1<<j-1)][j-1];
		if(dep[v1]>dep[v2])v1=v2;
		st[i][j]=v1;
	}
}
int getlca(int x,int y)
{
	int v1=lb[x],v2=lb[y];
	if(v1>v2)swap(v1,v2);
	if(v1==v2)return x;else v2--;
	int l1=lg[v2-v1+1],s1=st[v1][l1],s2=st[v2-(1<<l1)+1][l1];
	return dep[s1]<=dep[s2]?s1:s2;
}
int is[N],v1[N],v2[N],t1[N],c1;
vector<int> sr;
void solve()
{
	if(!is[1])sr.push_back(1);
	t1[c1=1]=sr[0];
	for(int i=1;i<sr.size();i++)
	{
		int nw=sr[i];
		while(1)
		{
			int l=getlca(t1[c1],nw);
			if(dep[l]<=dep[t1[c1-1]])
			{
				int ls=t1[c1];
				v1[t1[c1-1]]+=v1[ls];
				v2[t1[c1-1]]+=v2[ls];
				as[ls]+=1ll*v1[ls]*v2[ls];
				as[t1[c1-1]]-=1ll*v1[ls]*v2[ls];
				v1[ls]=v2[ls]=0;
				c1--;
			}
			else if(dep[l]!=dep[t1[c1]])
			{
				int ls=t1[c1];
				t1[c1]=l;
				v1[t1[c1]]+=v1[ls];
				v2[t1[c1]]+=v2[ls];
				as[ls]+=1ll*v1[ls]*v2[ls];
				as[t1[c1]]-=1ll*v1[ls]*v2[ls];
				v1[ls]=v2[ls]=0;
			}
			else break;
		}
		t1[++c1]=nw;
	}
	while(c1)
	{
		int ls=t1[c1];
		v1[t1[c1-1]]+=v1[ls];
		v2[t1[c1-1]]+=v2[ls];
		as[ls]+=1ll*v1[ls]*v2[ls];
		as[t1[c1-1]]-=1ll*v1[ls]*v2[ls];
		v1[ls]=v2[ls]=0;
		c1--;
	}
}
void dfs3(int u,int fa)
{
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs3(ed[i].t,u),as[u]+=as[ed[i].t],as2[u]+=as2[ed[i].t];
}
int main()
{
	scanf("%d%d",&n,&d);
	for(int i=1;i<n;i++)scanf("%d%d",&a,&b),adde(a,b);
	dfs(1,0);
	for(int i=1;i<=n;i++)scanf("%d",&v[i]);
	for(int i=1;i<=n;i++)
	{
		int f1=1,f2=1;
		ct=0;
		int nw=v[tid[i]];
		for(int j=2;j*j<=nw;j++)if(nw%j==0)
		{
			s1[++ct][0]=j;s1[ct][1]=0;
			while(nw%j==0)s1[ct][1]++,nw/=j;
		}
		if(nw>1)s1[++ct][0]=nw,s1[ct][1]=1;
		for(int j=1;j<=ct;j++)
		{
			if(s1[j][1]*2>d)f2=0;
			if(s1[j][1]&1)f1*=-1;
			if(s1[j][1]>d)f1=0;
			else
			{
				int v1=1;
				for(int t=1;t<=d-s1[j][1]+1;t++)v1=1.0*v1*s1[j][0]>1e6?1e6:v1*s1[j][0];
				s2[j]=v1;
			}
		}
		as2[tid[i]]=f2;
		if(f1)
		{
			dfs1(1,1,tid[i]*f1);
			dfs2(1,1,tid[i]*f1);
		}
	}
	rmq_init();
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<sr.size();j++)is[sr[j]]=0;
		sr.clear();
		if(!is[1])is[1]=1,sr.push_back(1);
		for(int j=0;j<qu[i].size();j++)
		{
			int tp=qu[i][j].first;
			int vl=tp>0?1:-1,st=vl*tp;
			if(!is[st])is[st]=1,sr.push_back(st);
			if(qu[i][j].second)v2[st]+=vl;else v1[st]+=vl;
		}
		solve();
	}
	dfs3(1,0);
	for(int i=1;i<=n;i++)printf("%lld\n",(as[i]+as2[i])/2);
}

R3T2 #35 Alice、Bob 与 DFS

Problem

给一个 $n$ 个点 $m$ 条边的DAG，给出的点编号顺序为拓扑序，每个点出边有序。每个点是黑色或者白色。

现在有这样一段dfs：

定义过程 dfs(u)：
    if u 是白点
        按顺序遍历 u 的所有出边 (u,v)
            读取一个布尔值 g
            if g
                dfs(v)
    else
        按顺序遍历 u 的所有出边 (u,v) 
            dfs(v)

读取一个整数 r
dfs(r)

在每次执行dfs前，该程序会暂停。

有 $k$ 个程序，每个程序有不同的初始输入值 $r_i$ 。现在两人进行如下博弈：

两人轮流操作，每个人每次可以选择一个当前处于暂停状态的程序，让这个程序继续运行。在运行过程中，所有读取 $g$ 的操作的结果都由当前操作的人决定。当该程序再次暂停或者结束时，当前人的操作结束。如果轮到一个人选择时所有程序都结束了，则这个人输。

求最优操作下谁获胜。

$n\leq 2\times 10^5,m\leq 4\times 10^5,k\leq 2\times 10^5$

$2s,256MB$

Sol

DAG上dfs状态不会出现环，因此博弈的状态没有环，因此是一个无环的公平博弈，可以计算sg值。

考虑全是白点的情况，考虑计算从每个点 $i$ 开始dfs的sg值 $sg_i$ 。

考虑一个点的情况，假设已经算出了它所有出边的 $sg$ 值。从后往前考虑每个儿子，对于最后一个儿子，它内部的情况和从它开始的情况相同，因此可以直接使用之前的 $sg$ 。但对于中间的一个儿子，从这个儿子内部dfs结束后，还可以继续dfs之后的儿子。设之前求出的从这个点开始dfs，并且当前dfs到这个儿子的情况的 $sg$ 值为 $sg_1,...,sg_k$ ，则对于第 $i$ 个儿子，从内部dfs结束后，当前操作的人可以到达状态 $sg_{i+1},...,sg_k,0$ 。因此考虑 $dp_{i,S}$ 表示从 $i$ 开始dfs，结束dfs时可以选择 $sg$ 值属于集合 $S$ 的状态，这种游戏的 $sg$ 值。则初始的答案显然为 $sg_{i,\{0\}}$ 。暴力的复杂度为 $O(m2^n)$

对于全是白点的情况，可以发现所有的 $sg$ 操作是取mex，且在每个点上都可以直接选择全部 $g$ 取 $0$ 从而直接结束dfs，因此每个点的后继状态中都有 $S$ 。因此，此时的mex操作可以看成，在自然数中去掉所有 $S$ 中位置，然后在剩下的位置上做没有 $S$ 的mex操作。因此设 $dp_{i,\emptyset}=k$ ，则 $dp_{i,S}$ 即为自然数中第 $k+1$ 个没有在 $S$ 中出现的数。

因此，在计算一个点的 $dp_{i,\emptyset}$ 时，考虑继续使用上面的方式，则从后往前操作时每次会向 $S$ 中加入新求出的 $sg$ 。可以使用树状数组维护所有加入的 $sg$ ，查询时二分即可。

考虑计算了所有儿子的 $dp$ 后的情况，从当前点开始先手可以选择跳过前几个儿子到达某个儿子开始dfs，因此当前点的 $sg$ 即为所有后继状态的mex可以直接计算，复杂度为 $O(m\log^2 m)$ 或者 $O(m\log m)$ 。

接着考虑一般情况，对于一个有儿子的黑点，它开始只有一种状态，因此它的sg值只能是 $0$ 或 $1$ 。对于黑色的叶子，可以把它变成白色，不影响答案。如果只有黑色节点，那么可以直接dp，但将这个dp和白色点的dp结合时，白色点的 $sg$ 值会因为之后的 $sg$ 改变，但黑色点必须向儿子走，因此之后的 $sg$ 不会改变黑色点。

但注意到黑色点的 $sg$ 只会是 $0,1$ ，而白色部分的dp中一个 $sg$ 类似于让后面大于等于它的 $sg$ 值加一。因此考虑将状态中 $sg=0,1$ 的部分特殊处理，对于 $sg>1$ 的部分，因为它们不影响 $sg=0,1$ 的情况，此时之前的结论成立。

因此考虑 $dp_{i,0/1,0/1}$ 表示从 $i$ 开始，后继状态 $S$ 中是否出现 $0,1$ 时，这个状态的 $sg$ 值。进行上面的过程时， $\geq 2$ 的儿子sg使用白色dp部分的方式维护， $\leq 1$ 的部分暴力记录，在上面考虑第 $k+1$ 个没有在 $S$ 中出现的数时不考虑 $0,1$ ，最后两部分一起计算 $i$ 的 $sg$ 即可。

复杂度 $O(m\log^2 m)$ 或者 $O(m\log m)$ ，~~1log又一次只比2log快1/3~~

Code

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 400500
int n,c[N],a,b,ct[N],q,su,sm;
vector<int> nt[N];
int tr[N],dp[N][4];
void add(int x,int k){for(int i=x;i<=sm;i+=i&-i)tr[i]+=k;}
int que(int x){int as=0;for(int i=x;i;i-=i&-i)as+=tr[i];return as;}
int query1(int k)
{
	int as=0;
	for(int i=18;i>=0;i--)if(as+(1<<i)<=sm)
	{
		int nt=(1<<i)-tr[as+(1<<i)];
		if(nt<k)k-=nt,as+=1<<i;
	}
	return as;
}
void solve()
{
	for(int i=n;i>=1;i--)if(c[i])
	for(int t=0;t<4;t++)
	{
		int f1=t&1,f2=t>>1;
		vector<int> tp;
		for(int j=nt[i].size();j>=1;j--)
		{
			int v1=dp[nt[i][j-1]][f2*2+f1],as=query1(v1+1);
			if(as>1&&que(as+1)-que(as)==0)add(as+1,1),tp.push_back(as+1);
			if(as==1)f2=1;if(as==0)f1=1;
		}
		if(f1)add(1,1);if(f2)add(2,1);
		dp[i][t]=query1(1);
		for(int j=0;j<tp.size();j++)add(tp[j],-1);
		if(f1)add(1,-1);if(f2)add(2,-1);
	}
	else for(int t=0;t<4;t++)
	{
		int ls=t;
		for(int j=nt[i].size();j>=1;j--)
		{
			int v1=nt[i][j-1];
			ls=dp[v1][ls];
			if(ls>=2)ls=0;
			else if(ls==1)ls=2;
			else ls=1;
		}
		dp[i][t]=ls&1?(ls>>1)+1:0;
	}
	int as=0;
	scanf("%d",&q);
	while(q--)scanf("%d",&a),as^=dp[a][1];
	printf("%s\n",as?"Alice":"Bob");
}
int main()
{
	scanf("%d",&n);sm=2;
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		while(a--)scanf("%d",&b),nt[i].push_back(b),sm++;
	}
	solve();
}

R3T3 #37 音符大师

Problem

有一个数轴，在数轴上你有两个长度为 $L$ 的区间，初始两个区间左端点都在 $0$ 。

接下来有 $n$ 次操作，第 $i$ 次操作会给出一个位置 $x_i$ ，你需要移动这些区间使得这两个区间至少有一个包含 $x_i$ 。

求总移动距离的最小值。

$n\leq 5\times 10^4,L\leq 50,x_i\leq 10^9$

$3s,512MB$

Sol

对于 $L=0$ 的情况，第 $i$ 次操作后一定有一个区间在当前操作位置。设 $dp_{i,j}$ 表示当前处理了前 $i$ 个操作，另外一个区间在位置 $x_j$ 的最小移动距离。转移有两种：

移动在 $x_i$ 的区间，则相当于在原来的 $dp$ 上整体加。
移动在 $x_j$ 的区间，相当于求原 $dp$ 中的 $\min_j dp_{i,j}+|x_{i+1}-x_j|$ ，可以在线段树中维护 $dp_{i,j}-x_i,dp_{i,j}-x_j$ 的最小值，然后区间询问。这部分会转移到一个点。

对于 $L\geq 0$ 的情况，首先如果确定了需要哪个区间去接这个位置，则一定是让这个区间移动最少可能的长度，这是一种最优方案。

那么此时一个转移只有三种情况（到 $[x_j-L,x_j],[x_j,x_j+L]$ 或者不动）。考虑维护 $L+1$ 个线段树，表示当前第一个位置在 $x_i-L,...,x_i$ 的 $dp$ 。对于第一种转移，可以发现相当于将若干个线段树合并，并进行几次整体加。

对于第二种转移， $x_j\leq x_i-L$ 的部分都会转移到左侧， $x_j\geq x_i$ 的部分都会转移到右侧，这部分暴力做的复杂度为 $O(nL\log n)$ 。

对于中间的部分，可能的状态有 $O(L^2)$ 个。如果直接暴力拿出来转移，因为它们位置连续，复杂度为 $O(nL^2+nL\log n)$ ，但是会被卡常。此时有如下几种方式：

考虑求出一个状态后，将这个状态等到不移动区间无法包含的下一个操作再转移。这样就不会出现中间部分不移动的情况，且此时只会有 $x=x_i-L,x=x_i$ 两种情况，只需要两个线段树。此时第二部分只有 $O(1)$ 个状态，第一部分如果第一个区间不包含下一个位置，则可能在下一个位置不移动接住的只有 $O(L)$ 个位置，可以直接拿出来。否则，可以整个线段树向后转移到第一个区间接不住的位置，在那个地方再线段树合并。复杂度 $O(nL\log n)$
考虑拿出所有区间后，固定一维，只留下另外一维中有用的状态（不会被两侧的状态移动过来直接替代），可以扫一遍求出有用状态，然后直接加入。实际数据中保留的状态数是 $O(nL)$ 的，因此复杂度与上一个相同，但我不会证。
对于每个 $i$ ，只保留去掉会被替代的状态后，剩余状态中前 $L$ 优的状态，然后直接转移。复杂度 $O(nL\log L)$ ，完全不会证。

时空复杂度 $O(nL\log n)$ 。~~但是数据里面单个时刻状态数最多只有2e5~~

Code

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define N 100050
#define M 12005000
#define K 54
#define ll long long
int n,l,v[N],sr[N],ct,l1,r1,l2,r2,c1;
int rt[N],ch[M][2];
ll vl[M],s1[M],s2[M];
queue<int> f1;
int doit()
{
	if(f1.empty()){int v1=++c1;vl[v1]=1e18;return v1;}
	int v1=f1.front();f1.pop();
	vl[v1]=1e18;ch[v1][0]=ch[v1][1]=0;return v1;
}
int st[K],nw;
ll v1[K];
void doit1(int x,ll v){if(!x)return;s1[x]+=v;s2[x]+=v;vl[x]+=v;}
void pushdown(int x){doit1(ch[x][0],vl[x]);doit1(ch[x][1],vl[x]);vl[x]=0;}
void insert(int x,int l,int r)
{
	if(l==r)
	{
		vl[x]=min(vl[x],v1[nw]);
		s1[x]=vl[x]-sr[l];
		s2[x]=vl[x]+sr[l];
		nw++;
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if(st[nw]<=mid)
	{
		if(!ch[x][0])ch[x][0]=doit();
		insert(ch[x][0],l,mid);
	}
	if(st[nw]<=r)
	{
		if(!ch[x][1])ch[x][1]=doit();
		insert(ch[x][1],mid+1,r);
	}
	s1[x]=min(s1[ch[x][0]],s1[ch[x][1]]);
	s2[x]=min(s2[ch[x][0]],s2[ch[x][1]]);
}
int sid;
int su3=0;
ll tp1,tp2,fu[K][K];
vector<int> fu5[K];
void doit(int x,ll v)
{
	if(fu[sid][x-l2]>1e17)fu5[x-l2].push_back(sid);
	fu[sid][x-l2]=min(fu[sid][x-l2],v);
}
void query(int x,int l,int r)
{
	if(!x)return;
	if(r<l2){tp1=min(tp1,s1[x]);return;}
	if(l>r2){tp2=min(tp2,s2[x]);return;}
	if(l==r){doit(l,vl[x]);return;}
	int mid=(l+r)>>1;pushdown(x);
	query(ch[x][0],l,mid);query(ch[x][1],mid+1,r);
}
int merge(int x,int y,int l,int r)
{
	if(!x||!y)return x+y;
	if(l==r)
	{
		vl[x]=min(vl[x],vl[y]);
		s1[x]=vl[x]-sr[l];
		s2[x]=vl[x]+sr[l];
		f1.push(y);return x;
	}
	pushdown(x);pushdown(y);
	int mid=(l+r)>>1;
	ch[x][0]=merge(ch[x][0],ch[y][0],l,mid);
	ch[x][1]=merge(ch[x][1],ch[y][1],mid+1,r);
	s1[x]=min(s1[ch[x][0]],s1[ch[x][1]]);
	s2[x]=min(s2[ch[x][0]],s2[ch[x][1]]);
	f1.push(y);return x;
}
ll as=1e18;
void dfs(int x,int l,int r)
{
	if(!x)return;
	if(l==r){as=min(as,vl[x]);return;}
	pushdown(x);
	int mid=(l+r)>>1;
	dfs(ch[x][0],l,mid);dfs(ch[x][1],mid+1,r);
}
int fg1[K];
int main()
{
	s1[0]=s2[0]=1e18;
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++)scanf("%d",&v[i]);
	sr[ct=1]=0;
	for(int i=1;i<=n;i++)
	{
		sr[++ct]=v[i];
		if(v[i]-l>=0)sr[++ct]=v[i]-l;
	}
	sort(sr+1,sr+ct+1);
	int c2=0;
	for(int i=1;i<=ct;i++)if(i==1||sr[i]!=sr[i-1])sr[++c2]=sr[i];
	ct=c2;
	l1=r1=1;
	st[nw=1]=1;st[2]=1e9;
	rt[1]=doit();insert(rt[1],1,ct);
	for(int i=1;i<=n;i++)
	{
		l2=lower_bound(sr+1,sr+ct+1,v[i]-l)-sr;
		r2=lower_bound(sr+1,sr+ct+1,v[i])-sr;
		for(int j=0;j<=r1-l1;j++)
		for(int k=0;k<=r2-l2;k++)fu[j][k]=1e18;
		for(int j=l1;j<=r1;j++)
		{
			sid=j-l1;
			tp1=tp2=1e18;
			query(rt[j],1,ct);
			fu[sid][0]=min(fu[sid][0],tp1+sr[l2]);
			fu[sid][r2-l2]=min(fu[sid][r2-l2],tp2-sr[r2]);
		}
		for(int j=l1;j<=r1;j++)
		{
			if(j<l2)doit1(rt[j],sr[l2]-sr[j]),rt[l2]=merge(rt[l2],rt[j],1,ct),rt[j]=0;
			if(j>r2)doit1(rt[j],sr[j]-sr[r2]),rt[r2]=merge(rt[r2],rt[j],1,ct),rt[j]=0;
		}
		for(int j=l2;j<=r2;j++)
		{
			nw=0;
			if(j>l2&&j<r2)for(int k=0;k<fu5[j-l2].size();k++)st[++nw]=fu5[j-l2][k];
			else for(int k=l1;k<=r1;k++)if(fu[k-l1][j-l2]<1e17)st[++nw]=k-l1;
			for(int k=1;k<=nw;k++)v1[k]=fu[st[k]][j-l2],st[k]+=l1;
			fu5[j-l2].clear();
			for(int k=1;k<=nw;k++)fg1[k]=1;
			ll mx=1e18;
			for(int k=1;k<nw;k++)
			{
				if(v1[k]>=mx)fg1[k]=0;else mx=v1[k];
				mx+=sr[st[k+1]]-sr[st[k]];
			}
			mx=1e18;
			for(int k=nw;k>1;k--)
			{
				if(v1[k]>=mx)fg1[k]=0;else mx=v1[k];
				mx+=sr[st[k]]-sr[st[k-1]];
			}
			int c2=0;
			for(int k=1;k<=nw;k++)if(fg1[k])st[++c2]=st[k],v1[c2]=v1[k];
			nw=c2;
			st[nw+1]=1e9;nw=1;
			if(!rt[j])rt[j]=doit();
			insert(rt[j],1,ct);
		}
		l1=l2;r1=r2;
	}
	for(int i=l1;i<=r1;i++)dfs(rt[i],1,ct);
	printf("%lld\n",as);
}

R4T2 #31 机器(machine)

Problem

给一个 $n$ 个点 $m$ 条边的有向图，每个点有点权 $h_i$ 。

对于第 $i$ 个点，有 $p_i$ 条管道向点 $i$ 放入物品，第 $j$ 条管道的费用为 $a_{i,j}$ 。有 $q_i$ 条管道从点 $i$ 拿出物品，第 $j$ 条管道的费用为 $b_{i,j}$ 。

你可以从某条管道放入一个物品，然后在图中让物品沿着边运动，最后从某条管道离开。设进入时在点 $s$ ，离开时在点 $t$ ，则这样的受益为 $h_s-h_t$ 再减去两条管道的费用和。

上述操作可以进行任意次，但每条管道只能用一次，每条边可以用任意次。求出最大收益。

$n\leq 2000,m\leq 2\times 10^4,p_i,q_i\leq 2000,h_i\leq 10^8,a_{i,j},b_{i,j}\leq 10^6$ ，权值随机。

$3s,1024MB$

Sol

问题显然可以看成一个最大费用流，但直接流显然过不去。

考虑最大费用循环流的对偶：

一个最大费用循环流相当于如下线性规划：给每条边一个流量 $f_i$ ，最大化 $\sum f_ic_i$ 且满足：

每个点的入流量和出流量相等
每条边的流量不超过上界

考虑对偶，设每个点限制对偶后变量为 $p_i$ ，边对应变量为 $e_i$ 。则 $p_i$ 没有 $\geq 0$ 的限制。

考虑原先一条边 $(s_i,t_i,v_i)$ 的变量对偶后对应的限制， $f_i$ 只出现在现在的 $p_{s_i},p_{t_i},e_i$ 的方程中，可以发现此时的限制为：

-p_{s_i}+e_i+p_{t_i}\geq c_i

而最小化的权值为 $\sum e_iv_i$ 。因为 $v_i\geq 0$ ，因此 $e_i$ 一定越小越好，因此 $e_i$ 一定取 $\max(0,p_{s_i}-p_{t_i}+c_i)$ 。因此相当于选择一种 $p$ ，最小化如下值：

\sum_i v_i*\max(0,p_{s_i}-p_{t_i}+c_i)

回到原问题，对于流量 $\infty$ ，费用 $0$ 的边 $s_i\to t_i$ ，相当于要求 $p_{s_i}\leq p_{t_i}$ 。此时相当于如下问题：

对图中每个点指定权值 $p_i$ ，以及原点权值 $p_s$ ，汇点权值 $p_t$ ，要求：

对于图中一条边 $s_i,t_i$ ，要求 $p_{s_i}\leq p_{t_i}$ ，且 $p_t\leq p_s$ 。

最小化 $\sum_{i=1}^n\sum_{j=1}^{p_i}\max(0,p_s-p_i+a_{i,j})+\sum_{i=1}^n\sum_{j=1}^{q_i}\max(0,p_i-p_t+b_{i,j})$ 。

显然 $p_t=p_s$ 最优，因此可以设 $p_s=p_t=0$ ，相当于最小化 $\sum_{i=1}^n\sum_{j=1}^{p_i}\max(0,-p_i+a_{i,j})+\sum_{j=1}^{q_i}\max(0,p_i+b_{i,j})$ 。

那么对于一个点，这个点带来的代价关于这个点的取值是一个分段上凸函数，每一段都是线性函数。

可以发现 $L_1$ 的保序回归是这个的特例， $L_1$ 保序回归中的函数为 $|x-x_i|$ 。可以说明这个问题满足整数上保序回归问题的结论：

对于任意权值 $k$ ，考虑所有 $p_i$ 只能取 $k,k+1$ 的问题，对于任意点 $x$ ，如果存在一个该问题的最优解使得 $p_x=k$ ，则存在一个最优解使得 $p_x\leq k$ ，如果存在一个该问题的最优解使得 $p_x=k+1$ ，则存在一个最优解使得 $p_x\geq k+1$ 。

使用原来的证明方式即可证明，但~~因为我没看过原证明~~所以咕了。

因此整体二分，每次的问题相当于求一个最大权闭合子图，网络流即可。

复杂度 $O(n*\log v*(dinic(n,m)+n\log k))$ ，数据随机所以可以接受。

Code

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define N 2050
#define M 40050
#define ll long long
int n,m,a,b,s[M][2],v[N],as[N],h[N];
vector<ll> s1[N],s2[N],su1[N],su2[N];
ll query(int x,int v)
{
	ll as=0;
	int v1=lower_bound(s1[x].begin(),s1[x].end(),v)-s1[x].begin();
	if(v1!=s1[x].size())as+=su1[x][v1]-1ll*v*(s1[x].size()-v1);
	int v2=lower_bound(s2[x].begin(),s2[x].end(),-v)-s2[x].begin();
	if(v2!=s2[x].size())as+=su2[x][v2]+1ll*v*(s2[x].size()-v2);
	return as;
}
int head[N],cnt,cur[N],dep[N],vis[N],is[N];
struct edge{int t,next,v;}ed[M*3];
void adde(int f,int t,int v)
{
	ed[++cnt]=(edge){t,head[f],v};head[f]=cnt;
	ed[++cnt]=(edge){f,head[t],0};head[t]=cnt;
}
bool bfs(int s,int t)
{
	for(int i=1;i<=n+2;i++)cur[i]=head[i],dep[i]=-1;
	queue<int> qu;qu.push(s);dep[s]=0;
	while(!qu.empty())
	{
		int u=qu.front();qu.pop();
		for(int i=head[u];i;i=ed[i].next)if(ed[i].v&&dep[ed[i].t]==-1)
		dep[ed[i].t]=dep[u]+1,qu.push(ed[i].t);
		if(dep[t]!=-1)return 1;
	}
	return 0;
}
int dfs(int u,int t,int f)
{
	if(u==t||!f)return f;
	int as=0,tp;
	for(int &i=cur[u];i;i=ed[i].next)if(ed[i].v&&dep[ed[i].t]==dep[u]+1&&(tp=dfs(ed[i].t,t,min(ed[i].v,f))))
	{
		ed[i].v-=tp;ed[i^1].v+=tp;
		as+=tp;f-=tp;
		if(!f)return as;
	}
	return as;
}
void dfs1(int u)
{
	vis[u]=1;
	for(int i=head[u];i;i=ed[i].next)if(!vis[ed[i].t]&&ed[i].v)dfs1(ed[i].t);
}
void solve(int l,int r,vector<int> tp)
{
	if(l==r||!tp.size())return;
	for(int i=0;i<tp.size();i++)is[tp[i]]=1;
	for(int i=1;i<=n+2;i++)head[i]=0;cnt=1;
	for(int i=1;i<=m;i++)adde(s[i][1],s[i][0],1e9);
	int mid=(l+r)>>1;
	for(int i=1;i<=n;i++)if(!is[i])
	{
		if(as[i]<=l)adde(n+1,i,1e9);
		else adde(i,n+2,1e9);
	}
	else
	{
		int tp=query(i,mid)-query(i,mid+1);
		if(tp>0)adde(i,n+2,tp);
		else adde(n+1,i,-tp);
	}
	for(int i=1;i<=n+2;i++)vis[i]=0;
	while(bfs(n+1,n+2))dfs(n+1,n+2,1e9);
	dfs1(n+1);
	vector<int> s1,s2;
	for(int i=1;i<=n;i++)if(is[i])
	{
		is[i]=0;
		if(vis[i])as[i]=mid,s1.push_back(i);
		else as[i]=mid+1,s2.push_back(i);
	}
	solve(l,mid,s1);
	solve(mid+1,r,s2);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]);
	for(int i=1;i<=m;i++)scanf("%d%d",&s[i][0],&s[i][1]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		while(a--)scanf("%d",&b),s1[i].push_back(h[i]-b);
		sort(s1[i].begin(),s1[i].end());su1[i]=s1[i];
		for(int j=su1[i].size();j>1;j--)su1[i][j-2]+=su1[i][j-1];
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		while(a--)scanf("%d",&b),s2[i].push_back(-h[i]-b);
		sort(s2[i].begin(),s2[i].end());su2[i]=s2[i];
		for(int j=su2[i].size();j>1;j--)su2[i][j-2]+=su2[i][j-1];
	}
	vector<int> fu;for(int i=1;i<=n;i++)fu.push_back(i);
	solve(-1.02e8,1.02e8,fu);
	ll as1=0;
	for(int i=1;i<=n;i++)as1+=query(i,as[i]);
	printf("%lld\n",as1);
}

R4T3 #48 数列重排

Problem

有 $n$ 个 $[0,m-1]$ 间的整数，定义 $f_k$ 为将这些正整数任意排列，得到的序列中 $mex$ 大于等于 $k$ 的子区间个数的最大值。

给出 $l,r$ ，求出 $f_l,...,f_r$ ，输出 $\oplus_{i=l}^r(f_i*233^i\bmod 998244353)$ 。

给出一个正整数 $x$ ，保证 $[0,m-1]$ 间的每种整数出现 $x$ 次或者 $x+1$ 次。输入一个长度为 $m$ 的01串，每一位表示对应的这种数字是否出现了 $x+1$ 次。

$n\leq 10^9,m\leq 10^7,0\leq l\leq r\leq m$

$0.6s,256MB$

Sol

考虑 $k=m$ 的情况，相当于让每种数都出现的子区间数量最多。直接的想法是让每个长度为 $m$ 的区间都满足要求，这可以通过如下方式实现：

设所有出现次数为 $x+1$ 的数为 $a_1,...,a_l$ ，剩下的数为 $b_1,...,b_r$ ，构造序列 $a,b,a,b,...,b,a$ 。

因此答案为 $\sum_{i=m}^n(n-i+1)$ ，可以 $O(1)$ 计算。

考虑任意一个 $k$ ，对于小于 $k$ 的数，显然它们按照上面的方式排列最优。只需要考虑将剩下的数加入的情况。

设小于 $k$ 的数有 $l$ 个，则最后的方案可以看成在这个序列中间插入数，设在第 $i$ 个数后面插入了 $c_i$ 个数。

注意到一个区间的mex大于等于 $k$ 当且仅当它包含了大于等于 $k$ 个原来的数，因此可以使用如下方式计算此时不合法的区间数：

两端都是原先的数，这部分数量是定值。
有一端是原先的数，这部分的数量为 $\sum_{i=0}^lc_i(\min(k-1,\min(i,l-i))+k-1)$
两端都不是原先的数，这部分的数量为 $\sum_{0<j-i<m}c_ic_j+\sum_{i=0}^m\frac{c_i(c_i+1)}2$

可以发现，在 $c_0,...,c_{m-1}$ 中的位置都会互相贡献，将它们全部移动到 $c_0$ 一定更优。 $c_{l-m+1},...,c_l$ 中类似。

对于中间的部分，此时第二部分数量也为定值，只需要考虑第三部分。将这些 $c_i$ 划分成 $k$ 个一段，则每一段内部一定会互相贡献，可以发现如果将每一段的都放在开头，则段之间不会互相贡献，这样最优。因此存在一种最优方案，使得只有 $c_0,c_l,c_{ik}(l-ik\geq k)$ 有值。

设 $s=\lfloor\frac{l-k}k\rfloor$ ，则可以看成选定 $d_0,...,d_{s+1}$ ，使得 $\sum d_i$ 等于某个定值，并最小化如下值：

\sum_{i=0}^{s+1}\frac{d_s(d_s+1)}2+d_s*(k+k*[i\in[1,s]])

如果看成一个一个加入数，则相当于对于中间的位置，第一次加入一个数的代价为 $2k-1$ ，之后每一次加入代价加一。对于两侧的位置，第一次加入的代价为 $k$ ，之后也是每一次代价加一。

那么一定会每次选择代价最小的一个加入，因此是先向两侧各加 $k-1$ 次，然后均匀地加。这可以 $O(1)$ 计算。

需要注意的是，如果前 $k$ 种数中有一种出现次数是 $x$ ，那么就有 $s=x$ ，但如果都是 $x+1$ 次，则 $s=x+1$

复杂度 $O(m)$

Code

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 10050000
#define mod 998244353
#define ll long long
int n,m,l,r,k,vl=1,as,s1,s2;
char s[N];
int main()
{
	scanf("%d%d%d%d%s",&m,&l,&r,&k,s);
	for(int i=0;i<m;i++)n+=k+s[i]-'0';
	s2=n;
	for(int i=0;i<=m;i++)
	{
		ll vl1=1ll*n*(n+1)/2;
		if(i)
		{
			s1+=k+s[i-1]-'0';
			s2-=k+s[i-1]-'0';
			ll tp=1ll*i*(i-1)/2+1ll*(s1-i+1)*(i-1);
			int v1=i,v2=2*i-1;
			int f1=min(s2,(v2-v1)*2),f2=f1>>1;
			tp+=1ll*(v1*2+f2-1)*f2/2;f2=f1-f2;
			tp+=1ll*(v1*2+f2-1)*f2/2;
			ll nt=s2-f1,fg=k+1;
			if(s1==i*(k+1))
			fg++;
			ll fu1=nt/fg,fu2=nt-fu1*fg;
			tp+=fu2*(v2*2+fu1)*(fu1+1)/2;
			tp+=(fg-fu2)*(v2*2+fu1-1)*fu1/2;
			vl1-=tp;
		}
		if(i>=l&&i<=r)as^=vl1%mod*vl%mod;
		vl=233ll*vl%mod;
	}
	printf("%d\n",as);
}

R5T1 #14 Speike & Tom

Problem

有一棵 $n$ 个点的树，现在加入了 $m$ 条额外边。

两个人在树上进行博弈，两人轮流行动，每个人每次可以选择沿着一条边移动到相邻点，或者不移动。第一个人可以走两种边，第二个人只能走树边。

当两个人位置重合时，游戏结束，第二个人获胜。

求在 $n^2$ 种初始位置中，有多少种初始位置使得第一个人能让第二个人永远无法获胜。

$n,m\leq 10^5$

$2s,512MB$

Sol

两个人初始位置相同则第二个人直接获胜，可以不考虑这种情况。然后可以考虑计算总情况减去第二个人获胜的情况。

分析原博弈问题，可以得到如下性质：

如果存在一条非树边使得两个端点在树上距离大于 $2$ ，则只要第一个人运动到了两个端点在树上的路径中且第二个人下一步不能获胜，则第二个人永远无法获胜。

这条非树边构成了一个环。如果第二个人当前不在环上，则第二个人会从某个确定的点回到环上，因此第一个人可以选择一个远离这个点的位置。

否则，第一个人可以在环上沿着远离第二个人的方向走，因为环长大于等于 $4$ ，且在环上第二个人只能沿着环走，因此只要第一个人保持 $2$ 的距离，第二个人就不可能获胜。

如果不存在这样的非树边，则第二个人必胜。

以第二个人初始位置为根，考虑第二个人在树上向第一个人接近。初始时，第一个人在第二个人位置的子树内。因为非树边两个端点在树上距离不超过 $2$ ，如果第一个人想离开这个子树，则他只能向上跳，第一个人只能跳到第二个人的父亲，但这样必败，因此第一个人不能离开第二个人的子树，因此第二个人必胜。

称一个点是关键点，当且仅当存在一条非树边，使得两个端点在树上的距离大于 $2$ 且端点间的路径包含这个点。则只要第一个人走到了一个关键点且第二个人下一步不能追上他，第二个人就不能获胜。

以第一个人的位置为根考虑原树，如果有至少两个根的儿子内有关键点，则第二个人不能获胜。

第一个人只需要选择第二个人不在的子树向那个子树内的关键点走，第二个人就无法追上。

则可以找到包含所有关键点的最小连通块，如果第一个人初始在这个连通块内，则第二个人不能获胜。接下来只需要考虑剩下的情况。剩下的情况一定可以看成若干个子树，可以对于每一个子树分别考虑第一个人在这个子树内的情况。

此时可以分成两种情况：

第二个人在子树内

因为子树内没有关键点，因此如果第二个人走到了第一个人的祖先他就能获胜，且只有这样能获胜。因此第二个人会选择每次往子树的根走。因此，第一个人也会选择每次尽量往上走，即如果有连向父亲的父亲的额外边就走，否则往父亲走。

考虑在两个人在原树上的LCA，在LCA后两个人走的是同一条链，但第一个人可以走额外边，因此第二个人在之后不可能再追上第一个人，因此第二个人必须在LCA处追上第一个人。即第二个人到达LCA时，第一个人还在LCA子树内。

再考虑第一个人走的情况，可以发现第一个人走的方式也形成了一棵树，考虑这棵树上的一个点 $u$ 以及父亲 $f$ ，在这条边处合并的信息有两种情况：

在原树中LCA为 $f$ ，第一个人来自子树 $u$ ，第二个人来自其他子树，此时相当于要求第一个人在新的树上与 $f$ 的距离不小于第二个人在原树上与 $f$ 的距离。
原树中LCA为 $u$ 到 $f$ 跳过的点，这种情况与上一种类似。

两种情况可以合并为，考虑所有第一个人在 $u$ 子树内，第二个人在 $f$ 子树内但不在 $u$ 子树内的情况，统计有多少种情况第一个人在新的树上与 $f$ 的距离不小于第二个人在原树上与 $f$ 的距离

考虑在第一棵树中长链剖分合并每个点子树中所有点到它的距离，然后枚举第一个人的距离，则相当于询问 $f$ 子树内距离 $f$ 不超过某个值的点数，减去子树内被重复计算的一个类似的部分。考虑从小到大询问距离，如果当前的结果已经是所有点，则之后的询问可以跳过。这样合并的询问次数为两侧深度的最小值。根据长链剖分这样的复杂度为 $O(n)$ 。

询问 $f$ 子树内的情况可以通过另外一个简单实现。复杂度 $O(n\log n)$

第二个人在子树外

第一个人选择与之前相同的策略更优，此时有两种情况：

第一个人会跳过子树的根到达一个好的点。

如果到达的点是关键点，则因为关键点是一个环，因此至少有两个方向可以走。否则，这个点也至少有两个方向的子树中有关键点。因此如果此时第二个人没有到达这个点，则之后不可能再获胜。因此相当于询问有多少种情况满足第一个人在子树内，第二个人在子树外，第二个人到达子树父亲的根的时间不晚于第一个人。可以枚举第一个人的距离（使用之前长链剖分的结果），然后相当于询问子树外有多少个点到达这个点的距离小于某个值。因为整体的根在外部，可以使用点分治算出整体的答案，再容斥减去子树内的（使用上面求的结果）。

第一个人会到达子树的根。

此时第一个人可以向父亲走，也可以走额外边到达另外一个与父亲相邻的好点。

如果有两条或者更多的额外边，则无论第二个人在哪个方向，第一个人都可以选择另外一个方向。此时第二个人能获胜当且仅当在第一个人到达子树根的这一轮，第二个人可以到达子树根的父亲，这是一个和上面类似的问题。

如果没有额外边，则只需要第一个人到达子树根的这一轮，第二个人可以走到一个距离子树根不超过 $1$ 的点，就可以获胜。

如果只有一条额外边，则如果第二个人不在这条额外边的方向上，则是上面第二种情况。否则是上面的第一种情况。

三种情况的询问都相当于给定一条边，求这条边某个方向的子树内，距离这条边上的某个点不超过某个点的点数。包括第一大类情况中询问 $f$ 子树以及上一小类中的询问。且总询问次数为 $O(n)$ 。这可以容斥拆成两部分：

距离某个点不超过某个值的点数。
在固定根的情况下，某个子树内距离根不超过某个值的点数。

1可以使用点分治实现，2可以使用长链剖分或者dfs序+主席树实现。这样的复杂度可以做到 $O(n\log n)$ 。

事实上长链剖分的合并也可以使用一个点分治来解决，但这样点分治的细节比长链剖分更加复杂。

一种长链剖分的实现方式：

使用vector，按照深度从大到小维护每个深度的信息。合并时继承子树内深度最大的儿子的vector，剩下的可以直接合并过来。最后只需要将当前点的信息加入到vector的最后即可。

Code

~~这里写的是2log但是和1log跑的差不多~~

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 100500
#define M 4005000
#define ll long long
int n,m,a,b,c,head[N],cnt;
struct edge{int t,next,id;}ed[N*4];
void adde(int f,int t,int id)
{
	ed[++cnt]=(edge){t,head[f],id};head[f]=cnt;
	ed[++cnt]=(edge){f,head[t],id};head[t]=cnt;
}
//pretree
int dep[N],lb[N],rb[N],ct1,sr1[N],f[N];
void dfs0(int u,int fa)
{
	dep[u]=dep[fa]+1;lb[u]=++ct1;sr1[ct1]=dep[u];f[u]=fa;
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs0(ed[i].t,u);
	rb[u]=ct1;
}
struct pretree{
	int rt[N],vl[M],ch[M][2],ct,c1;
	int modify(int x,int l,int r,int v)
	{
		int st=++ct;
		ch[st][0]=ch[x][0];ch[st][1]=ch[x][1];vl[st]=vl[x]+1;
		if(l==r)return st;
		int mid=(l+r)>>1;
		if(mid>=v)ch[st][0]=modify(ch[x][0],l,mid,v);
		else ch[st][1]=modify(ch[x][1],mid+1,r,v);
		return st;
	}
	void ins(int x){rt[c1+1]=modify(rt[c1],1,n,x);c1++;}
	int query(int x,int l,int r,int s)
	{
		if(!x)return 0;
		if(l>s)return 0;
		if(r<=s)return vl[x];
		int mid=(l+r)>>1;
		return query(ch[x][0],l,mid,s)+query(ch[x][1],mid+1,r,s);
	}
}pt;
void init_pret()
{
	dfs0(1,0);
	for(int i=1;i<=n;i++)pt.ins(sr1[i]);
}
int que1(int x,int d)
{
	return pt.query(pt.rt[rb[x]],1,n,d)-pt.query(pt.rt[lb[x]-1],1,n,d);
}
//centroid
int sz[N],tp1,tp2,as1,f1[N],de[N],de1[N],ds[N][22],fr[N][22],vis[N];
vector<int> v1[N],v2[N];
vector<int> fu;
void dfs1(int u,int fa)
{
	sz[u]=1;de1[u]=de1[fa]+1;fu.push_back(u);
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa&&!vis[ed[i].t])dfs1(ed[i].t,u),sz[u]+=sz[ed[i].t];
}
void dfs2(int u,int fa)
{
	sz[u]=1;
	int mx=0;
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa&&!vis[ed[i].t])
	{
		dfs2(ed[i].t,u);
		sz[u]+=sz[ed[i].t];
		if(mx<sz[ed[i].t])mx+=sz[ed[i].t];
	}
	if(mx<tp1-sz[u])mx=tp1-sz[u];
	if(tp2>mx)tp2=mx,as1=u;
}
void dfs3(int u)
{
	vis[u]=1;de1[u]=0;v1[u].push_back(0);
	for(int i=head[u];i;i=ed[i].next)if(!vis[ed[i].t])
	{
		dfs1(ed[i].t,u);
		tp1=sz[ed[i].t];tp2=1e7;
		dfs2(ed[i].t,u);
		for(int j=0;j<fu.size();j++)
		{
			int nt=fu[j];
			ds[nt][de[u]]=de1[nt];
			fr[nt][de[u]]=as1;
			v2[as1].push_back(de1[nt]);
			v1[u].push_back(de1[nt]);
		}
		fu.clear();
	}
	for(int i=head[u];i;i=ed[i].next)if(!vis[ed[i].t])
	{
		tp1=sz[ed[i].t];tp2=1e7;
		dfs2(ed[i].t,u);
		de[as1]=de[u]+1;f1[as1]=u;
		dfs3(as1);
	}
}
void init_cent()
{
	de[1]=1;dfs3(1);
	for(int i=1;i<=n;i++)sort(v1[i].begin(),v1[i].end());
	for(int i=1;i<=n;i++)sort(v2[i].begin(),v2[i].end());
}
int que2(int x,int c)
{
	int as=0,nw=x;
	while(nw)
	{
		int d=de[nw];
		as+=upper_bound(v1[nw].begin(),v1[nw].end(),c-ds[x][d])-v1[nw].begin();
		int f2=fr[x][d];
		if(f2)as-=upper_bound(v2[f2].begin(),v2[f2].end(),c-ds[x][d])-v2[f2].begin();
		nw=f1[nw];
	}
	return as;
}
int query(int x,int y,int d)
{
	if(dep[y]>dep[x])return que1(y,dep[x]+d);
	else return que2(x,d)-que1(x,dep[x]+d);
}
int is[N],su[N],su1;
void dfs4(int u,int fa)
{
	su[u]=is[u];
	int fg=0;
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa&&!ed[i].id)
	{
		dfs4(ed[i].t,u);su[u]+=su[ed[i].t];
		if(su[ed[i].t])fg++;
	}
	if(su[u]<su1)fg++;
	if(fg>=2)is[u]=1;
}
int d2[N],f2[N];
vector<int> t1;
void dfs5(int u,int fa)
{
	d2[u]=d2[fa]+1;t1.push_back(u);f2[u]=fa;
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa&&ed[i].id==0)dfs5(ed[i].t,u);
}
ll as;
vector<int> sn[N];
int d3[N],mxd[N];
void dfs6(int x)
{
	mxd[x]=d3[x];
	for(int i=0;i<sn[x].size();i++)d3[sn[x][i]]=d3[x]+1,dfs6(sn[x][i]),mxd[x]=max(mxd[x],mxd[sn[x][i]]);
}
int id1[N],sz1[N];
vector<int> fuc[N];
int merge(int x,int y)
{
	if(mxd[x]<mxd[y])swap(x,y);
	for(int i=0;i<fuc[y].size();i++)fuc[x][i+mxd[x]-mxd[y]]+=fuc[y][i];
	return x;
}
int calc(int x,int y,int d)
{
	int as=0;
	if(!f2[x])as=que2(x,d);else as=query(f2[x],x,d+1);
	if(f2[y]!=x)d--;
	as-=query(f2[y],y,d);
	return as;
}
void dfs7(int x)
{
	id1[x]=0;sz1[x]=1;
	for(int i=0;i<sn[x].size();i++)
	{
		dfs7(sn[x][i]);sz1[x]+=sz1[sn[x][i]];
		int mx=calc(x,sn[x][i],n+1),ls=sz1[sn[x][i]];
		for(int j=fuc[id1[sn[x][i]]].size()-1;j>=0;j--)
		{
			int vl=fuc[id1[sn[x][i]]][j],ds=fuc[id1[sn[x][i]]].size()-j;
			ls-=vl;
			int nt=calc(x,sn[x][i],ds);
			as+=1ll*vl*nt;
			if(nt==mx)break;
		}
		as+=1ll*ls*mx;
		if(!id1[x])id1[x]=id1[sn[x][i]];
		else id1[x]=merge(id1[x],id1[sn[x][i]]);
	}
	if(!id1[x])id1[x]=x,fuc[x].clear();
	fuc[id1[x]].push_back(1);
}
void doit(int x,int y)
{
	t1.clear();sn[x].clear();
	d2[x]=0;dfs5(y,x);f2[x]=0;
	for(int i=0;i<t1.size();i++)if(t1[i]!=y)
	{
		int u=t1[i],fg=0;
		for(int j=head[u];j;j=ed[j].next)if(ed[j].t==f2[f2[u]])fg=1;
		if(fg)sn[f2[f2[u]]].push_back(u);
		else sn[f2[u]].push_back(u);
	}
	d3[x]=0;dfs6(x);dfs7(x);
	d3[y]=0;dfs6(y);dfs7(y);
	int fg=0;
	for(int i=head[y];i;i=ed[i].next)if(is[ed[i].t]&&ed[i].t!=x)
	if(!fg)fg=ed[i].t;else if(fg!=ed[i].t)fg=-1;
	for(int i=0;i<fuc[id1[y]].size();i++)
	{
		int vl=fuc[id1[y]][i],ds=fuc[id1[y]].size()-i;
		if(fg)ds--;
		int t1=query(y,x,ds+1);
		if(fg&&fg!=-1)
		{
			t1-=query(x,fg,ds);
			t1+=query(x,fg,ds+1);
		}
		as+=1ll*vl*t1;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)scanf("%d%d",&a,&b),adde(a,b,0);
	init_pret();init_cent();
	while(m--)
	{
		scanf("%d%d",&a,&b);
		if(f[a]==b||f[b]==a)continue;
		if(f[f[a]]==b||f[f[b]]==a||f[a]==f[b])adde(a,b,1);
		else is[a]=is[b]=1;
	}
	for(int i=1;i<=n;i++)if(is[i])su1++;
	if(!su1){printf("0\n");return 0;}
	dfs4(1,0);
	for(int i=1;i<=n;i++)if(is[i])
	for(int j=head[i];j;j=ed[j].next)if(!is[ed[j].t]&&!ed[j].id)doit(i,ed[j].t);
	printf("%lld\n",1ll*n*(n-1)-as);
}

4182_543_731`s blog