[[https://ac.nowcoder.com/acm/contest/11254|比赛链接]]

====== 补题情况 =====

^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
|  A  |  2  |  1  |  0  | 
|  B  |  1  |  2  |  2  | 
|  C  |  1  |  1  |  2  | 
|  D  |  2  |  0  |  0  | 
|  E  |  2  |  0  |  2  | 
|  F  |  2  |  0  |  1  | 
|  G  |  2  |  1  |  0  | 
|  H  |  0  |  0  |  0  | 
|  I  |  2  |  0  |  1  | 
|  J  |  2  |  0  |  1  | 

====== 题解 ======

===== A. Guess and lies =====

==== 题意 ====

一开始有一个数 $x\in [1,n]$，只有 $A$ 知道，$B$ 不知道。

$B$ 每次可以给定一个 $y$，询问 $y\le x$ 是否成立。$A$ 至多可以说一次谎，$A$ 想要最大化询问次数，$B$ 想要最小化询问次数。

假定 $B$ 第一次问的数为 $i$ 且 $A$ 回答 $i\le x$ 成立，问还需要询问多少次。

==== 题解 ====

假定 $B$ 询问的数为 $y$，如果 $A$ 回答 $i\le x$ 成立，则将 $[1,y)$ 的说谎次数 $+1$，否则将 $[y,n]$ 的说谎次数 $+1$。

易知最后只剩下一个说谎次数不超过 $1$ 的数就是答案。于是 $B$ 相当于每个把 $[1,n]$ 分成两段，而 $A$ 需要选择一段 $+1$。

不妨在每次操作后删去大于 $1$ 的值，于是不难发现剩下的序列一定满足 $11100011$ 的形式。

假定当前序列开头有连续 $a$ 个 $1$，中间有连续 $b$ 个 $0$，最后有连续 $c$ 个 $1$。设 $\text{dp}(a,b,c)$ 表示当前局面剩下的操作次数。

不难发现可以枚举分割的位置，然后计算答案，时间复杂度 $O\left(n^4\right)$。

另外还有一个性质，设 $f(a,b,c,k)$ 表示当前局面如果决策位置为 $k$ 则接下来还需要操作的次数，不难发现 $f(a,b,c,k)$ 为单峰函数。

同时，设当前局面的最优决策位置为 $p(a,b,c)$，有 $c_1\le c_2\to p(a,b,c_1)\le p(a,b,c_2)$。

于是考虑决策单调性，可以做到 $O\left(n^3\right)$，但还是不能通过本题数据范围。

<hidden 查看代码>
<code cpp>
const int MAXN=505;
int dp[MAXN][MAXN][MAXN];
int pos[MAXN][MAXN][MAXN];
int cal(int a,int b,int c,int p){
	if(p<=a)
	return max(dp[a-p][b][c],dp[p+b][0][0]);
	else if(p<=a+b){
		int l=p-a,r=a+b-p;
		return max(dp[a][l][r],dp[l][r][c]);
	}
	else{
		int l=p-a-b,r=a+b+c-p;
		return max(dp[a][b][l],dp[b+r][0][0]);
	}
}
int main(){
	int n=read_int();
	pos[1][0][0]=pos[0][1][0]=pos[0][0][1]=1;
	_rep(s,2,n){
		for(int a=s;a>=0;a--)_rep(b,0,s-a){
			int c=s-a-b;
			int &p=pos[a][b][c];
			if(c==0)
			p=1;
			else
			p=pos[a][b][c-1];
			while(p<s-1){
				if(cal(a,b,c,p)>=cal(a,b,c,p+1))
				p++;
				else
				break;
			}
			dp[a][b][c]=cal(a,b,c,p)+1;
		}
	}
	_for(i,0,n)
	space(dp[i][n-i][0]);
	return 0;
}
</code>
</hidden>

不难发现 $B$ 询问的次数最多 $O\left(\log n\right)$ 次，于是交换 $\text{dp}$ 的值域和第三维。

设 $\text{dp}(i,a,b)$ 表示 $i$ 次操作能处理的局面 $(a,b,c)$ 中 $c$ 的最大值，如果 $\text{dp}(i,a,b)=-1$ 表示 $i$ 次操作不能处理局面 $(a,b,0)$。

关于状态转移也比较复杂，要分三种情况。

如果 $k\in [1,a]$，则 $(a,b,c)\to (k+b,0,0),(a-k,b,c)$，此时要保证 $\text{dp}(i-1,k+b,0)\ge 0$ 才算合法，否则 $B$ 就不能 $i$ 步走完。

合法情况下有 $\text{dp}(i,a,b)\gets \text{dp}(i-1,a-k,b)$。不难发现，$\text{dp}(i-1,a-k,b)$ 随 $k$ 增加递减，于是取合法情况的分界点即可。

如果 $k\in (a,a+b]$，则 $(a,b,c)\to (a,k-a,a+b-k),(k-a,a+b-k,c)$，此时要保证 $\text{dp}(i-1,a,k-a)\ge a+b-k$ 才算合法。

合法情况下有 $\text{dp}(i,a,b)\gets \text{dp}(i-1,k-a,a+b-k)$。同样 $\text{dp}(i-1,k-a,a+b-k)$ 也随 $k$ 增加递减。

最后 $k\in (a+b,a+b+c]$，不妨记 $k'=k-a-b$，则 $(a,b,c)\to (b,0,c-k'),(a,b,k')$。

此时要保证 $\text{dp}(i-1,b,0),\text{dp}(i-1,a,b)\ge 0$ 才算合法，不难发现，此时 $c=c-k'+k'=\text{dp}(i-1,b,0)+\text{dp}(i-1,a,b)$。

同时 $p(i,a,b)$ 表示当前状态最优决策位置，关于 $a$ 貌似具有不严格单峰性，根据打表结果有 $p(i,a,b)\ge p(i,a-1,b)-1$。

于是可以 $O(n^2\log n)$ 通过此题。

<hidden 查看代码>
<code cpp>
const int MAXV=20,MAXN=2005;
int dp[MAXV][MAXN][MAXN];
bool check(int i,int a,int b,int p){
	if(p<=a)
	return dp[i-1][p+b][0]>=0;
	else
	return dp[i-1][a][p-a]>=a+b-p;
}
int main(){
	int n=read_int();
	mem(dp,-1);
	dp[0][0][0]=1;
	dp[0][1][0]=dp[0][0][1]=0;
	_for(i,1,MAXV){
		_rep(b,0,n)for(int a=0,p=0;a<=n-b;a++){
			while(p<a+b&&check(i,a,b,p))p++;
			while(p&&!check(i,a,b,p))p--;
			dp[i][a][b]=(p<=a)?dp[i-1][a-p][b]:dp[i-1][p-a][a+b-p];
			if(dp[i-1][a][b]>=0&&dp[i-1][b][0]>=0)
			dp[i][a][b]=max(dp[i][a][b],dp[i-1][a][b]+dp[i-1][b][0]);
		}
	}
	_for(i,0,n){
		_for(j,0,MAXV){
			if(dp[j][i][n-i]>=0){
				space(j);
				break;
			}
		}
	}
	return 0;
}
</code>
</hidden>

===== D. Count =====

==== 题意 ====

给定一个 $n\times n$ 的网格图，有 $k$ 个格子不能选，分别为 $(r_1,c_1),(r_2,c_2)\cdots (r_k,c_k)$。

在此基础上选择 $m$ 个格子，满足每行每列至少选中一个格子，$r=c$ 和 $r+c=n+1$ 的对角线上至少选中一个格子。

==== 题解 ====

考虑容斥，首先枚举 $k$ 个不能选的格子的子集，强制选中这些格子，设共选了 $c$ 个格子。

进一步容斥计算在强制选中这些格子对应的方案数，考虑是否禁止对角线、是否禁止某行某列。

设 $\text{dp}(i,j,k)$ 表示强制只选 $i$ 行，只选 $j$ 列，且这些位置中有 $k$ 个位置因为强制不选对角线被禁止的方案数。

于是状态 $(i,j,k)$ 对应的方案数为 ${i\times j-k-c \choose m-c}\text{dp}(i,j,k)$。接下来考虑如何计算  $\text{dp}(i,j,k)$。

事实上，只有形如第 $i$ 行、第 $i$ 列、第 $n+1-i$ 行、第 $n+1-i$ 列这样的四元组会对 $k$ 产生影响。

于是可以将每个四元组看成一个物品，$O(2^4)$ 枚举这四元组每个元素的选择情况计算对 $k$ 的影响，然后三维背包合并所有四元组贡献。

由于 $(i,j,k)$ 的每个维度上界都是 $O(n)$，所以总时间复杂 $O\left(2^kn^4\right)$。实际上还是比较卡的，但题目数据比较友好。

<hidden 查看代码>
<code cpp>
const int MAXN=35,MAXV=MAXN*MAXN,mod=1e4+7;
int dp[MAXN][MAXN][MAXN<<1],temp[MAXN][MAXN][MAXN<<1];
int sr[MAXN],sc[MAXN],node[MAXN][2],frac[MAXV],invf[MAXV];
int quick_pow(int n,int k){
	int ans=1;
	while(k){
		if(k&1)ans=ans*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
int C(int n,int m){
	return frac[n]*invf[m]%mod*invf[n-m]%mod;
}
int solve(int n,int _k,int _c,int _s){
	int tf1=2,tf2=2,cnt=0;
	mem(sr,0);mem(sc,0);
	_for(i,0,_k){
		if(_s&(1<<i)){
			sr[node[i][0]]=1,sc[node[i][1]]=1;
			if(node[i][0]==node[i][1])
			tf1=1;
			if(node[i][0]+node[i][1]==n+1)
			tf2=1;
			cnt++;
		}
	}
	int ans=0;
	_for(f1,0,tf1)_for(f2,0,tf2){
		mem(dp,0);
		dp[0][0][0]=1;
		int mr=0,mc=0,mk=0;
		for(int p1=1,p2=n;p1<=p2;p1++,p2--){
			mem(temp,0);
			if(p1!=p2){
				mr+=2,mc+=2,mk+=4;
				_for(r1,sr[p1],2)_for(r2,sr[p2],2)
				_for(c1,sc[p1],2)_for(c2,sc[p2],2){
					int dr=r1+r2,dc=c1+c2;
					int dk=(r1&c1&f1)+(r2&c2&f1)+(r1&c2&f2)+(r2&c1&f2);
					_rep(i,dr,mr)_rep(j,dc,mc)_rep(k,dk,mk)
					temp[i][j][k]+=dp[i-dr][j-dc][k-dk];
				}
			}
			else{
				mr++,mc++,mk++;
				_for(dr,sr[p1],2)_for(dc,sc[p1],2){
					int dk=dr&dc&(f1|f2);
					_rep(i,dr,mr)_rep(j,dc,mc)_rep(k,dk,mk)
					temp[i][j][k]+=dp[i-dr][j-dc][k-dk];
				}
			}
			_rep(i,0,mr)_rep(j,0,mc)_rep(k,0,mk)
			dp[i][j][k]=temp[i][j][k]%mod;
		}
		_for(i,0,MAXN)_for(j,0,MAXN)_for(k,0,MAXN<<1){
			int tot=i*j-k;
			if(tot>=_c){
				int s=C(tot-cnt,_c-cnt)*dp[i][j][k]%mod;
				int sg=(n-i)+(n-j)+f1+f2+cnt;
				if(sg&1)
				ans=(ans-s)%mod;
				else
				ans=(ans+s)%mod;
			}
		}
	}
	return (ans+mod)%mod;
}
int main()
{
	int n=read_int(),k=read_int(),c=read_int();
	_for(i,0,k)
	node[i][0]=read_int(),node[i][1]=read_int();
	frac[0]=1;
	_for(i,1,MAXV)
	frac[i]=frac[i-1]*i%mod;
	invf[MAXV-1]=quick_pow(frac[MAXV-1],mod-2);
	for(int i=MAXV-1;i;i--)
	invf[i-1]=invf[i]*i%mod;
	int ans=0;
	_for(i,0,1<<k)
	ans=(ans+solve(n,k,c,i))%mod;
	enter(ans);
	return 0;
}
</code>
</hidden>

===== G. Yu Ling(Ling YueZheng) and Colorful Tree =====

==== 题意 ====

给定一棵点权树，初始值各点权值为 $0$，接下来两种操作：

  - $w(u)\gets x$，保证 $w(u)$ 之前一定为 $0$，该类操作的 $x$ 都不相同且 $1\le x\le n$
  - 给定 $1\le l,r,x\le n$，查询 $u$ 的最近祖先节点 $v$，满足 $x\mid w(v),l\le w(v)\le r$，输出 $u,v$ 之间的距离

==== 题解 ====

考虑离线操作，对每个权值，维护对他有贡献的操作序列。

首先对操作 $1$，显然 $x$ 会对所有是 $x$ 的因子的权值产生贡献，于是将操作 $1$ 加入到所有 $x$ 的因子的操作序列中。

对操作 $2$，直接丢到权值 $x$ 的操作序列处理即可。

接下来单独考虑每个权值的操作序列，发现操作序列一定都满足 $x\mid w(v)$ 这个约束。

于是只需要考虑 $l\le w(v)\le r$ 和 $v$ 是 $u$ 的最近祖先这两个约束。

首先转化一下$v$ 是 $u$ 的最近祖先这个约束，不难发现满足该约束的 $v$ 就是 $u$ 的祖先中 $\text{dfs}$ 序最大的点。

维护一个二维矩阵 $C$，$C[x][y]$ 表示 $\text{dfs}$ 序最大的 $v$，满足 $w(v)=x$ 且 $w(v)$ 是节点 $y$ 的祖先。

于是对操作 $1$ 等价于修改

$$
C[x][\text{dfn}(u)\sim \text{dfn}(u)+\text{sz}(u)-1]\gets \text{dfn}(u)
$$

操作 $2$ 等价于查询

$$
\max\left(C[l\sim r][\text{dfn}(u)]\right)
$$

考虑树套树维护 $C$，考虑修改操作共 $O(n\log n)$ 次，查询操作 $O(n)$，于是总时间复杂度 $O\left(n\log^3 n\right)$。

关于空间复杂度，首先对每个权值，由于他的倍数最多只有 $O(n)$ 个，所以修改操作最大只有 $O(n)$ 次。

树套树第二维是动态开点线段树，于是空间复杂度 $O\left(n\log^2 n\right)$。注意处理完每个权值的操作序列后要删除线段树，否则会爆空间。

<hidden 查看代码>
<code cpp>
const int MAXN=1.2e5+5,MAXM=150;
struct Edge{
	int to,w,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v,int w){
	edge[++edge_cnt]=Edge{v,w,head[u]};
	head[u]=edge_cnt;
}
int dfl[MAXN],dfr[MAXN],dfu[MAXN],dfs_t;
LL dis[MAXN];
void dfs(int u,int fa){
	dfl[u]=++dfs_t;
	dfu[dfs_t]=u;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dis[v]=dis[u]+edge[i].w;
		dfs(v,u);
	}
	dfr[u]=dfs_t;
}
struct node{
	int u,x,l,r,id;
	node(int u=0,int x=0,int l=0,int r=0,int id=0){
		this->u=u;
		this->x=x;
		this->l=l;
		this->r=r;
		this->id=id;
	}
};
namespace Tree{
	int ch[MAXN*MAXM][2],s[MAXN*MAXM],cnt;
	void clear(){cnt=0;}
	void update(int &k,int vl,int vr,int ql,int qr,int v){
		if(!k){
			k=++cnt;
			s[k]=0;
			ch[k][0]=ch[k][1]=0;
		}
		if(ql<=vl&&vr<=qr){
			s[k]=max(s[k],v);
			return;
		}
		int vm=vl+vr>>1;
		if(vm>=ql)
		update(ch[k][0],vl,vm,ql,qr,v);
		if(vm<qr)
		update(ch[k][1],vm+1,vr,ql,qr,v);
	}
	int query(int k,int vl,int vr,int pos){
		if(!k)return 0;
		if(vl==vr)return s[k];
		int vm=vl+vr>>1;
		if(vm>=pos)
		return max(s[k],query(ch[k][0],vl,vm,pos));
		else
		return max(s[k],query(ch[k][1],vm+1,vr,pos));
	}
}
int rt0[MAXN],rt[MAXN],n;
#define lowbit(x) (x&(-x))
void update(int pos,int u){
	Tree::update(rt0[pos],1,n,dfl[u],dfr[u],dfl[u]);
	while(pos<=n){
		Tree::update(rt[pos],1,n,dfl[u],dfr[u],dfl[u]);
		pos+=lowbit(pos);
	}
}
int query(int l,int r,int u){
	int ans=0;
	while(l<=r){
		ans=max(ans,Tree::query(rt0[r],1,n,dfl[u]));
		for(--r;r-l>=lowbit(r);r-=lowbit(r))
		ans=max(ans,Tree::query(rt[r],1,n,dfl[u]));
	}
	return ans;
}
void del(int pos){
	rt0[pos]=0;
	while(pos<=n){
		rt[pos]=0;
		pos+=lowbit(pos);
	}
}
vector<int> d[MAXN];
vector<node> opt[MAXN];
LL ans[MAXN];
void solve(int v){
	for(node q:opt[v]){
		if(q.x==0){
			int t=query(q.l,q.r,q.u);
			if(t==0)
			ans[q.id]=-1;
			else
			ans[q.id]=dis[q.u]-dis[dfu[t]];
		}
		else
		update(q.x,q.u);
	}
	for(node q:opt[v]){
		if(q.x!=0)
		del(q.x);
	}
	Tree::clear();
}
int main(){
	n=read_int();
	int q=read_int();
	_for(i,1,n){
		int u=read_int(),v=read_int(),w=read_int();
		Insert(u,v,w);
		Insert(v,u,w);
	}
	dfs(1,0);
	_rep(i,1,n){
		for(int j=i;j<=n;j+=i)
		d[j].push_back(i);
	}
	int qcnt=0;
	while(q--){
		int type=read_int(),u=read_int();
		if(type==0){
			int x=read_int();
			for(int v:d[x])
			opt[v].push_back(node(u,x));
		}
		else{
			int l=read_int(),r=read_int(),x=read_int();
			opt[x].push_back(node(u,0,l,r,qcnt++));
		}
	}
	_rep(i,1,n)
	solve(i);
	_for(i,0,qcnt){
		if(ans[i]==-1)
		puts("Impossible!");
		else
		enter(ans[i]);
	}
	return 0;
}
</code>
</hidden>

===== I. Kuriyama Mirai and Exclusive Or =====

==== 题意 ====

给定一个序列 $A$，接下来两种操作：

  - $a_i\gets a_i\oplus x(i\in [l,r])$
  - $a_i\gets a_i\oplus (x+i-l)(i\in [l,r])$

==== 题解 ====

$$
a_n=\left(\bigoplus_{i=1}^n b_i\right)\oplus\left(\bigoplus_{i=1}^n\bigoplus_{k=0}^{29} 2^k c(i,k)\right)\\
c(n,k)=\bigoplus_{i\times 2^k\le n} d(n-i\times 2^k,k)
$$

简单来讲 $a_n$ 是 $b_i,c(i,k)$ 的前缀和，$c(n,k)$ 是 $d(i,k)$ 的隔 $2^k$ 项前缀和。

然后操作 $1$ 只需要修改 $b_i$ 即可。操作 $2$ 的影响按位考虑影响，将 $[l,r]$ 区间操作等效于 $[l,\inf),[r+1,\inf)$ 两次操作。

每次操作对每个位是按 $001111000011110000$ 的规律周期性变化的。

对该序列进行一次差分，于是得到 $001000100010001000$，这个可以利用 $c(n,k)$ 维护。

再一次差分得到 $001000000000000000$ 发现可以利用 $d(n,k)$ 维护。

最后处理一下最开始非周期的部分即可，时间复杂度 $O((n+q)\log v)$。

<hidden 查看代码>
<code cpp>
const int MAXN=6e5+5,MAXB=30,mod=1<<30;
int n,a[MAXN],b[MAXN];
bitset<MAXN> c[MAXB];
void update(int pos,int v){
	_for(i,0,MAXB){
		int cyc=1<<(i+1),p1=pos%cyc,p2=((cyc-v%cyc)%cyc+(1<<i))%cyc,d=pos>>(i+1);
		if(p1>=p2){
			if(p1<p2+(1<<i)){
				b[pos]^=1<<i;
				if(d*cyc+p2+(1<<i)<MAXN)
				b[d*cyc+p2+(1<<i)]^=1<<i;
			}
			d++;
		}
		else if(p1<p2-(1<<i)){
			b[pos]^=1<<i;
			if(d*cyc+p2-(1<<i)<MAXN)
			b[d*cyc+p2-(1<<i)]^=1<<i;
		}
		if(d*cyc+p2<MAXN)
		c[i].flip(d*cyc+p2);
	}
}
int main() {
	n=read_int();
	int q=read_int();
	_for(i,0,n)a[i]=read_int();
	while(q--){
		int opt=read_int(),l=read_int()-1,r=read_int()-1,x=read_int();
		if(opt==0){
			b[l]^=x;
			b[r+1]^=x;
		}
		else{
			update(l,(x-l+mod)%mod);
			update(r+1,(x-l+mod)%mod);
		}
	}
	_for(i,0,MAXB){
		_for(j,0,n)if(j+(1<<i)<MAXN)
		c[i][j+(1<<i)]=c[i][j+(1<<i)]^c[i][j];
		_for(j,1,n)
		c[i][j]=c[i][j]^c[i][j-1];
		_for(j,0,n)
		a[j]^=(c[i][j]<<i);
	}
	_for(i,1,n)b[i]^=b[i-1];
	_for(i,0,n)a[i]^=b[i];
	_for(i,0,n)
	space(a[i]);
	return 0;
}
</code>
</hidden>

====== 赛后总结 =====

jxm：找操作中的不变量可能是解题的一种思路，比如这场的 $B$ 或者博弈论题。 $A$ 据说是 $\text{dp}$ 优化题，但没看懂题解，先咕了。

update：补完A了，感觉性质比较玄学。