本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-30 20:33:48

记录

A 一个 $n$ 写成 $m$ 挂 $10$ 分，C 的 $n=m$ 写了但是后来写前面的暴力时改小了数组，挂 $8$ 分。

题解

A. T392580 palin

考虑从左上角和右下角向中间 DP，显然可以设 $f_{i,x,y,X,Y}$ 表示步数和两个结尾的坐标，但是只有步数合法的坐标才有意义，这样会有很多无用状态。

所以设 $f_{i,j,k}$ 表示两边各走了 $i$ 步，左上角出发向下 $j$ 步，向右 $(i-j)$ 步，右下角出发向上 $k$ 步，向左 $(i-k)$ 步，且已走的路径两边回文的方案数。此时即从左上走到了 $(j+1,i-j+1)$，从右下走到了 $(n-k,m-i+k)$，先判断一下这两点是否相同，转移时枚举两边分别是竖着走还是横着走即可。

一共各走 $\lfloor\frac {n+m-2}2\rfloor$ 步。统计答案时，若 $n+m-2$ 为偶数，则两边最终会走到同一点，直接枚举走到的点。否则两边会走到距离恰为 $1$ 的两点，分一共竖着走了 $(n-1)$ 和 $(n-2)$ 步分别枚举即可。时间复杂度 $O(n^3)$。

#include<iostream>
using namespace std;
const int N=5e2+10;
const int mod=993244853;
void add(int &a,int b){a+=b;if(a>=mod)a-=mod;}
int n,m,res,st,f[2][N][N];
char a[N][N];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,st=(n+m-2)\/2;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		for(int j=m;j>=1;j--) a[i][j]=a[i][j-1];
	}
	if(a[1][1]!=a[n][m]) {cout<<0; return 0;}
	f[0][0][0]=1;
	for(int i=1;i<=st;i++)
	{
		int now=i%2,last=1-now;
		for(int j=0;j<=i;j++) for(int k=0;k<=i;k++)
		{
			f[now][j][k]=0;
			if(j>=n||k>=n||i-j>=m||i-k>=m) continue; 
			if(a[j+1][i-j+1]!=a[n-k][m-(i-k)]) continue;
			if(j&&k) add(f[now][j][k],f[last][j-1][k-1]);
			if(j&&i-k) add(f[now][j][k],f[last][j-1][k]);
			if(k&&i-j) add(f[now][j][k],f[last][j][k-1]);
			if(i-j&&i-k) add(f[now][j][k],f[last][j][k]);
		}
	}
	if((n+m-2)%2) for(int i=0;i<n;i++)
	{
		add(res,f[st%2][i][n-1-i]);
		if(n-2-i>=0) add(res,f[st%2][i][n-2-i]);
	}
	else for(int i=0;i<n;i++) add(res,f[st%2][i][n-1-i]);
	cout<<res;
	return 0;
}

B. T392683 Qsort

模拟一下发现，若 nan 作为基准值，则所有的 $a_l<a_i$ 均为假，没有数会被放到该 nan 前面，也即整个数组都不会变。若某个数 $x$ 作为基准值，则所有小于 $x$ 的数会被一起放到 $x$ 前面，其他的数和 nan 仍留在后面。不难发现此时前面的区间里只有数，因此最终一定会被排好序。

因此从左到右处理每个数，若已经被其他的数排序时提前，或者该数是 nan 则跳过，否则将后面所有小于 $x$ 的数升序放在 $x$ 前，最后放入 $x$。用优先队列可以实现该过程，时间复杂度 $O(n\log n)$。

#include<iostream>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;
const int N=5e5+10;
int n,ct,a[N],res[N];
bool vis[N];
string ts;
int getn()
{
	int len=ts.size(),tr=0;
	for(int i=0;i<len;i++) tr=tr*10+ts[i]-'0';
	return tr;
}
priority_queue <pii,vector<pii>,greater<pii> > q;
void sol()
{
	cin>>n,ct=0;
	while(q.size()) q.pop();
	for(int i=1;i<=n;i++) cin>>ts,a[i]=(ts[0]=='n'?0:getn()),vis[i]=0;
	for(int i=1;i<=n;i++) if(a[i]) q.push({a[i],i});
	for(int i=1;i<=n;i++) if(!vis[i])
	{
		if(!a[i]) {res[++ct]=a[i]; continue;}
		while(q.size())
		{
			pii te=q.top(); int x=te.first,y=te.second;
			if(x>=a[i]) break;
			if(y<=i) {q.pop(); continue;}
			vis[y]=1,res[++ct]=a[y],q.pop();
		}
		res[++ct]=a[i];
	}
	for(int i=1;i<=ct;i++)
	{
		if(res[i]) cout<<res[i]<<' ';
		else cout<<"nan ";
	}
	cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TT; cin>>TT;
	while(TT--) sol();
	return 0;
}

C. T392686 chaoticevil

首先若 $n$ 为奇数，添加 $a_{n+1}=0$ 变成偶数情况。

考虑如果给 $x$ 赋 $1$，给 $y$ 赋 $-1$，相当于给最终结果加上 $x-y$ 或减去 $y-x$，也就是说给两数赋上不同系数时，相当于只加或减了两数的差值。

因此我们将 $a$ 数组排序，并转化为 $b_i=a_{2i}-a_{2i-1}$，则 $b$ 数组长度 $k=\frac n2$。此时由于 $a$ 中每个数在 $\sum b$ 中都有贡献，只是有些取反了，所以 $\sum b$ 奇偶性不变，仍是偶数。同时由于原数两两不同，$b$ 数组中也没有 $0$。若能构造出一组 $e_i$ 使得 $\sum e_ib_i=0$，就可以构造出一组原问题的解。

$a$ 和 $b$ 似乎一样，但是后者有更强的性质，有 $\sum b\le m-\frac n2$。证明的话由于 $a_i\in [0,m]$，极差不超过 $m$，同时有 $\frac n2$ 个 $a_{2i+1}-a_{ai}$ 的空没有选，这些空的和至少为 $\frac n2$。

由于原题中保证 $\frac {2m}3<n$，我们取 $n=\frac {2m}3$ 代入上式，也即 $m-\frac n2<m-\frac m3=\frac {2m}3<n$，有 $\sum b<n=2k$。我们得到的新问题即为：给出长为 $k$，元素非 $0$ 的数组 $b$，满足 $\sum b<2k$ 且为偶数，构造一组 $e_i$ 使得 $\sum e_ib_i=0$。

不难想到如果 $b$ 中是偶数个 $1$，就可以给一半赋为 $-1$ 使得最终和为 $0$。如果有大于 $1$ 的数，考虑像最开始的转换一样再次转化，取出 $\max b$ 和 $\min b$，并加入它们的差值。由于 $\sum b<2k$，最大值和最小值此时不相等，因此差值仍为正。 $\sum b$ 减少了 $2\min b$，至少减少了 $2$ ，保证新的 $\sum b'<2k'$ 且仍为偶数，这样直到 $b$ 中数字全为 $1$ 即得解。

因此我们证明了在原问题条件下一定有解，并可以给出一组解。具体实现上可以使用优先队列维护目前的最值，并记录每个元素的来源（是哪两个元素相减所得），最终从所有的 $\pm 1$ 开始 dfs 一遍即可得到答案。时间复杂度 $O(n\log n)$。

#include<iostream>
#include<queue>
#include<algorithm>
#define pii pair<int,int>
using namespace std;
const int N=1e6+10;
int n,m,ct,a[N],v[N],c[N],lc[N],rc[N],p[N];
bool vis[N];
priority_queue <pii> qi,qa;
bool cmpa(int x,int y){return a[x]<a[y];}
void dfs(int x,int k)
{
	if(x<=0) {c[-x]=k; return;}
	dfs(lc[x],-k),dfs(rc[x],k);
}
void solv()
{
	for(int i=1;i<=ct;i++) qi.push({-v[i],i}),qa.push({v[i],i});
	while(qa.size())
	{
		int x=qa.top().second; qa.pop();
		while(vis[x]) x=qa.top().second,qa.pop();
		if(v[x]==1)
		{
			int k=1;
			for(int i=1;i<=ct;i++) if(!vis[i]) dfs(i,k),k=-k;
			return;
		}
		int y=qi.top().second; qi.pop();
		while(vis[y]) y=qi.top().second,qi.pop();
		ct++,vis[x]=vis[y]=1,lc[ct]=y,rc[ct]=x,v[ct]=v[x]-v[y];
		qi.push({-v[ct],ct}),qa.push({v[ct],ct});
	}
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],p[i]=i;
	sort(p+1,p+1+n,cmpa);
	for(int i=n;i>0;i-=2) ct++,v[ct]=a[p[i]]-a[p[i-1]],lc[ct]=-p[i-1],rc[ct]=-p[i];
	cout<<"NP-Hard solved\n",solv();
	for(int i=1;i<=n;i++) cout<<c[i]<<' ';
	return 0;
}

D. T392687 pigeons

发现一个点 $u$ 被区间 $[L,R]$ 选中当且仅当该点被区间完全包含，而该点的父亲节点不被完全包含，也即 $L\le l_u\le r_u\le R$ 成立且 $L\le l_{fa_u}\le r_{fa_u}\le R$ 不成立。另外由于 $u$ 被完全包含，所以其父亲区间跟 $[L,R]$ 一定有交。

所以我们考虑用 $L-1$ 和 $R+1$ 来刻画限制。具体地，我们发现根节点到 $L-1$ 的链上的点一定包含 $L-1$，那么它们的右子节点若不在链上，则一定不包含 $L-1$，且表示的区间左端点 $\ge L$，$R+1$ 到根节点的路径同理。

那么我们先找到 $L-1$ 和 $R+1$ 的 LCA $x$，则 $lc_x$ 到 $L-1$ 的链和 $rc_x$ 到 $R+1$ 这两条链不合法，且前者的不在链上的右儿子和后者不在链上的左儿子均合法，即在 $[L,R]$ 区间内。所以我们对这两条链进行操作，以他们的某个儿子所代表的区间长度为系数加上 $d$ 即可。

因此考虑树链剖分，对每一条重链维护其相邻的右子节点和左子节点的值，分在两棵线段树里维护即可。这样我们就可以把每条链剖成不超过 $\log n$ 条重链和轻边，那么我们用线段树维护重链的区间加，另外维护轻边的贡献。由于每个点只会连一条轻边，直接开数组维护每个点上轻边的值即可。时间复杂度 $O(n\log^2 n)$

#include<iostream>
#define int long long
using namespace std;
const int N=8e5+10;
int n,m,q,rt,ct,sr,ch[N][2],fa[N],w[N],aa[N][2];
int son[N],top[N],de[N],siz[N],id[N],ta[N];
struct sgmtt
{
	int t=1,lc[N],rc[N],le[N],s[N],tag[N];
	void pushup(int u) {s[u]=s[lc[u]]+s[rc[u]];}
	void pt(int u,int k) {s[u]+=k*le[u],tag[u]+=k;}
	void pushdown(int u) {if(tag[u]) pt(lc[u],tag[u]),pt(rc[u],tag[u]),tag[u]=0;}
	void build(int u,int l,int r,bool tf)
	{
		if(l==r) {le[u]=aa[l][tf]; return;}
		int mid=(l+r)\/2;
		lc[u]=++t,build(t,l,mid,tf);
		rc[u]=++t,build(t,mid+1,r,tf);
		pushup(u),le[u]=le[lc[u]]+le[rc[u]];
	}
	void update(int u,int l,int r,int ll,int rr,int k)
	{
		if(l>=ll&&r<=rr) {pt(u,k); return;}
		int mid=(l+r)\/2; pushdown(u);
		if(ll<=mid) update(lc[u],l,mid,ll,rr,k);
		if(rr>mid) update(rc[u],mid+1,r,ll,rr,k);
		pushup(u);
	}
	int query(int u,int l,int r,int ll,int rr)
	{
		if(l>=ll&&r<=rr) return s[u];
		int mid=(l+r)\/2,res=0; pushdown(u);
		if(ll<=mid) res+=query(lc[u],l,mid,ll,rr);
		if(rr>mid) res+=query(rc[u],mid+1,r,ll,rr);
		return res;
	}
}T[2];
void dfs(int u)
{
	siz[u]=1,de[u]=de[fa[u]]+1;
	if(u<=n) {w[u]=1; return;}
	for(int i=0;i<2;i++)
	{
		int c=ch[u][i]; dfs(c),w[u]+=w[c],siz[u]+=siz[c];
		if(siz[c]>siz[son[u]]) son[u]=c;
	}
}
void dfsb(int u,int to)
{
	id[u]=++ct,top[u]=to;
	if(!son[u]) return;
	dfsb(son[u],to);
	for(int i=0;i<2;i++)
	{
		int c=ch[u][i];
		if(c!=son[u]) dfsb(c,c),aa[id[u]][i]=w[c];
	}
}
void update(bool tf,int l,int r,int k) {T[tf].update(1,1,m,l,r,k);}
int query(bool tf,int l,int r) {return T[tf].query(1,1,m,l,r);}
int flca(int x,int y)
{
	if(x<0||y>n) return -1;
	while(top[x]!=top[y])
	{
		if(de[top[x]]<de[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if(de[x]>de[y]) swap(x,y);
	return x;
}
void add(int x,int to,int k,bool tf)
{
	while(top[x]!=top[to])
	{
		if(x!=top[x]) update(tf,id[top[x]],id[fa[x]],k),x=top[x];
		if(x!=ch[fa[x]][tf]) ta[x]+=k;
		x=fa[x];
	}
	if(x!=to) update(tf,id[to],id[fa[x]],k);
}
int ask(int x,int to,bool tf)
{
	int res=0;
	while(top[x]!=top[to])
	{
		if(x!=top[x]) res+=query(tf,id[top[x]],id[fa[x]]),x=top[x];
		if(x!=ch[fa[x]][tf]) res+=ta[x]*w[ch[fa[x]][tf]];
		x=fa[x];
	}
	if(x!=to) res+=query(tf,id[to],id[fa[x]]);
	return res;
}
void opa(int l,int r,int lca,int x)
{
	if(l==1&&r==n) sr+=x*n;
	else if(l==1) add(r+1,rt,x,0);
	else if(r==n) add(l-1,rt,x,1);
	else add(l-1,ch[lca][0],x,1),add(r+1,ch[lca][1],x,0);
}
int opb(int l,int r,int lca)
{
	if(l==1&&r==n) return sr;
	if(l==1) return ask(r+1,rt,0);
	if(r==n) return ask(l-1,rt,1);
	return ask(l-1,ch[lca][0],1)+ask(r+1,ch[lca][1],0);
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q,m=n*2-1;
	for(int i=n+1;i<=m;i++) cin>>ch[i][0]>>ch[i][1],fa[ch[i][0]]=fa[ch[i][1]]=i;
	for(int i=n+1;i<=m;i++) if(!fa[i]) rt=i;
	dfs(rt),dfsb(rt,rt),T[0].build(1,1,m,0),T[1].build(1,1,m,1);
	while(q--)
	{
		int op,l,r,x,lca; cin>>op>>l>>r,lca=flca(l-1,r+1);
		if(op==1) cin>>x,opa(l,r,lca,x);
		else cout<<opb(l,r,lca)<<'\n';
	}
	return 0;
}