模拟赛

这里的题解在出题人的基础上进行补充。

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$
  • 转移要注意状态的严谨性，以及举几个例子来验证。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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$，而最值和区间都是分治的常见套路。

原题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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 是什么就可以了。

整个过程可以用可持久化线段树从下往上做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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;
}