NOI 2024 题解

rgw2010 Lv1
  2024-08-28 2024-08-28 创建   2024-09-13 18:30:02 2024-09-13 18:30:02 更新      

NOI 2024 题解，by @rgw2010

思路：

容易发现，区间 中 与 等价的充分必要条为：

  • 两个序列中所有元素对于在区间 内的出现集合组成的集合相等。

  • 这样才可以使得存在一种对应的映射方案使得等价。

考虑哈希判定。

设 表示 出现的位置的集合，则设 ，。

固定左端点 时，容易发现 具有单调性，考虑求出 表示以 为左端点的最长等价区间，使用双指针算法；

设当前加入的数为 ，则重新计算下 即可，删除同理。

因为当前是单哈希，且基本都是加法哈希，可以双哈希 稳固一下。

时间复杂度为 。

完整代码：

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=2e5+10,M=6e5+10;
const ull base=127;
inline ll read(){
    ll 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<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
mt19937_64 R(time(0));
ull h1,h2;
int n,m,q,p,l,r;
int len[N],a[N][3],b[N][3];
ull f[N],s1[M],s2[M];
inline ull Hash(ull x){
	return x*f[x%(N-1)+1];	
}
inline void insert1(int x,int id){
	h1-=Hash(s1[x]);
	s1[x]+=f[id];
	h1+=Hash(s1[x]);
}
inline void insert2(int x,int id){
	h2-=Hash(s2[x]);
	s2[x]+=f[id];
	h2+=Hash(s2[x]);
}
inline void del1(int x,int id){
	h1-=Hash(s1[x]);
	s1[x]-=f[id];
	h1+=Hash(s1[x]);
}
inline void del2(int x,int id){
	h2-=Hash(s2[x]);
	s2[x]-=f[id];
	h2+=Hash(s2[x]);
}
inline void insert(int x){
	For(i,0,2){
		insert1(a[x][i],x);
		insert2(b[x][i],x);
	}
}
inline void del(int x){
	For(i,0,2){
		del1(a[x][i],x);
		del2(b[x][i],x);
	}
}
bool End;
int main(){
	//open("A.in","A.out");
	n=read(),m=read(),q=read();
	f[0]=1;	
	For(i,1,N-1)
	  f[i]=f[i-1]*base;
	For(i,1,n)
	  For(j,0,2)
	    a[i][j]=read();
	For(i,1,n)
	  For(j,0,2)
	    b[i][j]=read();
	for(int l=1,r=0;l<=n;){
		while(r<l){
			++r;
			insert(r);
		}
		while(r<=n&&h1==h2){
			r++;
			insert(r);
		}
		del(r--);
		len[l]=r;
		del(l++);
	}
	while(q--){
		l=read(),r=read();
		if(r>len[l])
		  puts("No");
		else
		  puts("Yes");
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

思路：

先考虑 Sub1 的部分分，暴力算法：

暴力询问所有 的数对 。
则一个 为最大值当且仅当 的返回值都是 且在 之前没有满足此条件的位置。

则设 表示暴力找出 个数中的最大值需要的询问次数，注意到 ，故可以通过 Sub1。

对于 Sub2，直接暴力肯定是不行的，但是注意到 的值开大了，故我们没必要一步到位，可以逐步缩小范围。

定义 表示原先最大值候选有 个，经过一次请求筛到 个候选人的最小询问次数；考虑分为 组，每组有 人，故：

现在我们的目的就是找到一个合理的筛检最大值候选的序列 ，使得长度 且 。

爆搜经过实测可以搜到 的情况，在 时几乎无法跑出来。

考虑动态规划算法，令 表示 的情况下的最小询问数，则状态转移方程为：

时间复杂度为 ，大概有 ，按照最低预算，计算机 1s 可以跑 ，则 ，则 ，大概要跑 天的时间，是肯定不行的。

可以有一个猜想，每次候选人的数量至少要减半，这样一定不会太劣，这样我们就将范围个缩小了，对于 有效的 只有 ，枚举的 大概是 ，这样大概可以缩到 左右，可以在 1h 内跑完。

其实也可以在确定前面几位为 的情况下对后面跑 ，这样时间更会大大减少。

最后根据我们得到的 模拟一下分组求最大值的过程即可。

单组数据时间复杂度最多为 。

完整代码：

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int maxn=1e6+10;
std::vector<int> ask(std::vector<int> a, std::vector<int> b);
int n;
vector<int> a,b,h;
namespace Sub1{
    int cnt=0;
    int work(){
    	a.clear(),b.clear();
    	cnt=0;
        vector<int> l(n,0),r(n,0);
        For(i,0,n-1){
            l[i]=cnt;
            For(j,i+1,n-1){
                a.push_back(i);
                b.push_back(j);
                ++cnt;
            }
            r[i]=cnt-1;
        }
        h=ask(a,b);
        For(i,0,n-1){
            bool F=1;
            For(j,l[i],r[i]){
                if(h[j]!=i){
                    F=0;
                    break;
                }
            }
            if(F)
              return i;
        }
        return 0;
    }
};
namespace Sub2{
	int cnt=0;
	int s[maxn];
	vector<int> E[maxn];
	stack<int> S;
	int p[]={1000000,500000,250000,125000,62498,20832,3472,183,1};
	void solve(int x){
		s[x]=a.size();
		int n=E[x].size();
        For(i,0,n-1){
            For(j,i+1,n-1){
                a.push_back(E[x][i]);
                b.push_back(E[x][j]);
            }
        }
	}
	int get(int x){
		int g=s[x],n=E[x].size();
		For(i,0,n-1){
			bool F=1;
			For(j,i+1,n-1)
			  if(h[g++]!=E[x][i])
				F=0;
			if(F)
			  return E[x][i];
		}
		return 0;
	}
	void get(int X,int Y){
		cnt=0;
		int l=0,cnt=0,g=0,B=X/Y;
		For(i,1,Y)
		  E[i].clear();
		while(!S.empty()){
			++l;
			int x=S.top();
			S.pop();
			if((l-1)/B+1!=cnt)
			  ++cnt;
			if(cnt<=Y)
			  E[cnt].push_back(x);
			else{
				++g;
				E[g].push_back(x);
			}
		}
		For(i,1,Y)
		  solve(i);
		h=ask(a,b);
		For(i,1,Y){
			int x=get(i);
			S.push(x);
		}
	}
	int work(){
		while(!S.empty())
		  S.pop();
    	_For(i,0,n-1)
    	  S.push(i);
		For(i,1,8){
			a.clear(),b.clear();
			get(p[i-1],p[i]);
		}
		return S.top();
	}
};
int richest(int N,int T,int S){
    n=N;
    if(n<=1000)
      return Sub1::work();
    else
      return Sub2::work();
}

待补。

待补。

思路：

我们可以对于每个 找到它能跳到的最远的点和最近的点，倍增求一下 级祖先即可，令 新表示 能跳到其祖先中深度在 内的点；同时令 表示 至少要跳到 的深度。

考虑动态规划算法，令 表示从 出发到山顶的合法登山序列个数。

那么相当于先从 滑落到 ，然后再从 冲刺到 ，再加上 的方案数。

则状态转移方程为：

在子树内为的祖先

其中 表示 路径上 的最小值，因为每次冲刺到达的深度必须小于所有经过的点的 。

朴素实现是 的，考虑优化；注意到 是 的祖先中一段深度连续的点，则我们可以做一个深度的 的前缀和，差分即可，时间复杂度优化至 ，可以得到 25pts。

Code： 
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
namespace Sub1{
    ll L,R,x,a,b;
    ll s[N],dp[N],dep[N];
    void dfs1(ll u){
        for(auto v:E[u]){
            if(v==fa[u])
              continue;
            dep[v]=dep[u]+1;
            dfs1(v);
        }
    }
    ll get(ll l,ll r){
        if(!l)
          return s[r];
        return (s[r]-s[l-1]+mod)%mod;
    }
    void dfs3(ll u,ll Min,ll from){
        L=l[u],R=min(r[u],Min);
        if(L<=R)
          dp[from]=(dp[from]+get(L,R))%mod;
        for(auto v:E[u]){
            if(v==fa[u])
              continue;
            dfs3(v,min(Min,h[v]),from);
        }
    }
    void dfs2(ll u){
        if(dep[u])
          s[dep[u]]=(s[dep[u]-1]+dp[u])%mod;
        else
          s[dep[u]]=dp[u];
        for(auto v:E[u]){
            if(v==fa[u])
              continue;
            dfs3(v,h[v],v);
            dfs2(v);
        }
    }
    void solve(){
        Read();
        dfs1(1);
        dp[1]=1;
        For(i,2,n){
            dp[i]=0;
            x=i;
            h[i]=dep[i]-h[i]-1;
            while(r[i]){
                x=fa[x];
                l[i]--,r[i]--;
                if(!l[i])
                  b=x;
                if(!r[i])
                  a=x;  
            }
            l[i]=dep[a],r[i]=dep[b];
        }
        dfs2(1);
        For(i,2,n){
            write(dp[i]);
            putchar(' ');
        }
        putchar('\n');
    }
    void work(){
        while(T--)
          solve();
    }
};

设 表示 的 级祖先，

现在考虑 的特殊性质，注意到对于 子树内的点 ，它最多只会对 造成 的贡献，注意到当 时是没有贡献的。

则我们考虑枚举 ，且注意到随着 的深度的变小 也会变小，考虑求出 表示深度最小的使得 的点，直接倍增求即可。

那么对于 路径上的 点，是可以由 下滑到 后冲刺到 的，那么对于 路径上的 的值都会增加 。

按照 的深度从小到大依次处理即可。

需要维护路径加，单点查，可以直接树剖与树状数组或线段树，时间复杂度为 ，这样我们就拿到了 45pts。

Code： 
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
class Tree{
public:
    ll cnt=0;
    ll p[N],t[N],z[N],d[N],fa[N];
    struct Node{
        ll l,r;
        ll data;
        ll tag;
    }X[N<<2];
	void dfs1(ll u,ll f){
		p[u]=1;
		for(auto v:E[u]){
			if(v==f)
			  continue;
			d[v]=d[u]+1;
			fa[v]=u;
			dfs1(v,u);
			p[u]+=p[v];
			if(p[v]>p[z[u]])
			  z[u]=v;
		}
	}
	void dfs2(ll u,ll k){
        dfn[u]=++cnt;
		t[u]=k;
		if(!z[u])
		  return ;
		dfs2(z[u],k);
		for(auto v:E[u]){
			if(v==fa[u]||v==z[u])
			  continue;
			dfs2(v,v);
		}
	}
    void build(ll k,ll l,ll r){
        X[k].l=l,X[k].r=r;
        X[k].data=X[k].tag=0;
        if(l==r)
          return ;
        ll mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
    }
    void add(ll k,ll v){
        X[k].data=Add(X[k].data,v);
        X[k].tag=Add(X[k].tag,v);
    }
    void push_down(ll k){
        if(X[k].tag){
            add(k<<1,X[k].tag);
            add(k<<1|1,X[k].tag);
            X[k].tag=0;
        }
    }
    void update(ll k,ll l,ll r,ll v){
        if(X[k].l==l&&r==X[k].r){
            add(k,v);
            return ;
        }
        push_down(k);
        ll mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          update(k<<1,l,r,v);
        else if(l>mid)
          update(k<<1|1,l,r,v);
        else{
            update(k<<1,l,mid,v);
            update(k<<1|1,mid+1,r,v);
        }
    }
    ll query(ll k,ll i){
        if(X[k].l==i&&i==X[k].r)
          return X[k].data;
        push_down(k);
        ll mid=(X[k].l+X[k].r)>>1;
        if(i<=mid)
          return query(k<<1,i);
        else
          return query(k<<1|1,i);
    }
    void update(ll u,ll v,ll h){
        while(t[u]!=t[v]){
            if(d[t[u]]<d[t[v]])
              swap(u,v);
            update(1,dfn[t[u]],dfn[u],h);
            u=fa[t[u]];
        }
        if(d[u]>d[v])
          swap(u,v);
        update(1,dfn[u],dfn[v],h);
    }
	void init(){
        For(i,1,n)
          z[i]=0;
        cnt=0;
		dfs1(1,1);
		dfs2(1,1);
        build(1,1,n);
	}
}Tr;
namespace Sub2{
    ll x,cnt;
    ll g[N],dep[N],Fa[N][M],F[N][M];
    vector<pi> G[N];
    void dfs1(ll u){
        For(j,1,M-1)
          Fa[u][j]=Fa[Fa[u][j-1]][j-1];
        for(auto v:E[u]){
            if(v==fa[u])
              continue;
            dep[v]=dep[u]+1;
            Fa[v][0]=u;
            dfs1(v);
        }
    }
    ll get_fa(ll u,ll k){
        if(!k)
          return u;
        _For(j,0,M-1){
            if(k>=(1ll<<j)){
                k-=(1ll<<j);
                u=Fa[u][j];
            }
        }
        return u;
    }
    void dfs2(ll u){
        For(j,1,M-1)
          F[u][j]=min(F[u][j-1],F[Fa[u][j-1]][j-1]);
        for(auto v:E[u]){
            if(v==fa[u])
              continue;
            F[v][0]=h[v];
            dfs2(v);
        }
    }
    void solve(){
        cnt=0;
        Read();
        Tr.init();
        For(j,0,M-1)
          Fa[1][j]=1;
        dfs1(1);
        For(i,0,n-1)
          G[i].clear();
        For(i,2,n){
            x=get_fa(i,l[i]);
            l[i]=r[i]=dep[x];
            h[i]=dep[i]-h[i]-1;
            G[l[i]].push_back({i,x});
        }
        For(j,0,M-1)
          F[1][j]=INF;
        dfs2(1);
        For(i,2,n){
            x=i;
            _For(j,0,M-1)
              if(r[i]<=F[x][j])
                x=Fa[x][j];
            g[i]=dep[x]+1;
            if(g[i]<=dep[i])
              g[i]=get_fa(i,dep[i]-g[i]);
            else
              g[i]=-1;
        }
        Tr.update(1,1,1);
        For(i,0,n-1){
            if(G[i].empty())
              continue;
            for(auto t:G[i]){
                ll v=t.fi;
                if(g[v]==-1)
                  continue;
                Tr.update(v,g[v],Tr.query(1,dfn[t.se]));
            }
        }
        For(i,2,n){
            write(Tr.query(1,dfn[i]));
            putchar(' ');
        }
        putchar('\n');
    }
    void work(){
        while(T--)
          solve();
    }
};

现在考虑根据 的思路，求 的情况。

还是一样，枚举 ，则对于一个 会增加 的贡献，其中 在 的祖先链上，表示深度为 的点的 值。

考虑分开计算，发现对于 的部分，就是 的情况，倍增求出深度最小的点 使得 ，然后对于 路径上的点都增加 的贡献。

现在是如何处理 的部分，注意到肯定还是先取一段 ，同样枚举 ，倍增找到深度最小的满足 （注意是 ） 的 ，则对于 路径上的 值，都要增加 。

然后考虑处理 的情况，考虑枚举 ，使得 是 的严格后缀最小值（即最小值中深度最深的那个点），注意到我们只需要求出 子树内有多少个 满足 的路径中没有小于等于 的 ，且 。

只要求出了这样的 的个数 ，则可以倍增求出深度最小的 使得 ，那么直接对于 的路径上的点，都会增加 的贡献。

注意到这样操作会有先后顺序的问题，考虑再求出 时，才考虑 和 和 的贡献。

该部分暴力 Code： 
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
namespace Sub3{
	ll Min,sum,x,a,b,c,t;
	ll dep[N],dp[N],g1[N],g2[N],g3[N];
	ll Fa[N][M];
	vector<pi> E1[N],E2[N],E3[N];
    void dfs(ll u){
        For(j,1,M-1)
          Fa[u][j]=Fa[Fa[u][j-1]][j-1];
        for(auto v:E[u]){
            if(v==fa[u])
              continue;
            Fa[v][0]=u;
            dep[v]=dep[u]+1;
            dfs(v);
        }
    }
    ll get_fa(ll u,ll k){
        if(!k)
          return u;
        _For(j,0,M-1){
            if(k>=(1ll<<j)){
                k-=(1ll<<j);
                u=Fa[u][j];
            }
        }
        return u;
    }
    ll get_sum(ll u){
    	ll ans=0;
    	while(u){
    		ans=Add(ans,dp[u]);
    		u=fa[u];
		}
		return ans;
	}
	void dfs2(ll u,ll k){
		if(h[u]<=h[k]&&u!=k)
		  return ;
		if(l[u]<=h[k]&&h[k]<=r[u])
		  sum++;
		for(auto v:E[u]){
			if(v==fa[u])
			  continue;
			dfs2(v,k); 
		}
	}
	void solve(){
		Read();
		dfs(1);
		dp[1]=1;
		For(i,0,n-1){
			E1[i].clear();
			E2[i].clear();
			E3[i].clear();
		}
        For(i,2,n){
            dp[i]=0;
            x=i;
            t=h[i]+1;
            h[i]=dep[i]-h[i]-1;
            while(l[i]>=1||r[i]>=1||t>=1){
                x=fa[x];
                l[i]--,r[i]--,t--;
                if(!l[i])
                  b=x;
                if(!r[i])
                  a=x;  
                if(!t)
                  c=x;
            }
            l[i]=dep[a],r[i]=dep[b];
            if(l[i])
              E1[l[i]-1].push_back({i,fa[a]});
            E2[r[i]].push_back({i,b});
            E3[h[i]].push_back({i,c});
        }
        //cerr<<'\n';
        For(i,2,n){
        	if(l[i]){
	        	Min=INF;
	        	x=i,a=-1;
	        	while(fa[x]!=1){
	        		Min=min(Min,h[x]);
	        		if(Min<l[i])
	        		  break;
	        		a=x;
	        		x=fa[x];
				}
				g1[i]=a;        		
			}
			else
			  g1[i]=-1;
			
			Min=INF;
			x=i,a=-1;
			while(fa[x]!=1){
				Min=min(Min,h[x]);
				if(Min<=r[i])
				  break;
				a=x;
				x=fa[x];
			}
			g2[i]=a;
			
			x=i;
			while(fa[x]!=1){
				if(h[fa[x]]<h[i])
				  break;
				x=fa[x];
			}
			g3[i]=x;
			
			//cerr<<i<<':'<<g1[i]<<','<<g2[i]<<','<<g3[i]<<'\n';
		}
		//cerr<<'\n';
		For(i,0,n-1){
			for(auto t:E1[i]){
				x=t.fi,a=get_sum(t.se),b=g1[x];
				if(b==-1)
				  continue;
				//cerr<<"("<<x<<"->"<<b<<")-"<<a<<'\n';
				while(x!=fa[b]){
					dp[x]=(dp[x]-a+mod)%mod;
					x=fa[x];
				}
			}
			for(auto t:E2[i]){
				x=t.fi,a=get_sum(t.se),b=g2[x];
				if(b==-1)
				  continue;
				//cerr<<"("<<x<<"->"<<b<<")+"<<a<<'\n';
				while(x!=fa[b]){
					dp[x]=Add(dp[x],a);
					x=fa[x];
				}
			}
			for(auto t:E3[i]){
				x=t.fi,a=get_sum(t.se),b=g3[x];
				if(b==-1)
				  continue;
				sum=0;
				dfs2(x,x);
				//cerr<<"("<<x<<"->"<<b<<")+"<<sum<<'*'<<a<<'\n';
				while(x!=fa[b]){
					dp[x]=(dp[x]+sum*a%mod)%mod;
					x=fa[x];
				}
			}
		}
		For(i,2,n){
			write(dp[i]);
			putchar(' ');
		}
		putchar('\n');
	}
	void work(){
		while(T--)
		  solve();
	}
};

这样的话操作都是一些基本操作，链加，链查，倍增优化等，唯一需要注意的是查询 ** 子树内有多少个 满足 的路径中没有小于等于 的 ，且 **。

考虑对于 找到 的路径上第一个满足 的 ，那么令 。

根据这个 ，建出边为 的新树，那么上述询问就变为了在求新树中 子树内的点 满足 的个数，证明显然，不再阐述。

那么可以每次将 范围内的 增加 ，那么满足条件的数的数量就是 。

考虑对于新树求出 dfn 序，则 子树内的点可以算作一段区间 ，然后建出前缀主席树即可快速求 被区间包含的个数（因为要区间加，可以直接标记永久化）。

也可以使用 dsu on tree 做，但是本人太菜不会。

总时间复杂度为 。

注意主席树的空间要开 倍。

完整代码；

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=1e5+10,M=20,mod=998244353,INF=1e9;
inline ll read(){
    ll 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<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
int T,n;
int root[N],fa[N],l[N],r[N],h[N],id[N],_id[N],dfn[N];
vector<int> E[N],G[N];
inline void add(int u,int v){
    E[u].push_back(v);
    E[v].push_back(u);
}
inline void ADD(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
inline void Read(){
    n=read();
    For(i,1,n){
    	E[i].clear();
    	G[i].clear();
	}
    For(i,2,n){
        fa[i]=read(),l[i]=read(),r[i]=read(),h[i]=read();
        add(fa[i],i);
    }
}
class Tree{
public:
    int cnt=0;
    int p[N],t[N],z[N],d[N],fa[N];
    struct Node{
        int l,r,len;
        ll data;
        ll tag;
    }X[N<<2];
	inline void dfs1(int u,int f){
		p[u]=1;
		for(auto v:E[u]){
			if(v==f)
			  continue;
			d[v]=d[u]+1;
			fa[v]=u;
			dfs1(v,u);
			p[u]+=p[v];
			if(p[v]>p[z[u]])
			  z[u]=v;
		}
	}
	inline void dfs2(int u,int k){
        dfn[u]=++cnt;
		t[u]=k;
		if(!z[u])
		  return ;
		dfs2(z[u],k);
		for(auto v:E[u]){
			if(v==fa[u]||v==z[u])
			  continue;
			dfs2(v,v);
		}
	}
    inline void build(int k,int l,int r){
        X[k].len=r-l+1;
		X[k].l=l,X[k].r=r;
        X[k].data=X[k].tag=0;
        if(l==r)
          return ;
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
    }
    inline void pushup(int k){
    	X[k].data=Add(X[k<<1].data,X[k<<1|1].data);
	}
    inline void add(int k,int v){
        X[k].data=(X[k].data+1ll*X[k].len*v%mod)%mod;
        X[k].tag=Add(X[k].tag,v);
    }
    inline void push_down(int k){
        if(X[k].tag){
            add(k<<1,X[k].tag);
            add(k<<1|1,X[k].tag);
            X[k].tag=0;
        }
    }
    inline void update(int k,int l,int r,int v){
        if(X[k].l==l&&r==X[k].r){
            add(k,v);
            return ;
        }
        push_down(k);
        int mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          update(k<<1,l,r,v);
        else if(l>mid)
          update(k<<1|1,l,r,v);
        else{
            update(k<<1,l,mid,v);
            update(k<<1|1,mid+1,r,v);
        }
        pushup(k);
    }
    inline int query(int k,int l,int r){
    	if(X[k].l==l&&r==X[k].r)
    	  return X[k].data;
    	push_down(k);
    	ll mid=(X[k].l+X[k].r)>>1;
    	if(r<=mid)
    	  return query(k<<1,l,r);
    	else if(l>mid)
    	  return query(k<<1|1,l,r);
    	else
    	  return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%mod;
	}
    inline int query(int k,int i){
        if(X[k].l==i&&i==X[k].r)
          return X[k].data;
        push_down(k);
        ll mid=(X[k].l+X[k].r)>>1;
        if(i<=mid)
          return query(k<<1,i);
        else
          return query(k<<1|1,i);
    }
    inline void update(int u,int v,int h){
        while(t[u]!=t[v]){
            if(d[t[u]]<d[t[v]])
              swap(u,v);
            update(1,dfn[t[u]],dfn[u],h);
            u=fa[t[u]];
        }
        if(d[u]>d[v])
          swap(u,v);
        update(1,dfn[u],dfn[v],h);
    }
    inline int ask(int u,int v){
    	int ans=0;
    	while(t[u]!=t[v]){
    		if(d[t[u]]<d[t[v]])
    		  swap(u,v);
    		ans=(ans+query(1,dfn[t[u]],dfn[u]))%mod;
    		u=fa[t[u]];
		}
		if(d[u]>d[v])
		  swap(u,v);
		ans=(ans+query(1,dfn[u],dfn[v]))%mod;
		return ans;
	}
	inline void init(){
        For(i,1,n)
          z[i]=0;
        cnt=0;
		dfs1(1,1);
		dfs2(1,1);
        build(1,1,n);
	}
}Tr;
namespace Seg{
	int siz[N];
	int cnt,s;
	struct Node{
		int L,R;
		int tag;
	}X[N*50];
	inline void dfs(int u,int fa){
		id[u]=++s;
		_id[s]=u;
		siz[u]=1;
		for(auto v:G[u]){
			if(v==fa)
			  continue;
			dfs(v,u);
			siz[u]+=siz[v];
		}
	}
	inline void tidy(){
		For(i,1,cnt)
		  X[i]={0,0,0};
		s=cnt=0;
		dfs(1,1);
	}
	inline void build(int &k,int l,int r){
		if(!k)
		  k=++cnt;
		X[k].tag=0;
		if(l==r)
		  return ;
		int mid=(l+r)>>1;
		build(X[k].L,l,mid);
		build(X[k].R,mid+1,r);
	}
	inline void update(int &k,int l,int r,int L,int R,int v){
		X[++cnt]=X[k];
		k=cnt;
		if(l==L&&r==R){
			X[k].tag=Add(X[k].tag,v);
			return ;
		}
		ll mid=(l+r)>>1;
		if(R<=mid)
		  update(X[k].L,l,mid,L,R,v);
		else if(L>mid)
		  update(X[k].R,mid+1,r,L,R,v);
		else{
			update(X[k].L,l,mid,L,mid,v);
			update(X[k].R,mid+1,r,mid+1,R,v);
		}
	}	
	inline void Ask(int k,int l,int r,int i,int &ans){
		ans=Add(ans,X[k].tag);
		if(l==i&&i==r)
		  return ;
		int mid=(l+r)>>1;
		if(i<=mid)
		  Ask(X[k].L,l,mid,i,ans);
		else
		  Ask(X[k].R,mid+1,r,i,ans);
	}
	inline int Ask(int u){
		int X=0,Y=0;
		Ask(root[id[u]+siz[u]-1],0,n,h[u],X);
		Ask(root[id[u]-1],0,n,h[u],Y);
		return (X-Y+mod)%mod;
	}
};
namespace Std{
	int Min,sum,x,a,b,c,t;
	int dep[N],g1[N],g2[N],g3[N];
	int Fa[N][M],F[N][M];
	vector<pi> E1[N],E2[N],E3[N];
    inline void dfs(int u){
        For(j,1,M-1)
          Fa[u][j]=Fa[Fa[u][j-1]][j-1];
        for(auto v:E[u]){
            if(v==fa[u])
              continue;
            Fa[v][0]=u;
            dep[v]=dep[u]+1;
            dfs(v);
        }
    }
    inline int get_fa(int u,int k){
        if(!k)
          return u;
        _For(j,0,M-1){
            if(k>=(1ll<<j)){
                k-=(1ll<<j);
                u=Fa[u][j];
            }
        }
        return u;
    }
	inline void dfs1(int u){
		For(i,1,M-1)
		  F[u][i]=min(F[u][i-1],F[Fa[u][i-1]][i-1]);
		for(auto v:E[u]){
			if(v==fa[u])
			  continue;
			F[v][0]=h[v];
			dfs1(v);
		}
	}
	inline void solve(){
		Read();
        For(j,0,M-1)
          Fa[1][j]=1;
		dfs(1);
		For(i,1,n)
		  root[i]=0;
		For(i,0,n-1){
			E1[i].clear();
			E2[i].clear();
			E3[i].clear();
		}
        For(i,2,n){
        	a=get_fa(i,r[i]),b=get_fa(i,l[i]),c=get_fa(i,h[i]+1);
			h[i]=dep[i]-h[i]-1;
            l[i]=dep[a],r[i]=dep[b];
            if(l[i])
              E1[l[i]-1].push_back({i,fa[a]});
            E2[r[i]].push_back({i,b});
            E3[h[i]].push_back({i,c});
        }
        For(j,0,M-1)
          F[1][j]=INF;
        dfs1(1);
        For(i,2,n){
        	if(l[i]){
        		x=i;
        		_For(j,0,M-1)
        		  if(F[x][j]>=l[i])
        			x=Fa[x][j];
        		if(x==i)
        		  g1[i]=-1;
        		else
        		  g1[i]=get_fa(i,dep[i]-dep[x]-1);    		
			}
			else
			  g1[i]=-1;
			x=i;
			_For(j,0,M-1)
			  if(F[x][j]>r[i])
			    x=Fa[x][j];
			if(x==i)
			  g2[i]=-1;
			else
			  g2[i]=get_fa(i,dep[i]-dep[x]-1);
			Min=INF,x=i;
			_For(j,0,M-1)
			  if(F[x][j]>=h[i])
				x=Fa[x][j];
			ADD(i,x);
			if(x==i)
			  g3[i]=-1;
			else
			  g3[i]=get_fa(i,dep[i]-dep[x]-1); 
		}
		Tr.init();
		Tr.update(1,1,1);
		Seg::tidy();
		Seg::build(root[1],0,n);
		For(i,2,n){
			root[i]=root[i-1];
			Seg::update(root[i],0,n,l[_id[i]],r[_id[i]],1);
			a=0;
			Seg::Ask(root[i],0,n,0,a);
		}
		For(i,0,n-1){
			for(auto t:E1[i]){
				x=t.fi,b=g1[x];
				if(b==-1)
				  continue;
				a=Tr.ask(1,t.se);
				Tr.update(x,b,mod-a);
			}
			for(auto t:E2[i]){
				x=t.fi,b=g2[x];
				if(b==-1)
				  continue;
				a=Tr.ask(1,t.se);
				Tr.update(x,b,a);
			}
			for(auto t:E3[i]){
				x=t.fi,b=g3[x];
				if(b==-1)
				  continue;
				a=Tr.ask(1,t.se);
				sum=Seg::Ask(x);
				Tr.update(x,b,1ll*sum*a%mod);
			}
		}
		For(i,2,n){
			write(Tr.query(1,dfn[i]));
			putchar(' ');
		}
		putchar('\n');
	}
	inline void work(){
		while(T--)
		  solve();
	}
};
int main(){
	//open("A.in","A.out");
    read(),T=read();
    Std::work();
    return 0;
}

待补。

  • 标题: NOI 2024 题解
  • 作者: rgw2010
  • 创建于 : 2024-08-28 00:00:00
  • 更新于 : 2024-09-13 18:30:02
  • 链接: https://rgw2010.github.io/2024/08/28/NOI 2024 题解/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
NOI 2024 题解
  1. 思路：
  2. 完整代码：
  3. 思路：
  4. 完整代码：
  5. 思路：
  6. 完整代码；