Day 2

A.sequence

题目描述：

题目分析：

考虑一个很简单的 \(dp\) 就是设 \(f[i]\) 表示考虑了前 \(i\) 个位置最多可以划分为多少个序列。
转移就是可以直接从 \(f[i-1]\) 继承，或者从 \(j\) 满足 \(\sum_{k=j+1}^{i} c_i = 0\)，也就是前缀和相等。
可以发现的是对于从 \(j\) 转移这种方式我们没有必要从所有符合条件的 \(j\) 转移，只需要找一个距离 \(i\) 最近的 \(j\) 即可，证明显然。
所以对于一组询问我们可以直接跑一遍就好了，对于多组询问的话肯定需要把 \(dp\) 搞成 \(dp\) 自动机的形式，即将 \(dp\) 的转移理解为边，\(dp\) 的状态理解为点，这样比较方便观察性质。
但是这样我们会发现我们直接弄的话转移边同时包含取 \(\max\) 和加 \(1\) 操作就很不行，那么考虑这个 \(dp\) 转移本质是什么：选择一个最近的点 \(j\) 使得 \([j,i]\) 存在一个子区间的区间和为 \(0\)，然后就直接转移 \(f[j]+1 \to f[i]\)。
这样弄完了我们自动机的转移边就只包含加 \(1\) 操作就很可做了。
稍微总结一下就是设 \(nxt_i = j\) 表示最小的 \(j\) 使得 \([i,j]\) 存在子区间区间和为 \(0\)，则连边 \((i,nxt_i+1)\)，答案即从 \(l\) 出发向上跳跳到第一个大于 \(r\) 的点的跳跃次数。
因为这个题卡空间，所以直接倍增的话空间就炸了，所以改成树剖加速跳跃的过程就好了。

代码：

（我写挂了，就随便扒一个看上去不错的放在这里了）

点击查看代码

bool M1;
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
//#include<ext/pb_ds/priority_queue.hpp>
#define fi first
#define se second
#define LD double
#define name(x) #x
#define ll long long
#define Vector Point
#define I128 __int128
#define ull unsigned ll
#define pii pair<int,int>
#define pb(x) push_back(x)
#define dek(x) debug(x)<<" "
#define deh(x) debug(x)<<endl
#define syt cerr<<"sytakioi\n"
#define debug(x) cout<<name(x)<<":"<<x
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define rd_i(l,r) uniform_int_distribution<int>(l,r)(rd)
#define rd_r(l,r) uniform_real_distribution<double>(l,r)(rd)
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n'
using namespace std;
//using namespace __gnu_cxx;
mt19937 rd(time(0));
const int N=4e5+5;
int n,m;
ll a[N];
struct edge{int to,next;}e[N];
int link[N],tot;
inline void add(int x,int y){e[++tot]={y,link[x]};link[x]=tot;}
unordered_map<ll,int> id;
int fa[N],dep[N],dfn[N],rk[N],top[N],cnt;
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void dfs(int u,int fath){
	dfn[u]=1;
	fa[u]=fath;
	dep[u]=dep[fath]+1;
	for(int i=link[u];i;i=e[i].next){
		int v=e[i].to;
		dfs(v,u);
		dfn[u]+=dfn[v];
		if(dfn[v]>dfn[top[u]]) top[u]=v;
	}
}
inline void dfs1(int u,int topf){
	int s=top[u];
	dfn[u]=++cnt;
	rk[cnt]=u;
	top[u]=topf;
	if(s) dfs1(s,topf);
	for(int i=link[u];i;i=e[i].next){
		int v=e[i].to;
		if(v!=s) dfs1(v,v);
	}
}
inline int ask(int x,int y){
	int res=0;
	while(fa[top[x]]<=y) res+=dep[x]-dep[top[x]]+1,x=fa[top[x]];
	int l=dfn[top[x]],r=dfn[x],ans=r+1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(rk[mid]<=y) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return res+dfn[x]-ans+1;
}
inline int query(int l,int r){return a[l]<=r?ask(a[l],r):0;}
bool M2;
int main(){
	int Time=clock();
	look_memory;
	cin.tie(nullptr)->sync_with_stdio(false);
//	freopen("sequence.in","r",stdin);
//	freopen("1.out","w",stdout);
//	freopen("sequence.out","w",stdout);
	cin>>n;
	id[0]=0;
	iota(fa,fa+n+2,0);
	F(i,1,n){
		cin>>a[i];
		a[i]+=a[i-1];
		if(id.count(a[i])) dep[i]=id[a[i]]+1;
		else dep[i]=-1;
		if(~dep[i]) add(dep[i],i);
		else fa[i]=i+1;
		id[a[i]]=i;
	}
	F(i,1,n+1){
		a[i]=find(1);
		for(int j=link[i];j;j=e[j].next) fa[e[j].to]=e[j].to+1;
	}
	tot=0;memset(link,0,sizeof link);
	F(i,1,n) if(dep[i]) add(a[i+1],i);
	dep[n+1]=0;
	dfs(n+1,n+1);dfs1(n+1,n+1);
	cin>>m;
	F(i,1,m){
		int l,r;cin>>l>>r;
		cout<<query(l,r)<<'\n';
	}
	look_time;
	return 0;
}

B.select

题目描述：

题目分析：

可以发现，我们一定可以找到一个点 \(r\) 作为根，使得 \(u,v,w\) 分别位于三棵子树内，所以就考虑枚举 \(r\)。
那么 \(u,v,w\) 一定是某三棵子树内深度最深的叶子节点，设分别为 \(a,b,c(a \le b \le c)\)
那么可以发现 \(f(u,v) = c \times(a + b)\)
证明可以考虑：\(c \times (a + b) = ac + bc = (ac +bc + ab) - ab\)
括号内的项随 \(a,b,c\) 的重排不变，所以就要求 \(ab\) 最小即可。
这样的话第一问就解决了，对于第二问来说就是沿用这种方式。
换根得到子树内最深的叶子和个数，然后分讨 \(dep_u=dep_v\) 和 \(dep_v = dep_w\) 即可。