模拟赛
这里的题解在出题人的基础上进行补充。
T1
首先忽略所有全开的子树（在这样的子树内我们不应该选择任何路径），选一个关的点作为根
设 $f_{u,0/1,0/1/2}$ 表示满足条件
- $u$ 最后是关/开的，子树内其它点最后都是开的
- 子树内有 0/1/2 个路径端点，其它端点为 $u$
的最小路径长度
设加入 $u$ 的前若干个儿子后的结果为 $tmp_{0/1,0/1/2}$，需要加入儿子 $v$，转移的规则为：
- 关于端点个数这一维是个背包
- 路径拼接时，可能会多走一次某个点。具体地，当 $v$ 子树内的端点数为 $0/1/2$ 时，分别会多走 $u$，$\emptyset$，$v$
- 在考虑上一条多走的情况下，如果 $v$ 最后被关闭了，那么还需要在中间走一个 $u-v$ 补一下。
考场上，除了看出来是个 DP，其它都没有看出来。
- 注意树上路径 dp 可以采用记录端点个数。但是要小心处理单个点的情况。
- 注意如果方便的话优先处理掉没有用的部分，因为它们可能对答案造成干扰。
- 注意 dp 初值取 $\min$ 或 $\max$ 的时候考虑 $\inf$ 和 $-\inf$
- 转移要注意状态的严谨性，以及举几个例子来验证。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 500010
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n,f[N][2][3];
char s[N];
vi e[N];
bool vis[N];
inline void pre(int k,int fa){
vis[k]=s[k]-'0';
for(int to:e[k]) if(to!=fa){
pre(to,k);vis[k]&=vis[to];
}
}
inline void dfs(int u,int fa){
int tmp[2][3];mset(tmp,0);
int op=(s[u]=='1');rep(i,0,2) f[u][op^1][i]=tmp[op^1][i]=1;
rep(i,0,2) f[u][op][i]=tmp[op][i]=INF;
for(int to:e[u]) if(to!=fa&&!vis[to]){
dfs(to,u);mset(f[u],INF);
rep(i,0,1)rep(j,0,2)rep(k,0,1)rep(o,0,j){
cmin(f[u][i][j],f[to][k][o]+tmp[i^k^(o&1)][j-o]+2*(k^1^(o==2))+((o&1)^1));
}
rep(i,0,1)rep(j,0,2)tmp[i][j]=f[u][i][j];
}
// rep(i,0,1)rep(j,0,2)printf("f[%d][%d][%d]=%d\n",u,i,j,f[u][i][j]);
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);scanf("%s",s+1);
rep(i,1,n-1){
int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
}
int rt=-1;rep(i,1,n) if(s[i]=='0') rt=i;pre(rt,0);dfs(rt,0);
printf("%lld\n",min(f[rt][1][2],min(f[rt][1][0],f[rt][1][1])));
return 0;
}
T2
一段区间的权值为 $len\times \min{a}\times \min{b}$，求最大的权值
分治，计算出所有三元组（到中点的距离，到中点的 $\min{a}$，到中点的 $\min{b}$），考虑合并。首先考虑两个 $\min$ 都在同一边取到的情况，此时另一边只需要让长度尽量大即可，容易单调扫描出另一边的合法区间。不在同一边的情况，同样可以单调扫描出另一边的合法区间，不妨设 $\min{a}$ 在左边取到，那么两个三元组会产生贡献 $(L+R)\cdot ma_l\cdot mb_r$，其中 $(L+R)\cdot mb_r$ 相当于一次函数最值，可以通过线段树维护凸包的方式快速计算。直接计算是三个 $\log$ ，但是注意 $L$ 是单调的，所以线段树上每个凸包的最优解都是单调移动的，这样就可以去掉一个 $\log$
如何用线段树维护凸包？只需要在每个线段树的节点开一个栈，保存这个线段树节点所代表的区间中的所有点的凸包即可。然后本来是要在上面二分的，但是因为具有单调性，可以用指针扫。
如何想到分治，只需要考虑答案是 $len\times ma\times mb$，而最值和区间都是分治的常见套路。
struct Point{
ll x,y;
inline Point(){}
inline Point(ll x,ll y) : x(x),y(y) {}
inline ll operator ^ (const Point &b)const{return x*b.y-y*b.x;}
inline Point operator - (const Point &b)const{return Point(x-b.x,y-b.y);}
inline bool operator < (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}c[N];
struct Node{
vc<Point> v,sta;
int id,top;
inline void GetSta(){
top=0;
for(Point x:v){
while(top&&((x-sta[top])^(sta[top-1]-sta[top]))>=0) top--;
sta[++top]=x;
}
id=top;
}
inline int Ask(int k){
Point now(1,k);
while(id&&((sta[id]-sta[id-1])^(now))>=0) id--;
return sta[id].y-sta[id].x*k;
}
}p[N<<2];
#define ls(k) k<<1
#define rs(k) k<<1|1
struct SegmentTree{
inline void Build(int k,int l,int r){
p[k].v.clear();
p[k].v.resize(r-l+1);p[k].sta.resize(r-l+2);int mid=(l+r)>>1;
if(l==r){p[k].v[0]=c[l];p[k].GetSta();return;}
// exit(0);
Build(ls(k),l,mid);Build(rs(k),mid+1,r);
merge(p[ls(k)].v.begin(),p[ls(k)].v.end(),p[rs(k)].v.begin(),p[rs(k)].v.end(),p[k].v.begin());
// exit(0);
p[k].GetSta();
}
inline ll Ask(int k,int l,int r,int z,int y,int x){
if(z<=l&&r<=y) return p[k].Ask(x);int mid=(l+r)>>1;
ll ans=0;
if(z<=mid) ans=max(ans,Ask(ls(k),l,mid,z,y,x));
if(mid<y) ans=max(ans,Ask(rs(k),mid+1,r,z,y,x));return ans;
}
}st;
int n,a[N],b[N],B[N];
ll Ans;
inline void Solve(int l,int r){
int mid=(l+r)>>1;
int ma=INF,mb=INF,R=mid-1;
dec(i,l,mid){
cmin(ma,a[i]);cmin(mb,b[i]);
while(R+1<=r&&a[R+1]>=ma&&b[R+1]>=mb) R++;
cmax(Ans,ma*mb*(R-i+1));
}
B[mid]=b[mid];rep(i,mid+1,r) B[i]=min(B[i-1],b[i]);
rep(i,mid,r) c[i-mid+1].x=-B[i],c[i-mid+1].y=B[i]*(i-mid);
// exit(0);
st.Build(1,1,r-mid+1);
// exit(0);
R=mid-1;ma=INF;mb=INF;
int L=mid;
// exit(0);
dec(i,l,mid){
cmin(ma,a[i]);cmin(mb,b[i]);
while(L<=r&&b[L]>mb) L++;if(L>r) break;
while(R+1<=r&&a[R+1]>=ma) R++;
if(L>R) continue;
Ans=max(Ans,ma*st.Ask(1,1,r-mid+1,L-mid+1,R-mid+1,mid-i+1));
}
}
inline void Divi(int l,int r){
if(l>r) return;int mid=(l+r)>>1;
Solve(l,r);reverse(a+l,a+r+1);reverse(b+l,b+r+1);
Solve(l,r);reverse(a+l,a+r+1);reverse(b+l,b+r+1);
Divi(l,mid-1);Divi(mid+1,r);
}
signed main(){
// freopen("my.in","r",stdin);
read(n);rep(i,1,n) read(a[i]),read(b[i]);
Divi(1,n);
printf("%lld\n",Ans);
return 0;
}
T3
考虑大部分点的 lca 都是在分叉点上，除非在一条链上，我们考虑只保留分叉点和其儿子之间的连边，其余都缩成一个点，首先点数是 $O(n)$ 的，而且我们只需要知道每个点缩点之后是哪个点，新树上两个点的 lca 是什么就可以了。
整个过程可以用可持久化线段树从下往上做。
int n,q,t,a[N],b[N],mod,c[N<<2];
struct Node{
int siz,val,ls,rs;
inline Node(){}
inline Node(int siz,int val) : siz(siz),val(val) {}
}p[N*40];
int rt[N],fa[N<<2][21],dep[N<<2],ans;
vi e[N<<2];
#define ls(k) p[k].ls
#define rs(k) p[k].rs
struct SegmentTree{
int tot;
inline SegmentTree(){tot=0;}
inline void PushUp(int k){p[k].siz=p[ls(k)].siz+p[rs(k)].siz;}
inline void Change(int &k,int last,int l,int r,int w,int x1,int x2){
k=++tot;p[k]=p[last];int mid=(l+r)>>1;
if(l==r){p[k].siz=x1;p[k].val=x2;return;}
if(w<=mid) Change(ls(k),ls(last),l,mid,w,x1,x2);
else Change(rs(k),rs(last),mid+1,r,w,x1,x2);PushUp(k);
}
inline P Ask(int k,int l,int r,int siz){
if(l==r) return mp(l,p[k].val);int mid=(l+r)>>1;
if(siz<=p[ls(k)].siz) return Ask(ls(k),l,mid,siz);
else return Ask(rs(k),mid+1,r,siz-p[ls(k)].siz);
}
inline void Build(int &k,int l,int r){
k=++tot;int mid=(l+r)>>1;if(l==r){p[k].siz=1;p[k].val=l;return;}
Build(ls(k),l,mid);Build(rs(k),mid+1,r);PushUp(k);
}
}st;
inline void dfs(int k,int fat){
fa[k][0]=fat;rep(i,1,20) fa[k][i]=fa[fa[k][i-1]][i-1];dep[k]=dep[fat]+1;
for(int to:e[k]) if(to!=fat) dfs(to,k);
}
inline int Lca(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
dec(i,0,20) if(dep[fa[a][i]]>=dep[b]) a=fa[a][i];if(a==b) return a;
dec(i,0,20) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i];return fa[a][0];
}
inline int getid(int x){
return lower_bound(b+1,b+n+2,x)-b;
}
inline int ID(int x){
int id=lower_bound(b+1,b+n+2,x)-b-1;
return x-(1+id)*id/2;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(q);read(t);mod=(n+1)*(n+2)/2;
rep(i,1,n) read(a[i]);int tot=n+1;st.Build(rt[n+1],1,n+1);
rep(i,1,n+1) b[i]=(1+i)*i/2;
dec(i,1,n){
// printf("ID(a[i])=%d\n",ID(a[i]));
P now=st.Ask(rt[i+1],1,n+1,ID(a[i]));
P now2=st.Ask(rt[i+1],1,n+1,ID(a[i])+1);
// printf("now.fi=%d now.se=%d now2.fi=%d now2.se=%d\n",now.fi,now.se,now2.fi,now2.se);
st.Change(rt[i],rt[i+1],1,n+1,now2.fi,0,-1);
++tot;st.Change(rt[i],rt[i],1,n+1,now.fi,1,tot);
e[tot].pb(now.se);e[tot].pb(now2.se);
// printf("Add %lld %lld\n",tot,now.se);printf("Add %lld %lld\n",tot,now2.se);
}
dfs(tot,0);
rep(i,1,n) c[st.Ask(rt[getid(a[i])],1,n+1,ID(a[i])).se]=a[i];
rep(i,1,q){
int x,y;read(x);read(y);
x=(x-1+t*ans)%mod+1;y=(y-1+t*ans)%mod+1;
// printf("getid(x)=%d ID(x)=%d x=%d\n",getid(x),ID(x),x);
P now=st.Ask(rt[getid(x)],1,n+1,ID(x));
// printf("getid(y)=%d ID(y)=%d y=%d\n",getid(y),ID(y),y);
P now2=st.Ask(rt[getid(y)],1,n+1,ID(y));
// printf("now.se=%d now2.se=%d\n",now.se,now2.se);
int l=Lca(now.se,now2.se);
if(now.se==now2.se){
if(x<y) swap(x,y);printf("%lld\n",(ans=y));
}
else if(l==now.se||l==now2.se){
if(l==now.se) printf("%lld\n",(ans=x));
else printf("%lld\n",(ans=y));
}
else{
// puts("here");printf("l=%d\n",l);
printf("%lld\n",(ans=c[l]));
}
}
return 0;
}