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\) 即可。
考场上只会第一问，就给出一种更好想的解决第一问的方式：
我们可以发现的是我们一定存在一种最优方案使得直径的两个端点就是我们选择的三个点之一，因为如果不是的话，我们将某一个点改为直径的端点一定不会变劣。
这样就确定了两个点，对于第三个点我们直接枚举就好了。