Blog Detail

C20250053's blog
省集笔记（4.26~5.2）
C20250053 LV 9 @ 2026-5-28 10:05:51

题面就不放了，有原题的会标注题号。

4.26

A

对于 $X=x_i$ ，我们设有 $S=s_i$ 个 $X_i$ 的值为 $1$ ，

$$X\sqrt{np(1-p)}=S+u-np\\\ S+u=X\sqrt{np(1-p)}+np\\$$

因为 $u$ 是 $[-0.5,0.5]$ 之间的数，所以对于每个 $n$ ， $S=s_i$ 应该是 $X\sqrt{np(1-p)}+np$ 这个式子四舍五入。

考虑枚举 $n$ 。

我们定义概率密度 $f(X=x_i)=\lim_{\Delta x\to 0\\}\frac{P(X\in [x,x+\Delta x])}{\Delta x}$。

对于形如 $Y=aX+b$ 的式子，有 $f(X=x)=|a|\cdot f(Y=y)$ 。

于是有 $f(X=x_i)=f(S=s_i)\times \sqrt{np(1-p)}$ 。

因为 $u$ 的随机区间长度为 $1$ ，所以 $f(S=s_i)=P(S=s_i)$ ，

$P(S=s_i)$ 是容易用 dp 在 $\mathcal{O}(n^2)$ 计算的。

具体地，令 $f_{i,j}$ 表示在前 $i$ 个 $X_i$ 有 $j$ 个等于 $1$ 的概率，然后枚举当前 $X_i$ 是 $0$ 还是 $1$ 即可。

然我们令每个 $n$ 成为答案的概率 $L(n)=\prod_{i=1}^N P(X=x_i| n)$ 。

对式子两边取 $\ln$ ：

$$\ln L(n)=\sum_{i=1}^N \ln P(X=x_i)\\ =\sum_{i=1}^N \ln \Big(P(S=s_i)\cdot\sqrt{np(1-p)}\Big)\\ =\sum_{i=1}^N \Big(\ln P(S=s_i)+\ln\sqrt{np(1-p)}\Big)\\$$

于是就变成了对于所有 $x_i$ 累加，最后输出 $L$ 最大的 $n$ 即可。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e2 + 10;

int n;
ld p;
ld f[MAXN][MAXN],g[MAXN];
ld P[MAXN];

int main(){
	int Num;
	scanf("%d%Lf",&Num,&p);
	f[0][0]=1;
	FL(i,1,100)
		FL(j,0,i)
			f[i][j]=(j?f[i-1][j-1]*p:0)+f[i-1][j]*(1-p);
	FL(i,1,100) FL(j,0,i) f[i][j]=log(f[i][j]);
	FL(n,1,100) g[n]=1.0/2.0*log(n*p*(1-p));
	while(Num--){
		int N;
		scanf("%d",&N);
		FL(n,1,100) P[n]=0;
		while(N--){
			ld x;
			scanf("%Lf",&x);
			FL(n,1,100){
				int S=round(x*sqrt(n*p*(1-p))+n*p);
				if(S<0||S>n) P[n]=-1e9;
				else P[n]+=f[n][S]+g[n];
			}
		}
		printf("%d\n",max_element(P+1,P+100+1)-P);
	} 
}

B

首先是很显然的区间 dp，令 $f_{l,r}$ 表示 $x\in[l,r]$ 时猜出的最小代价，则有：

$$f_{l,r}=\min_{k\in [l,r)}\{\max(f_{l,k},f_{k+1,r})+a_k\}$$

时间复杂度 $\mathcal{O}(n^3)$ 。

你会发现最小代价的最坏情况不会超过 $V=9\times 19$ （也就是所有的 $a_i=9$ 然后直接二分）。

所以我们考虑定义 $f_{x,r}$ 表示花费了 $x$ 的代价且右端点为 $r$ 时左端点的最小值，

同理定义 $g_{x,l}$ 表示花费了 $x$ 的代价且左端点为 $l$ 时右端点的最大值。

转移我们从小到大枚举 $x$ ，然后选择询问的位置 $i$ ，分别找出用 $x-a_i$ 的代价可以猜出的最大区间 $[l,i]$ 和 $[i+1,r]$ （发现 $l/r$ 分别是 $f_{x-a_i,i}/g_{x-a_i,i+1}$ 的定义）。

于是 $f_{x,r}=\min\{f_{x,r},l\},g_{x,l}=\max\{g_{x,l},r\}$。

然后有 $f_{x-1,r}\to f_{x,r}/g_{x-1,l}\to g_{x,l}$ 以及 $f_{x,r+1}\to f_{x,r}/g_{x,l-1}\to g_{x,l}$ （显然 $r+1$ 的时候可以取到的左端点 $r$ 的时候也可以取到， $l-1$ 时可以取到的右端点 $l$ 的时候也可以取到，是单调的）。

然后找到满足 $g_{x,1}=n+1$ 的最小的 $x$ 就是答案。

时间复杂度 $\mathcal{O}(nV)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 5e5 + 10;
const int MAXV = 2e2 + 1;

int n;
int a[MAXN];
int f[MAXV][MAXN],g[MAXV][MAXN];
char s[MAXN];

int main(){
	scanf("%s",s+1),n=strlen(s+1);
	FL(i,1,n) a[i]=(int)(s[i]-'0');
	memset(f,0x3f,sizeof(f));
	memset(g,0xcf,sizeof(g)); 
	FL(i,1,n+1) f[0][i]=g[0][i]=i;
	FL(x,1,MAXV-1){
		FL(i,1,n+1) f[x][i]=f[x-1][i],g[x][i]=g[x-1][i];
		FL(i,1,n){
			if(a[i]>x) continue;
			int l=f[x-a[i]][i],r=g[x-a[i]][i+1];
			f[x][r]=min(f[x][r],l),g[x][l]=max(g[x][l],r);
		}
		FR(i,n,1) f[x][i]=min(f[x][i],f[x][i+1]);
		FL(i,2,n+1) g[x][i]=max(g[x][i],g[x][i-1]);
		if(g[x][1]==n+1) printf("%d\n",x),exit(0); 
	}
}

C

我们发现 $u,v$ 在 $T_1,T_2$ 中的位置关系是相对独立的，所以我们考虑先处理 $T_1$ 中的位置关系。

我们对 $T_1$ 进行点分治，枚举重心 $rt$ ，则 $d_1(u,v)=d_1(u,rt)+d_1(rt,v)$ ，令 $dis_u=d_1(rt,u)$ 。

然后考虑处理 $T_2$ 中 $u,v$ 的距离，我们对于 $rt$ 的连通块中的所有点建在 $T_2$ 上的虚树，称连通块中真实存在的点为关键点，令 $sum_u$ 表示 $u$ 子树内的关键点点数， $val_u$ 表示 $u$ 子树内关键点的 $dis$ 之和，则虚树上的一条边 $(u,v,w)(u=fa_v)$ ， $v$ 子树内的所有点的 $dis$ 会被贡献 $sum_{Rt}-sum_v$ 次， $v$ 子树外所有点的 $dis$ 会被贡献 $sum_v$ 次，累加进答案即可。

然后注意我们这样会算重来自 $rt$ 的同一棵子树的 $u,v$ ，显然这样的 $u,v$ 不会经过 $rt$ ，所以我们以这个子树的根为重心再算一次，从答案减去。

最后注意这里的 $u,v$ 是无序对，将答案 $\times 2$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;

int n,ans=0;
int siz[MAXN],mx[MAXN],rt=-1;
vector<PII>G[MAXN];
bool vis[MAXN];

struct Tree{
	int dep[MAXN],fa[MAXN];
	ll dis[MAXN]; 
	int siz[MAXN],son[MAXN];
	int top[MAXN],dfn[MAXN],qid[MAXN],idx=0;
	vector<PII>G[MAXN];
	int lca(int u,int v){
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]]) swap(u,v);
			u=fa[top[u]];
		}
		return (dep[u]<dep[v]?u:v);
	}
	void dfs1(int u,int fth){
		dep[u]=dep[fth]+1,fa[u]=fth;
		siz[u]=1,son[u]=0;
		for(auto i:G[u]){
			int v=i.first,w=i.second;
			if(v==fth) continue;
			dis[v]=dis[u]+w;
			dfs1(v,u);
			if(siz[v]>siz[son[u]]) son[u]=v;
			siz[u]+=siz[v];
		}
	}
	void dfs2(int u,int tp){
		top[u]=tp;
		dfn[u]=++idx,qid[idx]=u;
		if(son[u]) dfs2(son[u],tp);
		for(auto i:G[u]){
			int v=i.first;
			if(v==fa[u]||v==son[u]) continue;
			dfs2(v,v); 
		}
	}
	int Get_dis(int x,int y){
		return ((dis[x]+dis[y]-(dis[lca(x,y)]<<1ll))%mod+mod)%mod;
	}
	void init(){
		FL(i,1,n-1){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			G[u].push_back({v,w});
			G[v].push_back({u,w});
		}
		dfs1(1,0);
		dfs2(1,1);
	}
}T1,T2;

int Get_sz(int u,int fth){
	int sz=1;
	for(auto i:T1.G[u]){
		int v=i.first;
		if(v==fth||vis[v]) continue;
		sz+=Get_sz(v,u);
	}
	return sz;
}
void Get_rt(int u,int fth,int sum){
	siz[u]=1,mx[u]=0;
	for(auto i:T1.G[u]){
		int v=i.first;
		if(v==fth||vis[v]) continue;
		Get_rt(v,u,sum);
		mx[u]=max(mx[u],siz[v]);
		siz[u]+=siz[v];
	}
	mx[u]=max(mx[u],sum-siz[u]);
	if(rt==-1||mx[rt]>mx[u]) rt=u;
}

int nw=0;
int sum[MAXN],val[MAXN];
ll dis[MAXN];
vector<int>V;
bool us[MAXN];

void dfs1(int u,int fth){
	V.push_back(u),us[u]=1;
	for(auto i:T1.G[u]){
		int v=i.first;
		if(v==fth||vis[v]) continue;
		dfs1(v,u);
	}
}
void dfs2(int u,int fth){
	for(auto i:T1.G[u]){
		int v=i.first,w=i.second;
		if(v==fth||vis[v]) continue;
		dis[v]=(dis[u]+w)%mod;
		dfs2(v,u);
	}
}
void dfs3(int u){
	sum[u]=us[u],val[u]=(us[u]?dis[u]:0);
	for(auto i:G[u]){
		int v=i.first;
		dfs3(v);
		sum[u]+=sum[v];
		val[u]=(val[u]+val[v])%mod;
	}
}
void dfs4(int u){
	for(auto i:G[u]){
		int v=i.first,w=i.second;
		nw=(nw+1ll*w*(1ll*sum[v]*(val[V[0]]-val[v]+mod)%mod+1ll*(sum[V[0]]-sum[v]+mod)*val[v]%mod)%mod)%mod; 
		dfs4(v);
	}
}

bool cmp(int p,int q){
	return T2.dfn[p]<T2.dfn[q];
}

void Calc(int u,int k){
	V.clear(),dfs1(u,0);
	if(k==1) dis[u]=0,dfs2(u,0);
	int tot=(int)V.size();
	sort(V.begin(),V.end(),cmp);
	FL(i,1,tot-1) V.push_back(T2.lca(V[i],V[i-1]));
	sort(V.begin(),V.end(),cmp);
	V.erase(unique(V.begin(),V.end()),V.end()); 
	tot=(int)V.size();
	for(int u:V) G[u].clear();
	FL(i,1,tot-1){
		int ps=T2.lca(V[i],V[i-1]);
		G[ps].push_back({V[i],T2.Get_dis(ps,V[i])});
	}
	dfs3(V[0]);
	nw=0,dfs4(V[0]),ans=(ans+1ll*k*nw%mod+mod)%mod; 
	for(int u:V) us[u]=0;
}

void solve(int u){
	Calc(u,1);
	vis[u]=1;
	for(auto i:T1.G[u]){
		int v=i.first;
		if(vis[v]) continue;
		Calc(v,-1);
	}
	for(auto i:T1.G[u]){
		int v=i.first;
		if(vis[v]) continue;
		int sz=Get_sz(v,u);
		rt=-1,Get_rt(v,0,sz);
		solve(rt);
	}
} 

int main(){
	scanf("%d",&n);
	T1.init(),T2.init();
	rt=-1,Get_rt(1,0,n);
	solve(rt);
	printf("%lld\n",2ll*ans%mod);
}

4.27

A

我们发现初始时每一个基环树连通块是互不影响的。

然后对于每个基环，我们枚举环上的每个点的子树，设其离环的距离为 $dep_u$ ，在环上第 $pos_u$ 个点的子树内，那么它进入环上会在第 $pos_u-dep_u$ 个点上。

对于 $k=0$ ，我们对环上每个点的答案取 $\max$ 即可，令第 $i$ 个环的答案为 $mxd_i$ 。

然后观察样例我们发现我们有两种策略：

第一种是耗费 $1$ 次操作把一个基环树的基环变成自环，然后其他的基环树全部连到它上，那么此时答案就是连通块的大小。

第二种是不选择变成自环，我们会选择一个长度为 $L$ 的环，因为环长总和为 $\mathcal{O}(n)$ ，所以最多只有 $\mathcal{O}(\sqrt{n})$ 种不同的环长，我们把相同环长的环一起处理。

那么我们对于每棵基环树算出我们断开其中一条边并连到长度为 $L$ 的环上，能给环上其中的一个点贡献的最大的点数 $cnt_i$ 。

然后我们把所有环按照这个点数从大到小排序，令 $s_i=\sum_{j=1}^i cnt_j$ ，然后考虑选一个长度为 $L$ 的环作为主环把其他树连上去。

假设我们要计算 $k=i$ 的答案。

选的主环贡献不在前 $i$ 大，答案就是 $s_i+mxd_{id}$ 那么我们肯定选 $id\in[k+1,tot]$ 中 $mxd_{id}$ 最大的
选的主环贡献在前 $i$ 大，答案就是 $s_{i+1}-cnt_{id}+mxd_{id}$ ，那么我们肯定选 $id\in [1,i]$ 中 $mxd_{id}-cnt_{id}$ 最大的。

于是做完了，时间复杂度 $\mathcal{O}(n\sqrt{n}\log n)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;
const int inf = 0x3f3f3f3f;

int n,ans=0;
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
vector<int>G[MAXN],V[MAXN];
int deg[MAXN],dep[MAXN],blg[MAXN],pos[MAXN];
int cyc[MAXN],sum[MAXN],typ[MAXN],mxd[MAXN],tot=0;
int Ans[MAXN];
bool vis[MAXN];

vector<int>vL;
bool vsL[MAXN];

int cnt[MAXN],qcnt[MAXN],nw=0;
vector<int>Us;

PII e[MAXN];
int rnk[MAXN],suf[MAXN],prv[MAXN],s[MAXN];

void Add(int val){
	if(!cnt[val]) Us.push_back(val); 
	if(cnt[val]>0) qcnt[cnt[val]]--;
	cnt[val]++,qcnt[cnt[val]]++;
	if(cnt[val]>nw) nw=cnt[val];
}
void Del(int val){
	qcnt[cnt[val]]--;
	if(cnt[val]==nw&&!qcnt[cnt[val]]) nw--;
	cnt[val]--;
	if(cnt[val]>0) qcnt[cnt[val]]++;
}

int Get(int id,int L){
	int C=cyc[id];
	vector<vector<int> >Vs(C+1);
	for(int u:V[id]) Vs[pos[u]].push_back(u);
	for(int u:V[id]){//C->1
		int p=(dep[u]+(C-pos[u])+L)%L;
		Add(p);
	}
	int mx=nw;
	FL(B,1,C){
		for(int u:Vs[B]){
			int p=((dep[u]+(C-pos[u]))%L+L)%L,np=((dep[u]-pos[u])%L+L)%L;
			Del(p),Add(np);
		}
		mx=max(mx,nw);
	}
	for(int val:Us) cnt[val]=0;
	Us.clear(),nw=0;
	for(int i=1;i<=(int)V[id].size();i++) qcnt[i]=0;
	return mx;
}

int dfs(int u,int tp,int len){
	pos[u]=tp,blg[u]=tot;
	V[tot].push_back(u);
	int ps=((tp-dep[u]%len)%len+len-1)%len+1;
	d[b[ps]]++;
	int sz=1;
	for(int v:G[u])
		dep[v]=dep[u]+1,sz+=dfs(v,tp,len);
	return sz;
}

bool cmp(int p,int q){
	return sum[p]>sum[q];
}

int main(){
	scanf("%d",&n); 
	FL(i,1,n) scanf("%d",&a[i]),deg[a[i]]++;
	queue<int>q;
	FL(i,1,n)
		if(!deg[i]) q.push(i);
	while(!q.empty()){
		int u=q.front(),v=a[u];
		q.pop();
		vis[u]=1,deg[v]--;
		G[v].push_back(u);
		if(!deg[v]) q.push(v);
	}
	FL(i,1,n){
		if(vis[i]) continue;
		int j=i,len=0,num=0,mx=0;
		tot++;
		while(!vis[j]) vis[j]=1,b[++len]=j,j=a[j];
		cyc[tot]=len,typ[tot]=(len==1);
		FL(k,1,len) num+=dfs(b[k],k,len);
		sum[tot]=num;
		FL(k,1,len) mx=max(mx,d[b[k]]);
		mxd[tot]=mx,ans=max(ans,mx);
	}
	Ans[0]=ans;
	FL(i,1,tot) c[i]=i;
	sort(c+1,c+tot+1,cmp);
	FL(i,1,tot) s[i]=s[i-1]+sum[c[i]];
	bool ty=0;
	FL(i,1,tot)
		ty|=typ[c[i]],Ans[i]=max(Ans[i],s[min(tot,i+ty)]);
	FL(i,tot+1,n) Ans[i]=max(Ans[i],n);
	FL(i,1,tot)
		if(!vsL[cyc[i]])
			vsL[cyc[i]]=1,vL.push_back(cyc[i]);
	for(int L:vL){
		FL(i,1,tot) e[i]={Get(i,L),i};
		sort(e+1,e+tot+1,greater<PII>());
		FL(i,1,tot) rnk[i]=s[i]=0,suf[i]=prv[i]=-inf;
		FL(i,1,tot)
			rnk[e[i].second]=i,s[i]=s[i-1]+e[i].first;
		FL(id,1,tot){
			if(cyc[id]==L){
				suf[rnk[id]]=max(suf[rnk[id]],mxd[id]);
				prv[rnk[id]]=max(prv[rnk[id]],mxd[id]-e[rnk[id]].first);
			}
		}
		FR(i,tot-1,1) suf[i]=max(suf[i],suf[i+1]);
		FL(i,2,tot) prv[i]=max(prv[i],prv[i-1]);
		FL(i,1,tot)
			Ans[i]=max({Ans[i],(i<tot?s[i]+suf[i+1]:-inf),(i<tot?s[i+1]+prv[i]:-inf)});
	}
	FL(i,1,n) Ans[i]=max(Ans[i],Ans[i-1]);
	FL(i,0,n) printf("%d ",Ans[i]);
	puts("");
}

B

发现题目给定的操作是选择一个区间，将区间内的所有数变成该区间的最大值。

因此原序列中的每个 $a_i$ 要么被其他数覆盖，要么扩展并覆盖一个连续的区间 $[l_i,r_i]$ 。

发现最终这些非空的 $[l_i, r_i]$ 恰好构成了 $[1,n]$ 的一个划分，且区间之间的相对顺序与原下标顺序一致。

若一个元素 $a_i$ 能够覆盖某个位置，那么要求它在扩展的过程中，遇到的数都不大于它。

因此，对于每个 $a_i$ ，我们可以向左找到第一个大于它的位置 $L_i$ ，向右找到第一个大于它的位置 $R_i$ ，则 $[l_i,r_i]\sube [L_i,R_i]$ 。

如果原序列是一个排列，因为没有重复元素，那么最终局面和合法的区间划分是一一对应的，直接计数即可。

具体地，令 $f_{i,j}$ 表示原序列的前 $i$ 个元素恰好覆盖了最终序列的前 $j$ 个位置的方案数。

转移有 $f_{i,j}=f_{i-1,j}+\sum_{k=l}^jf_{i-1,k-1}$ 。

然后如果有重复的元素，我们考虑计数字典序最大的划分，为了让字典序最大，每个区间应该尽可能地向右扩展。

所以如果存在两个相同的值 $i<j\land a_i=a_j$ ，且 $[L_i,R_i]=[L_j,R_j]$ ，区间 $[i+1,j-1]$ 中的元素都没有被选择，而后面的 $j$ 却被选择了，那么我们可以让 $i$ 接管 $j$ 的区间，显然这样的字典序更大。

于是减去 $f_{prv_{a_i},j-1}$ ，也就是上一个相同元素覆盖到 $j$ 的前一个位置的方案数。

时间复杂度 $\mathcal{O}(n^3)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 5e3 + 10;
const int mod = 998244353;

int n;
int a[MAXN];
int L[MAXN],R[MAXN],prv[MAXN];
int f[MAXN][MAXN];

int main(){
	scanf("%d",&n);
	FL(i,1,n) scanf("%d",&a[i]);
	f[0][0]=1;
	FL(i,1,n){
		int l=i,r=i;
		while(l-1>=1&&a[l-1]<=a[i]) l--;
		while(r+1<=n&&a[r+1]<=a[i]) r++;
		L[i]=l,R[i]=r;
		FL(j,l,r) f[i][j]=f[i-1][j-1];
		if(prv[a[i]]&&L[prv[a[i]]]==l&&R[prv[a[i]]]==r)
			FL(j,l,r) f[i][j]=(f[i][j]-f[prv[a[i]]][j-1]+mod)%mod;
		FL(j,l,r) f[i][j]=(f[i][j]+f[i][j-1])%mod;
		FL(j,0,n) f[i][j]=(f[i][j]+f[i-1][j])%mod;
		prv[a[i]]=i; 
	}
	printf("%d\n",f[n][n]);
}

C

首先考虑 $\sum_{i=1}^nQ_i=360$ 的情况，那么此时所有割出的圆弧都是有用的。

全割半径的情况是平凡的，需要 $n$ 次。

那么考虑至少割了一条直径的情况。

我们不妨令这条直径是水平割的，于是把 $Q$ 分成了两个部分 $A,B$ ，且 $A,B$ 都按照顺时针方向放圆弧。

于是有 dp，令 $f_{S,i}$ 表示已经放置的圆弧的集合为 $S$ ，在 $A$ 集合中的圆弧前缀和为 $i$ ，那么 $B$ 集合中的圆弧前缀和是容易计算的，有 $j=sum_S-i$ 。然后每次考虑 $S$ 中最后放入的圆弧 $L$ ，如果放入的是 $A$ 集合且 $i-L=j$ 那么不需要再割一次，直接把这一次切割变成直径即可，放入 $B$ 集合同理。

然后拓展到 $\sum_{i=1}^nQ_i\not = 360$ 。

我们可以证明说没用的废料不超过两块且存在一种方案使其分别在 $A$ 集合和 $B$ 集合的末尾。

（显然如果有一段没用的圆弧在两段有用的圆弧之间，我们一定需要两刀把它和这两段圆弧割开，就算第二刀能和 $B$ 集合共用一条直径，把没用的圆弧移到集合的最后也一定是不劣的，因为移到后面一定不会增加切割次数）。

于是我们沿用 $\sum_{i=1}^n Q_i=360$ 的 dp 即可，

对于全割半径的方案，如果和不为 $360$ ，我们需要割 $n+1$ 刀（为了隔开没用的圆弧，显然只有一段）。

然后对于割直径的情况，我们枚举 $A$ 集合的前缀和 $j$ ，答案就是 $f_{U,j}+1-[j=180\lor (sum_U-j)=180]$ ，

$+1$ 是割的直径，后面减去的是如果 $j=180$ 那么末尾切的一刀和直径是重叠的（用的是 $\lor$ 是因为当 $j=sum_U-j=180$ 的时候， $f$ 已经把这两刀当作一条直径计算了，所以只用减去 $1$ ）。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 16 + 3;
const int MAXV = 360 + 10;
const int MR = (1<<16) + 5;
const int inf = 0x3f3f3f3f;

int n,U;
int ans,tot;
int a[MAXN];
int sum[MR];
int f[MR][MAXV],prv[MR][MAXV];
bool ct[MAXV];

int main(){
	scanf("%d",&n),U=(1<<n)-1;
	FL(i,1,n) scanf("%d",&a[i]);
	FL(S,0,U)
		FL(i,1,n)
			if((S>>i-1)&1) sum[S]+=a[i];
	FL(S,0,U) FL(j,0,180) f[S][j]=inf;
	f[0][0]=0;
	FL(S,0,U){
		FL(j,1,180){
			int k=sum[S]-j;
			if(k>180) continue;
			FL(i,1,n){
				if(!((S>>i-1)&1)) continue;
				if(j>=a[i]&&f[S][j]>f[S^(1<<i-1)][j-a[i]]+(j!=k))
					f[S][j]=f[S^(1<<i-1)][j-a[i]]+(j!=k),prv[S][j]=i;
				if(k>=a[i]&&f[S][j]>f[S^(1<<i-1)][j]+(j!=k))
					f[S][j]=f[S^(1<<i-1)][j]+(j!=k),prv[S][j]=-i;
			}
		}
	}
	ans=n+(sum[U]!=360),tot=-1;
	FL(j,max(0,sum[U]-180),min(180,sum[U]))
		if(f[U][j]+1-(j==180||(sum[U]-j)==180)<=ans) ans=f[U][j]+1-(j==180||(sum[U]-j)==180),tot=j;
	if(tot==-1){
		printf("%d\n",n+(sum[U]!=360));
		puts("0 0");
		FL(i,1,n-1+(sum[U]!=360)) printf("%d 0\n",sum[(1<<i)-1]);
		exit(0);
	}
	ct[0]=ct[180]=1;
	int S=U,j=tot;
	while(S){
		int ps=prv[S][j],k=sum[S]-j;
		ct[j]=ct[k+180]=1;
		if(ps>0) j-=a[ps],S^=(1<<ps-1);
		else S^=(1<<(-ps)-1);
	}
	vector<PII>Ans;
	FL(i,0,359){
		if(i<180&&ct[i]&&ct[i+180]) Ans.push_back({i,1});
		if(i<180&&ct[i]&&!ct[i+180]) Ans.push_back({i,0}); 
		if(i>=180&&ct[i]&&!ct[i-180]) Ans.push_back({i,0});
	}
	printf("%d\n",(int)Ans.size()),assert((int)Ans.size()==ans);
	for(PII i:Ans) printf("%d %d\n",i.first,i.second);
}

4.28

A

感觉比较显然的是，你把每种男生看作 $(a_i,b_i)$ 的一条边，那么要求图中任意两条边都有公共节点。

如果你选择了第 $i$ 种男生，你把 $c_i$ 个全选上肯定是最优的，

因为这 $c_i$ 条边互相之间肯定是满足条件的，然后和其他边的话，如果第 $1$ 条是合法的那么之后均是合法的。

是不是发现满足条件的图只有菊花和三角形。

菊花是容易的，加边的时候累加和每个点相连的边的边权和即可。

然后考虑三角形，

我们考虑一条边 $(u,v)$ 可能作为答案的条件，那么要求这条边的边权 $w$ 加上 $u$ 出发的除了 $(u,v)$ 外的最大边权以及 $v$ 出发的除了 $(u,v)$ 外的最大边权，这三个的和大于最大的菊花图的答案。

我们把满足条件的边加入图，然后根据度数进行定向，度数小的连向度数大的，度数相同的编号小的连向编号大的。

时间复杂度 $\mathcal{O}(m\sqrt{m})$ ，我不是很清楚 $m$ 的量级，但是跑到了最优解。

然后讲评的时候是说答案三角形一定有两条边是一个点出发的最大的两条边。

设三角形的三条边为 $a,b,c(a\ge b\ge c)$ ，若 $a,b$ 不是最大的两条边，那么有这个点出发的 $d\ge \min\{a,b\}\ge c$ ，那么 $a+b+d\ge a+b+c$ ，这个三角形一定不优。

哈希表可以做到线性。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e7 + 10;

char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}

int n;
ll ans;
ll num[MAXN];
int deg[MAXN];
int mx1[MAXN],mx2[MAXN];
int head[MAXN],cnt=0;
struct node{
	int v,w,nxt;
}e[MAXN];
void Add_edge(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
array<int,3> ed[MAXN];
int mk[MAXN];
bool us[MAXN];

int main(){
	int Num;
	Num=read();
	while(Num--){
		n=read(),ans=0;
		FL(i,1,(n<<1)) deg[i]=num[i]=0,mx1[i]=mx2[i]=0,head[i]=0,us[i]=0;
		cnt=0;
		FL(i,1,n){
			int u,v,w;
			u=read(),v=read(),w=read();
			if(u>v) swap(u,v);
			if(w>mx1[u]) mx2[u]=mx1[u],mx1[u]=w;
			else if(w>mx2[u]) mx2[u]=w;
			if(w>mx1[v]) mx2[v]=mx1[v],mx1[v]=w;
			else if(w>mx2[v]) mx2[v]=w;
			num[u]+=w,num[v]+=w;
			ed[i]={u,v,w},us[i]=0;
		}
		FL(i,1,(n<<1)) ans=max(ans,num[i]);
		FL(i,1,n){
			int u=ed[i][0],v=ed[i][1],w=ed[i][2];
			if((ll)w+(mx1[u]==w?mx2[u]:mx1[u])+(mx1[v]==w?mx2[v]:mx1[v])>ans)
				us[i]=1,deg[u]++,deg[v]++;
		}
		FL(i,1,n){
			if(!us[i]) continue;
			int u=ed[i][0],v=ed[i][1],w=ed[i][2];
			if(deg[u]<deg[v]) Add_edge(u,v,w);
			else if(deg[u]>deg[v]) Add_edge(v,u,w);
			else if(u<v) Add_edge(u,v,w);
			else Add_edge(v,u,w);
		}
		FL(u,1,(n<<1)){
			for(int i=head[u];i;i=e[i].nxt){
				int v=e[i].v,w=e[i].w;
				mk[v]=w;
			}
			for(int i=head[u];i;i=e[i].nxt){
				int v1=e[i].v,w1=e[i].w;
				for(int j=head[v1];j;j=e[j].nxt){
					int v2=e[j].v,w2=e[j].w;
					if(mk[v2]) ans=max(ans,(ll)w1+w2+mk[v2]);
				}
			}
			for(int i=head[u];i;i=e[i].nxt){
				int v=e[i].v;
				mk[v]=0;
			}
		}
		printf("%lld\n",ans);
	}
}

B

可以把一次操作拆为给所有数加上 $t$ ，然后选择一个位置减去 $k+t$ 。

假设我们一共操作了 $x$ 次，其中第 $i$ 个位置被选择了 $c_i$ 次（ $\sum_{i=1}^n c_i=x$ ），那么 $c_i$ 要满足：

$$a_i+t\cdot x-(k+t)\cdot c_i \le 0\\ \Rightarrow c_i\ge \frac{a_i+t\cdot x}{k+t}$$

显然 $t=0$ 时这个式子和 $x$ 无关可以直接求出，然后当 $k=0$ 且 $a_i>0$ 时， $c_i\ge x$ ，显然无解。

可以推出一个 $x$ 合法的充要条件是：

$$\sum_{i=1}^n\max(0,\lceil\frac{a_i+t\cdot x}{k+t}\rceil)\le x$$

于是我们要找最小的合法的 $x$ .

我们先把 $a_i$ 从大到小排序，显然此时 $c_1\ge c_2\ge \cdots\ge c_n$ 。

考虑我们操作了 $m$ 个不同的数时被选择的每个数值的变化量 $\Delta=t(m-1)-k$ 。

如果 $t(m-1)>k$ ，那么此时每个数值都是在增大的，显然不进行第 $m$ 次操作会更优。

所以我们最多只可能操作 $m$ 个不同的数（ $m$ 是满足 $t(m-1)\le k$ 的最大的 $m$ ），因为 $c_i$ 单调不升，

所以我们最多对序列的前 $m$ 个数进行操作，其余数一定不会被操作，如果我们操作了后面的数，我们可以撤销这些操作，使得总操作次数更少且依然合法。

然后我们对这个式子两边同时加 $t$ ，于是有 $t\cdot m\le k+t$ ，

我们发现，当 $x$ 的增量 $\Delta x\in [0,m-1]$ 时， $c_i$ 的变化量不超过 $1$ ，

所以我们把 $x$ 按 $m$ 个为周期进行表示，即 $x=mid\cdot m+\Delta x(\Delta x\in [0,m-1])$ ，显然 $x$ 的合法性关于 $mid$ 单调，于是我们二分 $mid$ 。

我们记录差分数组 $d$ ，还原出来就是 $b=x-\sum c$ ，初始 $d_0=mid\cdot m$ ， $d_i=1(i\in [1,m-1])$ ，也就是 $b_i=mid\cdot m+i$ ，对于每个 $c_i$ 我们可以算出初始的值 $dl=\lceil\frac{a_i+t\cdot mid\cdot m}{k+t}\rceil$ ，以及这个变化的位置 $ps$ ，并令 $d_0\to d_0-dl,d_{ps}\to d_{ps}-1$ 。

令 $b_i=\sum_{j=1}^i d_j$ ，然后如果存在 $b_i\ge 0$ 那么说明 $x=mid\cdot m+i$ 是合法的，返回最小的合法的 $x$ 。

时间复杂度 $\mathcal{O}(n\log n+m\log V)$ ，其中 $V=10^9$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e6 + 10;
const int ll inf = 0x3f3f3f3f;

ll n,m,k,t,lim;
ll a[MAXN],c[MAXN],d[MAXN];
int id[MAXN];

ll check(int mid){
	d[0]=mid*m;
	FL(i,1,m-1) d[i]=1;
	FL(i,1,m){
		i128 val=a[id[i]]+(i128)mid*m*t;
		if(val+(m-1)*t<=0) continue;
		ll dl=(val+k+t-1)/(k+t),ps=(dl*(k+t)-val)/t+1;
		d[0]-=dl;
		if(ps<m) d[ps]--;
	}
	FL(i,1,m-1) d[i]+=d[i-1];
	FL(i,0,m-1) if(d[i]>=0) return mid*m+i;
	return -1;
}

bool cmp(int p,int q){
	return a[p]>a[q];
}

int main(){
	scanf("%lld%lld%lld",&n,&k,&t),lim=n*inf;
	FL(i,1,n) scanf("%lld",&a[i]),id[i]=i;
	if(!t){
		ll sum=0;
		FL(i,1,n){
			if(a[i]>0&&!k) puts("-1"),exit(0);
			else if(a[i]>0) c[i]=(a[i]+k-1)/k,sum+=c[i];
		}
		printf("%lld\n",sum);
		FL(i,1,n) printf("%lld ",c[i]);
		puts(""),exit(0);
	}
	sort(id+1,id+n+1,cmp),m=n;
	while(m&&t*(m-1)>k){
		if(a[id[m]]>0) puts("-1"),exit(0);
		lim=min(lim,(-a[id[m]])/t),m--;
	}
	if(!m){
		puts("0");
		FL(i,1,n) printf("0 ");
		puts(""),exit(0);
	}
	int l=0,r=inf,pos=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)!=-1) pos=mid,r=mid-1;
		else l=mid+1;
	}
	if(pos==-1) puts("-1"),exit(0);
	ll sum=check(pos),ans=sum;
	if(sum>lim) puts("-1"),exit(0);
	printf("%lld\n",sum);
	FL(i,1,m){
		i128 val=a[id[i]]+(i128)ans*t;
		if(val>0) c[id[i]]=(val+k+t-1)/(k+t),sum-=c[id[i]];
	}
	c[id[1]]+=sum;
	FL(i,1,n) printf("%lld ",c[i]);
}

C

题意翻译一下就是对于无限图任意坐标 $(x,y)$ ，它的状态与坐标 $(x\bmod R,y\bmod C)$ 的状态完全相同。

我们可以建立一张图，相邻（跨越边界的也算）两点之间连边，边权是移动量，也就是二维向量 $(0,1)/(0,-1)/(1,0)/(-1,0)$ 。

考虑把 $(s_x,s_y),(t_x,t_y)$ 都映射到这个图，也就是从 $(s_x\bmod R,s_y\bmod C)$ 走到 $(t_x\bmod R,t_y\bmod C)$ 。

如果在这张图中都不在一个连通块，那么显然是无法到达的。

否则我们可以在这张图这个连通块的 dfs 树上找到一条位移为 $(D_x,D_y)$ 的路径，但是我们在无限图中想要的位移是 $(t_x-s_x,t_y-s_y)$ ，所以我们考虑走一些这张图上的环来达成。

（这张图上的环对应无限图上在 $x$ 方向改变了 $R$ 的整数倍，在 $y$ 方向改变了 $C$ 的整数倍）。

我们对于每个连通块建出 dfs 树，那么每条非树边 $(u,v)$ 都对应一个环。

$Rt\to u:(disx_u,disy_u),u\to v:(wx,wy),v\to Rt:(-disx_v,-disy_v)$，

$Rt\to \mathrm{lca}$ 在向量加减中被抵消了，所以这个环对应的二维向量是 $(disx_u+wx-disx_v,disy_u+wy-disy_v)$ 。

现在我们在连通块中找到了很多环，每个环可以贡献一个二维向量 $v_i$ 。

也就是问下面这个方程有没有整数解：

$$k_1v_1+k_2v_2+\cdots +k_nv_n=((t_x-s_x)-D_x,(t_y-s_y)-D_y)$$

然后发现二维向量也可以辗转相除：

对于二维向量 $(A,B),(C,D)$ ，如果 $A>C$ ，那么 $(A,B)(C,D)\to (A-k\cdot C,B-k\cdot D)(C,D)$ 能表示出的向量是等价的，那么此时最后会得到形如 $(p,q),(0,r)$ 的两个向量。

于是每次加入新的向量和 $(p,q)$ 辗转相除一下然后剩下的余数和 $r$ 取 $\gcd$ 即可。

最后问题变为：

a(p,q)+b(0,r)=((t_x-s_x)-D_x,(t_y-s_y)-D_y)

有没有解，然后判断是容易的。

时间复杂度 $\mathcal{O}(RC\log RC+Q)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define id(i,j) ((i)*m+(j))
using namespace std;
const int MAXN = 1e3 + 10;

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int n,m,q;
char s[MAXN][MAXN];
vector<array<int,3> >G[MAXN*MAXN];
int disx[MAXN*MAXN],disy[MAXN*MAXN],vis[MAXN*MAXN];

struct Basis{
	ll p,q,r;
	void init(){
		p=q=r=0;
	} 
	void Ins(ll a,ll b){
		if(a<0) a=-a,b=-b;
		while(1){
			if(a>p) swap(a,p),swap(b,q);
			if(!a) break;
			ll d=p/a;
			p-=d*a,q-=d*b;
		}
		r=__gcd(r,b);
	}
	bool Chk(ll x,ll y){
		if(x){
			if(!p||x%p) return 0;
			y-=x/p*q;
		}
		if(!y) return 1;
		if(!r||y%r) return 0;
		return 1;
	}
}T[MAXN*MAXN];

void dfs(int u,int tp){
	vis[u]=tp;
	for(auto i:G[u]){
		int v=i[0],wx=i[1],wy=i[2];
		if(vis[v]==-1) disx[v]=disx[u]+wx,disy[v]=disy[u]+wy,dfs(v,tp);
		else T[tp].Ins(disx[u]+wx-disx[v],disy[u]+wy-disy[v]);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	FR(i,n-1,0) scanf("%s",s[i]);
	FL(i,0,n-1){
		FL(j,0,m-1){
			if(s[i][j]!='.') continue;
			FL(k,0,3){
				int nx=((i+dx[k])%n+n)%n,ny=((j+dy[k])%m+m)%m;
				if(s[nx][ny]=='.') G[id(i,j)].push_back({id(nx,ny),dx[k],dy[k]});
			}
		}
	}
	FL(i,0,id(n-1,m-1)) vis[i]=-1;
	FL(i,0,id(n-1,m-1)) if(vis[i]==-1) T[i].init(),dfs(i,i);
	scanf("%d",&q);
	while(q--){
		ll sx,sy,ex,ey;
		scanf("%lld%lld%lld%lld",&sy,&sx,&ey,&ex);
		int s=id(sx%n,sy%m),t=id(ex%n,ey%m);
		if(vis[s]!=vis[t]) puts("No");
		else puts(T[vis[s]].Chk((ex-sx)-(disx[t]-disx[s]),(ey-sy)-(disy[t]-disy[s]))?"Yes":"No");
	}
}

4.29

A

原题 P16357

首先 $n$ 是偶数的情况是简单的，显然所有木块的数量都需要是偶数，然后构造一个回文串即可。

然后考虑 $n$ 是奇数的情况。

首先如果有只有 $1$ 个木块的颜色，那么这个木块一定要放在中间，如果这样的颜色 $>1$ 种，那么无解。

否则我们随便选一个有奇数个木块的颜色放到中间。

然后考虑剩余的偶数种出现奇数次的颜色的放置（因为剩下 $n-1$ 个位置而 $n-1$ 是偶数，所以是偶数种）。

所以我们考虑对颜色两两配对，记为颜色 $A,B$ ，从中心点往外扩展，每种颜色拿出 $3$ 个木块，分别在中心点左边/右边构造 $BAA$ 和 $BBA$ ，此时发现平均坐标正好是 $\frac{n+1}{2}$ ，然后每种颜色的出现次数变为偶数。

你把这种构造拓展一下，设一共有 $tot$ 对，

变成 $(\frac{n+1}{2}-i,\frac{n+1}{2}-(3tot-2i+1),\frac{n+1}{2}+(3tot-i+1))$ 和 $(\frac{n+1}{2}-(tot+2i),\frac{n+1}{2}+i,\frac{n+1}{2}+(tot+i))$。

我们发现这个构造恰好能填满 $[\frac{n+1}{2}-3tot,\frac{n+1}{2}-1]\cup [\frac{n+1}{2}+1,\frac{n+1}{2}+3tot]$。

剩下的构造回文串即可。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e6 + 10;

int n,K,tot=0,cnt1=0;
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int cnt[MAXN];

bool cmp(int p,int q){
	return cnt[p]<cnt[q];
}

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d%d",&n,&K),tot=cnt1=0;
		FL(i,1,K) cnt[i]=0;
		FL(i,1,n) scanf("%d",&d[i]),cnt[d[i]]++;
		FL(i,1,K)
			if(cnt[i]&1) tot++,cnt1+=(cnt[i]==1);
		if(!(n&1)){
			if(tot) puts("NO");
			else{
				puts("YES");
				FL(i,1,K)
					FL(j,1,cnt[i]/2) printf("%d ",i);
				FR(i,K,1)
					FL(j,1,cnt[i]/2) printf("%d ",i);
				puts("");
			}
		}
		else{
			if(cnt1>1) puts("NO");
			else if((tot&1)&&tot-1<=n/3){
				puts("YES");
				int id=-1;
				FL(i,1,K)
					if((cnt1&&cnt[i]==1)||(!cnt1&&(cnt[i]&1))){
						id=i;
						break;
					}
				cnt[id]--;
				tot=0;
				FL(i,1,K)
					if(cnt[i]&1) a[++tot]=i,cnt[i]-=3;
				tot/=2;
				FL(i,1,tot)
					b[i]=b[3*tot-2*i+1]=c[3*tot-i+1]=a[i];
				FL(i,1,tot)
					c[i]=c[tot+i]=b[tot+2*i]=a[i+tot];
				FL(i,1,K)
					FL(j,1,cnt[i]/2) printf("%d ",i);
				FR(i,3*tot,1) printf("%d ",b[i]);
				printf("%d ",id);
				FL(i,1,3*tot) printf("%d ",c[i]);
				FR(i,K,1)
					FL(j,1,cnt[i]/2) printf("%d ",i);
				puts("");
			}
			else puts("NO");
		}
	}
}

B

原题 QOJ10306

考虑一个子区间 $[l,r]$ ，我们假设最大权独立集选了位置集合 $P$ ，那么这个子区间不合法当且仅当 $[l,r]$ 中 $\Delta=\sum_{x\in P}a_x-\sum_{x\not\in P}a_x=0$ （也就是选了和没选的 $a$ 的和相等），显然最大权独立集的权值至少是区间和的一半（因为可以选所有奇数/偶数位置，而这些位置上的数和就是区间和），所以区间的 $\Delta\ge 0$ 。

对于一个固定区间，我们从左到右加入数字，我们需要维护两个值：

$v_0$ ：加入的最后一个数可选可不选时 $\Delta$ 的最大值。
$v_1$ ：强制最后一个数不选时 $\Delta$ 的最大值。

显然 $v_0\ge v_1$ ，现在我们加入数 $x$ ，如果选 $x$ 那么前面一个数一定不能选，最大是 $v_1+x$ ，如果不选 $x$ 那么最大是 $v_0-x$ 。

因此转移到的新状态是 $v_0'=\max(v_1+x,v_0-x),v_1'=v_0-x$ ，如果在某次加入后 $v_0'=0$ ，那么说明这个子区间不合法。

然后我们会观察到一个性质，当 $v_0+v_1>0$ 时，加入任何数 $x$ ， $v_0$ 之后都不可能变成 $0$ ：

若最大值取的 $v_1+x$ ，那么 $v_0'+v_1'=(v_1+x)+(v_0-x)=v_0+v_1>0$ 。
否则说明 $v_0-x\ge v_1+x$ ，那么 $v_0'=v_0-x\ge \frac{(v_0-x)+(v_1+x)}{2}>0$ 。

因此对于整个序列，我们只需要记录满足 $v_0+v_1=0$ 的后缀： $(v_0,v_1)=(p,-p)$ 。

考虑维护临界状态 $p$ 的集合 $S$ ，加入新数 $x$ ， $v_0'=\max(x-p,p-x),v_1'=p-x$ ，讨论 $x$ 和 $p$ 的大小关系：

$x=p$ ：那么 $v_0'=0$ ，说明整个序列不合法。
$x<p$ ，此时 $v_0'=v_1'=p-x$ ， $v_0'+v_1'>0$ ，这个后缀永远合法，可以丢掉。
$x>p$ ：此时 $v_0'=x-p,v_1'=p-x=-(x-p),v_0'+v_1'=0$ ，此时仍是临界状态： $p\to x-p$ 。

那么如果 $x\not\in S$ ，新的临界值集合就是 $S'=\{x\}\cup\{x-p|p\in S,x>p\}$ 。

因为 $x\le m$ ，所以 $S$ 中所有元素 $p\in [1,m]$ ，发现 $m\le 19$ ，可以状压。

令 $f_S$ 表示处理完前若干个位置后，当前临界值集合为 $S$ 的合法序列数量。

枚举 $i,S,x$ 转移， $S$ 在加入 $x$ 之后得到的 $S'$ 可以预处理，相当于清空 $p>x$ 的 $p$ 并对 $p<x$ 进行翻转，然后将 $p=x$ 设为 $1$ ，所以相当于将 $S+1$ 的后 $x$ 位翻转（ $+1$ 是因为合法的 $S$ 的第 $0$ 位一定是 $0$ ，将第 $0$ 位设为 $1$ 那么翻转后正好成为第 $x$ 位的 $1$ ），时间复杂度 $\mathcal{O}(nm2^m)$ 。

考虑优化，我们从大到小枚举 $x$ ，在计算完 $x$ 的答案后，对于第 $x$ 位等于 $1$ 的 $S$ （显然），我们将它的 $f$ 值累加到 $S\oplus 2^x$ （只用枚举 $[2^x,2^{x+1})$ ，因为第 $[x+1,m]$ 位等于 $1$ 的 $S$ 已经在前面累加了），于是对于每个 $x$ ，就只用枚举 $2^{x}$ ，因为第 $0$ 位恒为 $0$ 还带 $\frac12$ 的常数，是 $\frac{1}{2}\sum_{i=1}^m 2^i=\mathcal{O}(2^m)$ 量级的。

时间复杂度 $\mathcal{O}(n2^m)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 19 + 1;
const int MR = (1<<20) + 10;
const int mod = 998244353;

int n,m,U,ans=0;
int A[MAXN];
int R[MAXN][MR],f[MR],g[MR];

int main(){
	scanf("%d%d",&n,&m),U=(1<<m+1)-1;
	FL(i,1,m) FL(S,0,(1<<i)-1) R[i][S]=R[i-1][S/2]+(S&1)*(1<<i);
	f[0]=1;
	FL(i,1,n){
		FL(j,1,m) scanf("%d",&A[j]);
		int Mx=(1<<m);
		FR(j,m,1){
			if(A[j])
				for(int S=0;S<Mx;S+=2)
					g[R[j][S+1]]=(g[R[j][S+1]]+f[S])%mod;
			for(int S=Mx;S<(Mx<<1);S+=2) f[S^Mx]=(f[S^Mx]+f[S])%mod;
			Mx/=2;
		}
		for(int S=0;S<U;S+=2) f[S]=g[S],g[S]=0;
	}
	for(int S=0;S<U;S+=2) ans=(ans+f[S])%mod;
	printf("%d\n",ans);
}

4.30

A

我们发现对于两个区间，只有当存在包含关系时我们不需要使用 clear 操作而是使用更长的区间的 $len$ 次 add 操作。

所以我们想把序列划分为尽量少的嵌套链，使得链上每个区间都被下一个区间所包含。

于是我们把所有区间按照左端点 $l$ 升序排序，如果 $l$ 相同则按右端点 $r$ 升序排序。

于是对于 $A,B$ ， $A$ 在 $B$ 前面，则一定有 $l_A\le l_B$ ，此时我们只需要保证 $r_B\le r_A$ ，那么区间 $B$ 就一定被区间 $A$ 完全包含。

于是我们维护一个 set 表示所有链尾的区间的右端点以及链的编号。

然后对于当前区间 $[l,r]$ ，找 $\ge r$ 的最小右端点将其接上即可。

貌似期望的链数是 $\mathcal{O}(\sqrt{q})$ 的，所以期望 Add 次数是 $\mathcal{O}(q\sqrt{q})$ ，但是本地实测随机数据都在 $8\times 10^6$ 左右。

#include"ds.h"
#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXQ = 1e5 + 10;

int n,q;
int idx=0;
struct Dat{
	int l,r,id;
}e[MAXQ];

set<PII>st;
vector<int>E[MAXQ];

bool cmp(Dat p,Dat q){
	if(p.l!=q.l) return p.l<q.l;
	return p.r<q.r;
}

void solve(int N,int Q,vector<int> l,vector<int> r){
	n=N,q=Q,idx=0;
	for(int i=0;i<(int)l.size();i++) e[i+1]={l[i],r[i],i+1};
	sort(e+1,e+q+1,cmp);
	FL(i,1,q){
		int l=e[i].l,r=e[i].r,id=e[i].id;
		if(st.empty())
			E[++idx].push_back(i),st.insert({r,idx});
		else{
			auto it=st.lower_bound({r,-1});
			if(it!=st.end()){
				int cid=it->second;
				st.erase(it);
				E[cid].push_back(i);
				st.insert({r,cid});
			}
			else E[++idx].push_back(i),st.insert({r,idx});
		}
	} 
	FL(Id,1,idx){
		clear();
		int L,R;
		for(int i=(int)E[Id].size()-1;i>=0;i--){
			int ql=e[E[Id][i]].l,qr=e[E[Id][i]].r,qid=e[E[Id][i]].id;
			if(i==(int)E[Id].size()-1) FL(j,ql,qr) add(j);
			else{
				while(L>ql) L--,add(L);
				while(R<qr) R++,add(R);
			}
			L=ql,R=qr;
			report(qid);
		}
	}
}

B

发现 $d_{i,j}$ 相等的点 $a_{i,j}$ 相等，呈一圈圈扩散的趋势。

$$f_{i,j}=\min_{k<i,j\le l}\{f_{k,l}+Calc(k+1,i,j)\}$$

然后发现我们并不关心 $j,l$ 的值，因为对于距离 $\in[k+1,i]$ 的坐标，我们将它的 $a$ 值统一修改为距离 $\le i$ 的坐标中 $a$ 的最小值 $mn_i$ 一定是最优的，且满足条件。

于是有：

f_{i}=\min_{k<i}\{f_{k}+Calc(k+1,i,mn_i)\}

然后 $Calc(l,r,val)$ 是简单的，经典的最小割，我们对于每行/每列建点（注意距离 $<l$ 的点可能会把一行/一列割成两半，建两个点即可），然后对于每个距离 $\in [l,r]$ 的坐标 $(i,j)$ ，若 $a_{i,j}>val$ ，就让对应的行列连边，中间的边不能割，两边至少割一条，跑最大流即可。

因为最大流的最大值 $F=\mathcal{O}(n+m)$ ，边数 $E=\mathcal{O}(nm)$ ，所以 $n,m$ 同阶的话复杂度 $\mathcal{O}((n+m)nm)=\mathcal{O}(n^3)$ 。

状态枚举 $\mathcal{O}(n^2)$ ，计算代价是 $\mathcal{O}(n^3)$ 的，所以是 $\mathcal{O}(n^5)$ 的，获得 80pts：

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 160 + 5;
const int MAXM = 1e6 + 10;
const int inf=1e9;

int n,m,r,c,mxa=0,mxd=0;
int a[MAXN][MAXN],d[MAXN][MAXN],mn[MAXN<<1];
int f[MAXN<<1];

namespace Solve1{
	void solve(){
		bool fg=1;
		FL(i,1,c-1) fg&=(a[1][i]<=a[1][i+1]);
		FL(i,c,m-1) fg&=(a[1][i]>=a[1][i+1]);
		puts(fg?"0":"1");
	}
}

int S,T;
int head[MAXN<<3],now[MAXN<<3],cnt=1;
int dis[MAXN<<3];
struct node{
	int v,w,nxt;
}e[MAXM<<1];
void Add_edge(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

bool bfs(){
	FL(i,S,T) dis[i]=inf;
	queue<int>q;
	now[S]=head[S],dis[S]=0,q.push(S);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(w&&dis[v]==inf){
				now[v]=head[v],dis[v]=dis[u]+1,q.push(v);
				if(v==T) return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int flow){
	if(u==T) return flow;
	if(!flow) return 0;
	int res=0;
	for(int i=now[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		now[u]=i;
		if(w&&(dis[v]==dis[u]+1)){
			int tmp=dfs(v,min(flow,w));
			if(!tmp) dis[v]=inf;
			e[i].w-=tmp,e[i^1].w+=tmp;
			flow-=tmp,res+=tmp;
			if(!flow) break; 
		}
	}
	return res;
}
int dinic(){
	int res=0;
	while(bfs()) res+=dfs(S,inf);
	return res;
}

int Calc(int L,int R,int val){
	S=0,T=2*n+2*m+1,cnt=1;
	FL(i,S,T) head[i]=0;
	FL(i,1,n){
		Add_edge(S,i,1),Add_edge(i,S,0);
		if(abs(i-r)<L) Add_edge(S,i+n,1),Add_edge(i+n,S,0);
	}
	FL(j,1,m){
		Add_edge(2*n+j,T,1),Add_edge(T,2*n+j,0);
		if(abs(j-c)<L) Add_edge(2*n+m+j,T,1),Add_edge(T,2*n+m+j,0);
	}
	FL(i,1,n){
		FL(j,1,m){
			if(d[i][j]>=L&&d[i][j]<=R&&a[i][j]>val){
				int u=(abs(i-r)<L?(j<c?i:i+n):i);
				int v=(abs(j-c)<L?(i<r?2*n+j:2*n+m+j):2*n+j); 
				Add_edge(u,v,inf),Add_edge(v,u,0);
			}
		}
	}
	return dinic();
}

int main(){
	scanf("%d%d%d%d",&n,&m,&r,&c);
	memset(mn,0x3f,sizeof(mn));
	FL(i,1,n) FL(j,1,m) scanf("%d",&a[i][j]),d[i][j]=abs(r-i)+abs(c-j),mxa=max(mxa,a[i][j]),mxd=max(mxd,d[i][j]),mn[d[i][j]]=min(mn[d[i][j]],a[i][j]);
	FL(i,1,mxd) mn[i]=min(mn[i],mn[i-1]); 
	memset(f,0x3f,sizeof(f));
	f[0]=Calc(0,0,mn[0]);
	FL(i,1,mxd){
		f[i]=Calc(0,i,mn[i]); 
		FL(k,0,i-1)
			f[i]=min(f[i],f[k]+Calc(k+1,i,mn[i]));
	}
	printf("%d\n",f[mxd]);
	return 0;
}

然后我们会发现对于 $Calc(l,r,val)$ ，当 $l$ 固定 $r$ 增大时，增加的边数其实是很少的，我们可以预处理对于每个 $(i,j)$ ，最早可以被加入的 $r$ ，也就是 $\min\{r|a_{i,j}>mn_r\}$ ，此时如果 $l\le d_{i,j}\le r$ ，那我们加入这条边。

于是我们预处理 $Calc(l,r,val)$ ，具体地，我们枚举 $l$ 再从小到大枚举 $r$ ，加边，每次最多增广边数次，时间复杂度 $\mathcal{O}(n\cdot n^3)=\mathcal{O}(n^4)$ 。

然后再加一些常数优化，比如中间的边边权设为 $1$ 这样边权只剩 $0/1$ （割中间边相当于对单点做行列操作，合法但不会比最优解优），记录连接每对行列点的边是否加入过，不重复加入，然后还有就是不知道为啥 vector 跑得比链式前向星快。

时间复杂度 $\mathcal{O}(n^4)$ ，瓶颈在预处理。

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;

const int MAXN = 160 + 5;
const int MAXM = 1e6 + 10;
const int inf = 0x3f3f3f3f;

inline int read(){
    int x=0,f=1;
	char c=getchar();
    while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x*f;
}

int n,m,r,c,mxa=0,mxd=0;
int a[MAXN][MAXN],d[MAXN][MAXN],mn[MAXN<<1];
int f[MAXN<<1];
int Val[MAXN<<1][MAXN<<1];
vector<PII>V[MAXN<<1];

int S,T;
int now[MAXN<<3];
int dis[MAXN<<3];
int vis[MAXN][MAXN],idx=0;
int Q[MAXN<<3];

struct Edge{
    int v,w,rid;
};
vector<Edge>G[MAXN<<3];

void Add_edge(int u,int v,int w){
    G[u].push_back({v,w,(int)G[v].size()});
    G[v].push_back({u,0,(int)G[u].size()-1});
}

bool bfs(){
    FL(i,S,T) dis[i]=inf;
    int ql=1,qr=0;
    now[S]=0,dis[S]=0,Q[++qr]=S;
    while(ql<=qr){
        int u=Q[ql++];
        for(int i=0;i<(int)G[u].size();i++){
            int v=G[u][i].v,w=G[u][i].w;
            if(w&&dis[v]==inf){
                now[v]=0;
                dis[v]=dis[u]+1;
                Q[++qr]=v;
            }
        }
    }
    return dis[T]!=inf;
}

int dfs(int u,int flow){
    if(u==T) return flow;
    if(!flow) return 0;
    int res=0;
    for(int &i=now[u];i<(int)G[u].size();i++){
        int v=G[u][i].v,w=G[u][i].w;
        if(w&&(dis[v]==dis[u]+1)){
            int tmp=dfs(v,min(flow,w));
            if(!tmp) dis[v]=inf;
            G[u][i].w-=tmp,G[v][G[u][i].rid].w+=tmp;
            flow-=tmp,res+=tmp;
            if(!flow) break; 
        }
    }
    return res;
}

int dinic(){
    int res=0;
    while(bfs()) res+=dfs(S,inf);
    return res;
}

int main(){
	scanf("%d%d%d%d",&n,&m,&r,&c);
    memset(mn,0x3f,sizeof(mn));
    FL(i,1,n){
        FL(j,1,m){
            a[i][j]=read();
            d[i][j]=abs(i-r)+abs(j-c);
            mxa=max(mxa,a[i][j]);
            mxd=max(mxd,d[i][j]);
            mn[d[i][j]]=min(mn[d[i][j]],a[i][j]);
        }
    }
    FL(i,1,mxd) mn[i]=min(mn[i],mn[i-1]);
    FL(i,1,n) 
        FL(j,1,m)
            FL(R,d[i][j],mxd)
                if(a[i][j]>mn[R]){
                    V[R].push_back({i,j});
                    break;
                }
    FL(L,0,mxd){
        S=0,T=n*2+m*2+1;
        idx++;
        FL(i,S,T) G[i].clear();
        FL(i,1,n){
            Add_edge(S,i,1);
            if(abs(i-r)<L) Add_edge(S,i+n,1);
        }
        FL(j,1,m){
            Add_edge(n*2+j,T,1);
            if(abs(j-c)<L) Add_edge(n*2+m+j,T,1);
        }
        int mxf=0;
        FL(R,L,mxd){
            bool fg=0;
            for(auto p:V[R]){
                int i=p.first,j=p.second;
                if(d[i][j]>=L){
                    if(vis[i][j]!=idx){
                        vis[i][j]=idx;
                        int u=(abs(i-r)<L?(j<c?i:i+n):i);
                        int v=(abs(j-c)<L?(i<r?n*2+j:n*2+m+j):n*2+j);
                        Add_edge(u,v,1);
                        fg=1;
                    }
                }
            }
            if(fg) mxf+=dinic();
            Val[L][R]=mxf;
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0]=Val[0][0];
    FL(i,1,mxd){
        f[i]=Val[0][i];
        FL(k,0,i-1)
            f[i]=min(f[i],f[k]+Val[k+1][i]);
    }
    printf("%d\n",f[mxd]);
    return 0;
}

5.1

A

为了方便表述，下文令“加入”表示加入 $X$ 集合，“弹出”表示从 $X$ 集合中删除并加入 $Y$ 集合。

因为我们要求最终 $Y=S$ ，说明所有被 $-$ 弹出的数都要属于集合 $S$ 。

于是我们把数分为两类，我们称属于 $S$ 的数为目标元素，不属于 $S$ 的数为非目标元素。

考虑一个非目标元素 $v$ ，如果未来还要弹出某个目标元素 $a_j$ ，且 $v<a_j$ 。

那么如果 $v$ 在弹出 $a_j$ 前加入，那么方案非法，因为 $v$ 会先于 $a_j$ 被弹出，所以一个非目标元素能否加入只取决于当前还没有弹出的最大目标元素 $a_k$ ，只有满足 $v>a_k$ 的 $v$ 才能被加入。

我们发现我们只关心最大的未弹出的目标元素，以及已加入的目标元素的数量，于是考虑在 $+$ 加入时如果我们要加入目标元素那么将其视为占位符，并在之后钦定它的值，设计状态：

令 $f_{x,y,op}$ 表示最大的 $x$ 个目标元素已经确定被弹出，有 $y$ 个目标元素占位符未被钦定值（均被加入但不一定未被弹出）， $op=0/1$ 表示 $a_{m-x}$ 不在/在集合 $X$ 里面的方案数。

用 $cnt_1,cnt_2$ 记录已经遇到的 $-/+$ 数量。

若当前 $s_i=+$ ：

在当前 $+$ 之前有 $cnt_2-1$ 个 $+$ 。
若加入非目标元素，那么其要 $>a_{m-x}$ ，然后前面加入了 $(cnt_2-1)-(x+y)$ 个非目标元素，最大的 $x$ 个目标元素都已被弹出，显然这些数都 $>a_{m-x}$ ，所以有 $(n-a_{m-x})-((cnt_2-1)-(x+y)+x)=(n-a_m)-(cnt_2-1-y)$ 个可用的非目标元素。

$((n-a_{m-x})-(cnt_2-1-y))\cdot f_{x,y,0/1}\to g_{x,y,0/1}$。
若加入目标元素，那么 $y$ 增加 $1$ ，讨论它是否是 $a_{m-x}$ ：
- 若 $op=0$ ，那么可能是 $a_{m-x}$ 也可能不是： $f_{x,y,0}\to g_{x,y+1,0/1}$ 。
- 若 $op=1$ ，那么一定不是 $a_{m-x}$ ： $f_{x,y,1}\to g_{x,y+1,1}$ 。

若当前 $s_i=-$ ：

当前前缀中已经加入了 $x+y$ 个目标元素，已经弹出了 $cnt_1-1$ 个，所以当前 $X$ 中的目标元素个数 $t=(x+y)-(cnt_1-1)$ ，若 $t=0$ 那么状态非法。
若 $t=1$ ：
- 若 $op=0$ ，当前最大的未处理目标元素 $a_{m-x}$ 还没有加入，那么此时弹出的数依旧是更小的目标元素占位符， $f_{x,y,0}\to g_{x,y,0}$ 。
- 若 $op=1$ ，那么这次处理的是最大**目标元素 ** $a_{m-x}$ ，然后此时我们可以同时钦定若干个之前已经处理的更小目标元素占位符，假设处理了 $c$ 个，那我们要从 $y-1$ 个（因为用了 $1$ 个占位符钦定为 $a_{m-x}$ ）中选出 $c$ 个，$\binom{y-1}{c}\cdot c!\cdot f_{x,y,1}\to g_{x+1+c,y-1-c,0}$。
若 $t>1$ ：
- 若 $op=0$ ，当前最大的未处理目标元素 $a_{m-x}$ 还没有加入，一定不会弹出它。
- 若 $op=1$ ，那么加入了最大目标元素 $a_{m-x}$ ，但是一定有比它小的目标元素存在，也不会弹出它。
综上，状态不变， $f_{x,y,0/1}\to g_{x,y,0/1}$ 。

$+$ 的转移时间复杂度是 $\mathcal{O}(m^2)$ 的， $-$ 虽然会枚举 $c$ 但是只有在 $t=1$ 的时候才会枚举，所以瓶颈复杂度也是 $\mathcal{O}(m^2)$ 的。

时间复杂度 $\mathcal{O}(nm^2)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 5e2 + 10;
const int mod = 998244353;

int n,m;
int a[MAXN];
char s[MAXN<<1];
int fac[MAXN],inv[MAXN];
int f[MAXN][MAXN][2],g[MAXN][MAXN][2];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
} 

int C(int n,int m){
	if(n<m||n<0||m<0) return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main(){
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	FL(i,1,m) scanf("%d",&a[i]); 
	fac[0]=1;
	FL(i,1,MAXN-1) fac[i]=1ll*fac[i-1]*i%mod;
	inv[MAXN-1]=qpow(fac[MAXN-1],mod-2);
	FR(i,MAXN-2,0) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	f[0][0][0]=1;
	int cnt1=0,cnt2=0;
	FL(i,1,n+m){
		if(s[i]=='-'){
			cnt1++;
			FL(x,0,min(m,cnt2)) FL(y,0,cnt2-x) FL(op,0,1) g[x][y][op]=0;
			FL(x,0,min(m,cnt2)){
				FL(y,0,min(m,cnt2)-x){
					int t=(x+y)-(cnt1-1);
					if(t<1) continue;  
					if(t>1)
						g[x][y][0]=(g[x][y][0]+f[x][y][0])%mod,
						g[x][y][1]=(g[x][y][1]+f[x][y][1])%mod;
					else{
						g[x][y][0]=(g[x][y][0]+f[x][y][0])%mod;
						if(f[x][y][1])
							FL(c,0,y-1)
								if(x+1+c<=min(m,cnt2))
									g[x+1+c][y-1-c][0]=(g[x+1+c][y-1-c][0]+1ll*f[x][y][1]*fac[c]%mod*C(y-1,c)%mod)%mod;
					}
				}
			}
			FL(x,0,min(m,cnt2)) FL(y,0,min(m,cnt2)-x) FL(op,0,1) f[x][y][op]=g[x][y][op];
		}
		else{
			cnt2++;
			FL(x,0,min(m,cnt2)) FL(y,0,min(m,cnt2)-x) FL(op,0,1) g[x][y][op]=0;
			FL(x,0,min(m,cnt2-1)){
				FL(y,0,min(m,cnt2-1)-x){
					int t=(n-a[m-x])-(cnt2-1-y);
					if(t>0){
					    g[x][y][0]=(g[x][y][0]+1ll*f[x][y][0]*t%mod)%mod;
					    g[x][y][1]=(g[x][y][1]+1ll*f[x][y][1]*t%mod)%mod;
					}
					if(x+y+1<=min(m,cnt2))
						g[x][y+1][0]=(g[x][y+1][0]+f[x][y][0])%mod,
						g[x][y+1][1]=(g[x][y+1][1]+f[x][y][1])%mod,
						g[x][y+1][1]=(g[x][y+1][1]+f[x][y][0])%mod;
				}
			}
			FL(x,0,min(m,cnt2)) FL(y,0,min(m,cnt2)-x) FL(op,0,1) f[x][y][op]=g[x][y][op];
		}
	}
	printf("%d\n",f[m][0][0]);
}

5.2

A

首先考虑不修改时的答案。

我们定义 $mx_l=\min\{p|l<p\land a_p<a_l\}$ ，若不存在则令 $mx_l=n+1$ ，那么以 $l$ 为左端点的合法右端点区间为 $[l+1,mx_l-1]$ ，所以答案就是 $num=\sum_{l=0}^n(mx_l-l-1)$ 。

设修改位置为 $pos$ ，令 $ans_{pos}$ 为修改 $pos$ 后的答案，对于二元组 $(l,r)$ ：

若 $r<pos\lor pos\le l$ ，那么相对大小不变，答案不变。
否则讨论 $X$ 的正负：
- 若 $X\ge 0$ ，那么会有不合法的区间变得合法，我们定义 $dl_i$ 为 $pos=i$ 时答案的增加量。
  
  对于左端点 $l$ ，当 $l<pos\le mx_l$ 时会影响 $mx_l$ 的值。
  
  考虑二分找到最小的位置 $R$ 满足 $R\ge mx_l\land a_R+X<a_l$ ，答案增量就是 $R-mx_l$ 。
  
  对 $dl_{l+1}\sim dl_{mx_l}$ 加上增量。
- 若 $X<0$ ，那么会有合法的区间变得不合法。
  
  $(l,r)$ 合法当且仅当 $\forall k\in [pos,r],a_k+X\ge a_l\Rightarrow a_l\le \min_{k\in [pos,r]}a_k+X$。
  
  我们枚举 $pos$ ，统计所有 $l<pos\land mx_l\ge pos$ 的 $l$ 的个数 $siz_{pos}$ 以及 $mx_l$ 之和 $sum_{pos}$ ，于是可能变为不合法的二元组总量为 $sum_{pos}-pos\cdot siz_{pos}$ （ $\sum \Big((mx_l-1)-pos+1\Big)$ ）。
  
  接下来需要统计其中修改后仍然合法的区间，记 $dl_i$ 为 $pos=i$ 时仍合法的区间数量。
  
  我们令 $a_p$ 为区间 $[pos,r]$ 中位置最前的最小值。对于固定的 $p$ ，设 $q$ 是它左边最大满足 $a_q\le a_p$ 的位置，那么 $a_p$ 可以作为最前的最小值，修改位置 $pos$ 的范围为 $[q+1,p]$ 。
  
  记 $L=q+1$ ，把 $p$ 加入事件集合 $Q_L$ 。
  
  当处理到 $pos=L$ 时，用树状数组统计当前满足 $l<pos\land mx_l\ge pos$ 的 $l$ 中 $a_l\le a_p+X$ 的数量 $vcnt$ 。由于 $[L,p-1]$ 中所有 $a$ 都 $>a_p$ ，且 $X<0$ ，所以所有被 $vcnt$ 统计到的 $mx_l\ge pos$ 的 $l$ 一定满足 $mx_l\ge p$ ，所以 $vcnt$ 在所有 $pos\in[L,p]$ 中的贡献保持不变。
  
  对每个这样的左端点，右端点可以取 $p\sim mx_p-1$ ，数量为 $mx_p-p$ ，于是向 $dl_L\sim dl_p$ 加上 $(mx_p-p)\cdot vcnt$ 。
  
  最后 $ans_{pos}=num-(sum_{pos}-pos\cdot siz_{pos}-dl_{pos})$。

时间复杂度 $\mathcal{O}(n\log n)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 5e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n;
ll X,ans=0;
int lg[MAXN];
ll a[MAXN],d[MAXN];
ll mn[20][MAXN];

int st[MAXN],top=0;
int mx[MAXN];
ll dl[MAXN],num=0;

int b[MAXN<<1],cnt=0;
ll sum[MAXN],Smx=0;
int siz[MAXN];
vector<int>Q[MAXN];

ll Get(int l,int r){
	int k=lg[r-l+1];
	return min(mn[k][l],mn[k][r-(1<<k)+1]);
}

int find(int p,ll val){
	if(p>n) return n+1;
	int t=p;
	FR(j,19,0)
		if(t+(1<<j)-1<=n&&mn[j][t]>=val) t+=(1<<j);
	return t;
}

struct BIT{
	#define lowbit(x) (x&(-x))
	int c[MAXN<<1];
	void update(int x,int k){
		while(x<=cnt){
			c[x]+=k;
			x+=lowbit(x);
		}
	}
	int query(int x){
		int res=0;
		while(x){
			res+=c[x];
			x-=lowbit(x);
		}
		return res;
	}
}T;

int main(){
	scanf("%lld%d",&X,&n);
	a[0]=0;
	FL(i,1,n) scanf("%lld",&d[i]),a[i]=a[i-1]+d[i];
	lg[0]=-1;
	FL(i,1,n) lg[i]=lg[i>>1]+1;
	FL(i,0,n) mn[0][i]=a[i];
	FL(j,1,19)
		FL(i,0,n-(1<<j)+1)
			mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<j-1)]);
	top=0;
	FL(i,0,n){
		mx[i]=n+1;
		while(top&&a[st[top]]>a[i]) mx[st[top]]=i,top--;
		st[++top]=i;
	}
	FL(i,0,n) num+=(mx[i]-i-1);
	if(X>=0){
		FL(l,0,n){
			int R=find(mx[l],a[l]-X);
			if(R>mx[l]&&mx[l]>=l+1){
				dl[l+1]+=(R-mx[l]);
				if(mx[l]+1<=n+1) dl[mx[l]+1]-=(R-mx[l]);
			}
		}
		FL(i,2,n) dl[i]+=dl[i-1];
		FL(i,1,n) ans=max(ans,num+dl[i]);
		printf("%lld\n",ans);
		exit(0);
	}
	if(X<0){
		FL(i,0,n) b[++cnt]=a[i];
		FL(i,1,n) b[++cnt]=a[i]+X;
		sort(b+1,b+cnt+1);
		cnt=unique(b+1,b+cnt+1)-b-1;
		top=0;
		FL(i,1,n){
			while(top&&a[st[top]]>a[i]) top--;
			int L=(top?st[top]:0)+1;
			if(L<=i) Q[L].push_back(i);
			st[++top]=i;
		}
		top=0;
		FL(i,1,n){
			while(top&&a[st[top]]>a[i-1]){
				int ps=lower_bound(b+1,b+cnt+1,a[st[top]])-b;
				Smx-=mx[st[top]];
				T.update(ps,-1);
				top--;
			}
			st[++top]=i-1;
			int ps=lower_bound(b+1,b+cnt+1,a[i-1])-b;
			Smx+=mx[i-1];
			T.update(ps,1);
			sum[i]=Smx,siz[i]=top;
			for(int p:Q[i]){
				int ps=lower_bound(b+1,b+cnt+1,a[p]+X)-b;
				ll vcnt=T.query(ps);
				dl[i]+=1ll*(mx[p]-p)*vcnt;
				if(p+1<=n+1) dl[p+1]-=1ll*(mx[p]-p)*vcnt;
			}
		}
		FL(i,1,n) dl[i]+=dl[i-1];
		FL(i,1,n)
			ans=max(ans,num-(sum[i]-1ll*i*siz[i]-dl[i]));
		printf("%lld\n",ans);
		exit(0);
	}
}

B

我们称在集合 $S$ 中的节点为关键点，要求根到每个叶子的路径都满足恰好经过 $k$ 个关键点，且关键点权值按路径顺序单调不增。

我们考虑朴素树形 dp，令 $f_{u,i,j}$ 表示在 $u$ 子树内给每个节点赋值并选点，满足 $u$ 到每个叶子的路径上恰好选 $i$ 个点，且所有关键点权值 $\le j$ 的方案数。

我们令 $g_{u,i,j}=\prod_{v\in son(u)}f_{v,i,j}$ ，考虑 $u$ 是否选入集合：

如果不选 $u$ ，那么 $x_u$ 不影响 $j$ 的值，可以随便填，贡献为 $(R_u-L_u+1)\cdot g_{u,i,j}$ 。
否则令 $x_u=y\in [L_u,R_u]$ ，贡献为 $\sum_{y=L_u}^{\min(R_u,j)}g_{u,i-1,y}$ 。

因此 $f_{u,i,j}$ 的转移式子是：

$$f_{u,i,j}=(R_u-L_u+1)\cdot g_{u,i,j}+\sum_{y=L_u}^{\min(R_u,j)}g_{u,i-1,y}$$

时间复杂度 $\mathcal{O}(nkV^2)$ ，可以前缀和优化到 $\mathcal{O}(nkV)$ ，其中 $V=10^9$ 。

发现 $j$ 的取值范围是 $10^9$ 的，直接枚举显然不可行，所以考虑离散化，把 $L_i,R_i+1$ 放进离散化数组里得到 $tot$ 个不同的数，中间有 $tot-1$ 段。

发现同一段中的数，和各个节点的取值范围的包含关系不变。

考虑对每段分别处理，设当前在处理第 $X$ 段，也就是 $[b_X,b_{X+1})$ ，发现 $f$ 是关于 $p=j-b_X$ 是一个次数不超过 $n$ 的多项式 $F(p)$ （这个可以从叶子开始推，每个点的选择方案是带 $p$ 的式子，显然乘起来是多项式），于是我们求出其在 $p=0\sim n+1$ 的点值然后用拉格朗日插值还原多项式并求出整段的答案。

具体地，我们固定 $X$ ，维护 $F_{u,i}(p)=f_{u,i,b_X+p}(p\in [0,n+1])$ ，定义 $his_{u,i}$ 表示在处理当前段 $X$ 之前，所有已经处理过且属于 $u$ 的权值范围的 $y$ 的 $g_{u,i,y}$ 的和。

对于节点 $u$ ：

如果 $x_u$ 的取值范围覆盖这一段，那么对于上界 $j=b_X+p$ ，选 $u$ 的贡献就是 $S_{u,i}(p)=his_{u,i}+\sum_{q=0}^pg_{u,i,b_X+q}$ 。
否则选 $u$ 的贡献只有以前贡献和 $his_{u,i}$ 。

转移后，我们需要把这段的新值加入 $his_{u,i}$ ：

我们已经得到 $p=0\sim n+1$ 时 $S$ 的值，用拉格朗日插值可以求出 $S$ ，然后带入 $p=b_{X+1}-b_X-1$ ，此时多项式等于 $S_{u,i}(p)=his_{u,i}+\sum_{q=0}^{b_{X+1}-b_X-1}g_{u,i,b_X+q}$，此时对应的 $j=b_{X+1}-1$ ，正好是我们想求的 $his_{u,i}$ 的新值。

然后最后用同样的方法还原答案，即令 $X=tot-1$ ，求 $F_{1,k}(b_{tot}-b_{tot-1}-1)=f_{1,k,b_{tot}-1}$ 的值，此时对应的 $j=b_{tot}-1$ ，也就是还没有选择任何点且没有任何取值限制时的答案。

时间复杂度 $\mathcal{O}(n^3K)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e2 + 10;
const int MAXK = 20 + 5;
const int mod = 1004535809;

int n,K,X;
int L[MAXN],R[MAXN],sum[MAXN];
int f[MAXN][MAXK][MAXN],g[MAXK][MAXN];
int his[MAXN][MAXK];
vector<int>G[MAXN];
int b[MAXN<<1],tot=0;

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

int suf[MAXN],pre[MAXN],exc[MAXN];

void init(){
	FL(i,0,n+1){
		int Mul=1;
		FL(j,0,n+1)
			if(j!=i) Mul=1ll*Mul*(i-j+mod)%mod;
		exc[i]=qpow(Mul,mod-2);
	}
}

int Get(int *f,int ps){
	int R=b[ps+1]-b[ps]-1;
	suf[n+1]=(R-(n+1)+mod)%mod;
	FR(i,n,0) suf[i]=1ll*suf[i+1]*(R-i+mod)%mod;
	pre[0]=R;
	FL(i,1,n+1) pre[i]=1ll*pre[i-1]*(R-i+mod)%mod;
	int Mul=1,res=0;
	FL(i,0,n+1){
		res=(res+1ll*f[i]*exc[i]%mod*(i?pre[i-1]:1)%mod*(i+1<=n+1?suf[i+1]:1)%mod)%mod;
		Mul=1ll*Mul*(R-i+mod)%mod; 
	}
	return res;
}

void dfs1(int u,int fth){
	for(int v:G[u]){
		if(v==fth) continue;
		dfs1(v,u),sum[u]++;
	}
}
void dfs2(int u,int fth){
	for(int v:G[u]){
		if(v==fth) continue;
		dfs2(v,u);	
	}
	FL(j,0,K) FL(k,0,n+1) g[j][k]=(!sum[u]&&j?0:1);
	for(int v:G[u]){
		if(v==fth) continue;
		FL(j,0,K) FL(k,0,n+1) g[j][k]=1ll*g[j][k]*f[v][j][k]%mod;
	}
	int len=b[R[u]+1]-b[L[u]];
	FL(j,0,K) FL(k,0,n+1) f[u][j][k]=1ll*len*g[j][k]%mod;
	FL(j,0,K-1){
		int prv=his[u][j];
		if(L[u]<=X&&X<=R[u]){
			int sum=prv;
			FL(k,0,n+1){
				sum=(sum+g[j][k])%mod;
				f[u][j+1][k]=(f[u][j+1][k]+sum)%mod,g[j][k]=sum;
			}
			his[u][j]=Get(g[j],X);
		}
		else FL(k,0,n+1) f[u][j+1][k]=(f[u][j+1][k]+prv)%mod;
	}
}

int main(){
	scanf("%d%d",&n,&K);
	FL(i,1,n) scanf("%d",&L[i]);
	FL(i,1,n) scanf("%d",&R[i]);
	FL(i,1,n-1){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	FL(i,1,n) b[++tot]=L[i],b[++tot]=R[i]+1;
	sort(b+1,b+tot+1);
	tot=unique(b+1,b+tot+1)-b-1;
	FL(i,1,n)
		L[i]=lower_bound(b+1,b+tot+1,L[i])-b,
		R[i]=lower_bound(b+1,b+tot+1,R[i]+1)-b-1;
	init();
	dfs1(1,0); 
	FL(i,1,tot-1) X=i,dfs2(1,0);
	printf("%d\n",Get(f[1][K],tot-1));
}

C

原题 CF1874G

我们发现被 $\times 10^9$ 的卡牌是特殊的，因此我们考虑枚举这张牌，称为特殊牌，假设我在 $p$ 点获得这张牌，那么路径被分为两段， $1\to p$ 和 $p\to n$ ，显然在 $p\to n$ 中，所有加生命值的事件都应该加到这张卡牌上，因为最少的贡献也有 $10^9$ ，显然最优。

我们可以预处理 $p\to n$ 的贡献，

令 $g_{u,x}=(d,val)$ 表示从 $u\to n$ 的某条路径上，给特殊牌分配的生命值增量总和为 $x$ 时能获得的最大伤害增量为 $d$ ，在伤害增量最大时，普通牌贡献加额外贡献最大为 $val$ 。

我们反向 dp，当前我们已知 $u\to n$ 的答案，尝试更新它的前驱 $v$ ，假设我们要计算 $g_{v,x}$ ：

$op_v=0$ ：直接转移，没有新贡献。
$op_v =1$ ：因为我们已经选定特殊牌，所以只能是普通牌，普通牌的贡献增加 $a_v\times b_v$ 。
$op_v=2$ ：生命值增加 $a_v$ ，一定给特殊牌，从 $g_{u,\max(x-a_v,0)}$ 转移。
$op_v=3$ ：伤害增加 $a_v$ ，一定给特殊牌，最大伤害增量增加 $a_v$ 。
$op_v=4$ ：额外贡献增加 $a_v$ 。

然后考虑处理 $1\to p$ 的路径。

我们发现如果我们知道了每张牌的最终生命值，那么路径上每次加伤害操作，都应该加在已经拿到的最终生命值最大的卡牌上。

于是我们考虑钦定当前最大的最终生命值，同时记录我们提前预支的生命值，设计 dp 状态：

令 $f_{u,x,y}$ 表示从 $1\to u$ ，当前拿到的所有牌的最终生命值最大值为 $x$ ，有 $y$ 点生命增量是提前预支的且还未被补上，此时的最大普通收益。

考虑转移：

$op_v=0$ ：直接转移，没有贡献。
$op_v =1$ ：

可以选择不给其任何生命增量，那么贡献固定为 $a_v\times b_v$ ， $f_{u,x,y}$ 转移到 $f_{v,\max(x,a_v),y}$ 。

也可以选择把它补到 $t$ ，但是我们必须要 $y=0$ 的时候才可以转移，因为当 $y\not=0$ 时，我们在之后还需要偿还前面的预支，如果 $t$ 成为之后的最大生命值，全部补给 $v$ 一定是最优的，所以从 $y=0$ 转移严格不劣于 $y\not=0$ 。
$op_v=2$ ：生命值增加 $a_v$ ，我们选择这次操作用于偿还预支的生命值，差值 $y\to \max(0,y-a_v)$ 。
$op_v=3$ ：伤害增加 $a_v$ ，一定给当前最终生命值最大的牌，新增贡献 $x\cdot a_v$ 。
$op_v=4$ ：额外贡献增加 $a_v$ 。

此时我们发现 $x$ 的取值范围是 $\mathcal{O}(nV)$ 的，但是我们发现对于 $1\to p$ ，所有牌的最终生命值最大值 $\le V$ ，或所有牌的最终伤害最大值 $\le V$ ，两者至少成立一个。

（具体地，如果在 $1\to p$ 存在某张牌最终生命值 $>V$ ，又存在某张牌最终伤害 $>V$ ，那么可以推出存在一张牌同时满足生命值 $>V$ ,伤害 $>V$ ，此时选择这张牌为特殊牌一定比 $p$ 优。）

若最大伤害出现在最大生命后面那么符合条件，否则交换这两维能得到同样的结果，于是 $x$ 的取值范围 $\mathcal{O}(V)$ ，跑两遍 dp，一次正常跑，一次交换生命值和伤害跑， $x$ 始终记录 $\le V$ 的维度。

最后是枚举 $p$ 合并答案，注意 $f$ 和 $g$ 都包含了 $p$ 作为普通牌的贡献 $a_p\times b_p$ ，注意减去。

最后如果路径上没有 $op=1$ 的点，那么只有额外贡献，我们特殊处理这种情况，令 $dis_u$ 表示 $1\to u$ 只有额外贡献时的最大贡献， $dis_v=\max_{(u,v)\in E}\{dis_u\}+[op_v=4]a_v$ 。

时间复杂度 $\mathcal{O}(mnV+mV^2+n^2V)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,ll>
using namespace std;
const int MAXN = 2e2 + 10;
const int V = 2e2;
const int inf = 1e9;

int n,m;
ll ans=0;
int op[MAXN],a[MAXN],b[MAXN];
vector<int>G[MAXN],E[MAXN];
ll f[2][MAXN][MAXN][MAXN];
PII g[MAXN][MAXN*MAXN];
ll dis[MAXN];

void init(){
	g[n][0]={0,0};
	FR(u,n,1){
		for(int v:E[u]){
			if(op[v]==0)
				FL(x,0,n*V) g[v][x]=max(g[v][x],g[u][x]);
			else if(op[v]==1)
				FL(x,0,n*V) g[v][x]=max(g[v][x],{g[u][x].first,g[u][x].second+a[v]*b[v]});
			else if(op[v]==2)
				FL(x,0,n*V) g[v][x]=max(g[v][x],g[u][max(x-a[v],0)]);
			else if(op[v]==3)
				FL(x,0,n*V) g[v][x]=max(g[v][x],{g[u][x].first+a[v],g[u][x].second});
			else if(op[v]==4)
				FL(x,0,n*V) g[v][x]=max(g[v][x],{g[u][x].first,g[u][x].second+a[v]});
		}
	}
}

void solve(ll f[MAXN][MAXN][MAXN]){
	f[1][0][0]=0;
	FL(u,1,n){
		for(int v:G[u]){
			if(op[v]==0)
				FL(x,0,V)
					FL(y,0,x)
						f[v][x][y]=max(f[v][x][y],f[u][x][y]);
			else if(op[v]==1)
				FL(x,0,V){
					FL(y,0,x)
						f[v][max(x,a[v])][y]=max(f[v][max(x,a[v])][y],f[u][x][y]+a[v]*b[v]);
					FL(t,a[v],V)
						f[v][max(x,t)][t-a[v]]=max(f[v][max(x,t)][t-a[v]],f[u][x][0]+t*b[v]);
				}
			else if(op[v]==2)
				FL(x,0,V)
					FL(y,0,x)
						f[v][x][max(0,y-a[v])]=max(f[v][x][max(0,y-a[v])],f[u][x][y]);
			else if(op[v]==3)
				FL(x,0,V)
					FL(y,0,x)
						f[v][x][y]=max(f[v][x][y],f[u][x][y]+x*a[v]);
			else if(op[v]==4)
				FL(x,0,V)
					FL(y,0,x)
						f[v][x][y]=max(f[v][x][y],f[u][x][y]+a[v]); 
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	FL(i,1,n){
		scanf("%d",&op[i]);
		if(op[i]==1) scanf("%d%d",&a[i],&b[i]);
		else if(op[i]==2||op[i]==3||op[i]==4) scanf("%d",&a[i]);
	}
	FL(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		E[v].push_back(u);
	}
	memset(f,-0x3f,sizeof(f));
	memset(g,-0x3f,sizeof(g));
	init();
	solve(f[0]);
	FL(i,1,n){
		if(op[i]==1) swap(a[i],b[i]);
		else if(op[i]==2||op[i]==3) op[i]^=1;
	}
	solve(f[1]);
	FL(i,1,n){
		if(op[i]==1) swap(a[i],b[i]);
		else if(op[i]==2||op[i]==3) op[i]^=1;
	}
	FL(u,1,n){
		if(op[u]==1){
			ll mx=0;
			FL(i,0,n*V)
				if(g[u][i].first>=0)
					mx=max(mx,1ll*(a[u]+i)*(b[u]+g[u][i].first)*inf+g[u][i].second-a[u]*b[u]);
			FL(x,0,V) ans=max(ans,max(f[0][u][x][0],f[1][u][x][0])-a[u]*b[u]+mx);
		}
	}
	memset(dis,-0x3f,sizeof(dis));
	dis[1]=0;
	FL(u,1,n)
		for(int v:G[u])
			dis[v]=max(dis[v],dis[u]+(op[v]==4?a[v]:0));
	ans=max(ans,dis[n]);
	printf("%lld\n",ans);
}

省集笔记（4.26~5.2）

4.26

A

B

C

4.27

A

B

C

4.28

A

B

C

4.29

A

B

4.30

A

B

5.1

A

5.2

A

B

C

Status

Development

Support

About

省集笔记（4.26~5.2）

4.26

A

B

C

4.27

A

B

C

4.28

A

B

C

4.29

A

B

4.30

A

B

5.1

A

5.2

A

B

C

Status

Development

Support

About

SIGN IN