Reincarnation

正因为梦易碎，才格外美好。

NOIP2023未来共同体 模拟十

发表于 分类于 ，
本文字数： 9.5k 阅读时长 ≈ 9 分钟

前面忘了。

A. 任务（mission）

原题： 月票购买

与本博客成外集训系列中均有提及。

B. 子段和

原题 世界上最幸福的女孩

全局加，区间最大子段和。

这道题没有常数空间限制，所以原题中线段树维护闵可夫斯基和显得有些鸡肋。

考虑把修改操作虚拟化，两种操作合二为一，得到：若全局加 ，则求包含 的最大子段和。

这个强制包含有点奇怪，但是我们可以将其拆分成 的最大右段和和 的最大左段和，你发现这是等价的。

我们以最大左段和为例，设 ，然后从图论考虑，若 ，则连边 ，否则不连边。

我们能够得到若干条链，设 表示 所在链的结点即可，有：

当 单调递增时， 单调递增，将 单增离线，则转移一定从每个位置划开，前面 ，后面 。可以发现分界点为 。

这个阈值可以通过堆进行维护，加边事实上是 的区间加，但查询为 的单点查，所以可以直接维护 。

AC 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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

const int N=2e5+5,inf=1e18;
#define mid (l+(r-l)/2)
struct line{
	int k,b;
	int val(int x){return k*x+b;}
};
struct sgt{
	line L[N];
	int s[N][2],rt,tot;
	void ins(int &d,int l,int r,line nw){
		if(!d){
			d=++tot;
			L[d]=nw;
			return;
		}
		int val0=L[d].val(mid),val1=nw.val(mid);
		if(val0>val1){
			swap(nw,L[d]);
		}
		if(l!=r){
			if(nw.k<L[d].k){
				ins(s[d][1],mid+1,r,nw);
			}
			else{
				ins(s[d][0],l,mid,nw);
			}
		}
	}
	void query(int d,int l,int r,int nd,int &ans){
		if(!d){
			return;
		}
		ans=min(ans,L[d].val(nd));
		nd<=mid?query(s[d][0],l,mid,nd,ans):query(s[d][1],mid+1,r,nd,ans);
	}
}le,ri;
#undef mid

int n,m;
int a[N];
void Input(){
	cin>>n>>m;
	rep(i,1,n){
		cin>>a[i];
	}
}
vector<pi> qry[N];
void solve(){
	vi pre(n+1,0);
	rep(i,1,n){
		pre[i]=pre[i-1]+a[i];
	}
	int totqry=0;
	int sum=0,mndlt=0,mxdlt=0;
	vi ans(m+1,0);
	rep(i,1,m){
		int op;cin>>op;
		if(op==1){
			int x;cin>>x;
			totqry++;
			ans[totqry]=pre[n]+n*sum;
			qry[x].pb(mp(sum,totqry));
		}
		else{
			int x;cin>>x;
			sum+=x;
			mndlt=min(mndlt,sum);
			mxdlt=max(mxdlt,sum);
		}
	}
	le.ins(le.rt,mndlt,mxdlt,(line){0,0});
	rep(i,1,n){
		for(pi x:qry[i]){
			int Get=inf;
			le.query(le.rt,mndlt,mxdlt,x.fi,Get);
			ans[x.se]-=Get;
		}
		le.ins(le.rt,mndlt,mxdlt,{i,pre[i]});
	}
	ri.ins(ri.rt,mndlt,mxdlt,{0,0});
	per(i,n,1){
		for(pi x:qry[i]){
			int Get=inf;
			ri.query(ri.rt,mndlt,mxdlt,x.fi,Get);
			ans[x.se]-=Get;
		}
		ri.ins(ri.rt,mndlt,mxdlt,{n-i+1,pre[n]-pre[i-1]});
	}
	rep(i,1,totqry){
		cout<<ans[i]<<'\n';
	}
}
signed main(){
	freopen("subarray.in","r",stdin);
	freopen("subarray.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	Input();
	solve();
	return 0;
}

C. 匹配（match）

题目简介

给定一个有 个结点的二分图，其中左边第 个结点与右边第 个结点间有连边。

要求对于任意两组匹配 ，有 ，求出最大匹配。

数据范围：

考虑朴素的 ，设 表示左边 与 的最大匹配，有转移：

显然有 ，那么 一定会转移前者，考虑转移时对差分数组的影响，发现是区间内位移一位，然后对区间端点处 个位置进行修改。

使用平衡树维护，时间复杂度 。

AC 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
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

const int N=1e5+5,M=N*2;
mt19937 rnd(114);
int s[M][2],w[M],sz[N],val[M],add[M],rt,tot;
int Newnode(int nw){
	tot++;
	w[tot]=rnd();
	sz[tot]=1;
	val[tot]=nw;
	return tot;
}
void pushup(int d){
	sz[d]=sz[s[d][0]]+sz[s[d][1]]+1;
}
void f(int d,int nw){
	val[d]+=nw;
	add[d]+=nw;
}
void pushdown(int d){
	if(add[d]){
		if(s[d][0]){
			f(s[d][0],add[d]);
		}
		if(s[d][1]){
			f(s[d][1],add[d]);
		}
		add[d]=0;
	}
}
void split(int d,int rk,int &le,int &ri){
	if(!d){
		le=ri=0;
		return;
	}
	pushdown(d);
	if(sz[s[d][0]]+1<=rk){
		le=d;
		split(s[d][1],rk-sz[s[d][0]]-1,s[le][1],ri);
	}
	else{
		ri=d;
		split(s[d][0],rk,le,s[ri][0]);
	}
	pushup(d);
}
void split_val(int d,int nw,int &le,int &ri){
	if(!d){
		le=ri=0;
		return;
	}
	pushdown(d);
	if(val[d]<=nw){
		le=d;
		split_val(s[d][1],nw,s[le][1],ri);
	}
	else{
		ri=d;
		split_val(s[d][0],nw,le,s[ri][0]);
	}
	pushup(d);
}
int merge(int x,int y){
	if(!x || !y){
		return x+y;
	}
	if(w[x]>w[y]){
		pushdown(x);
		s[x][1]=merge(s[x][1],y);
		pushup(x);
		return x;
	}
	else{
		pushdown(y);
		s[y][0]=merge(x,s[y][0]);
		pushup(y);
		return y;
	}
}
int qmx(int d){
	pushdown(d);
	return s[d][1]?qmx(s[d][1]):val[d];
}
int qmn(int d){
	pushdown(d);
	return s[d][0]?qmn(s[d][0]):val[d];
}
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;cin>>n;
	rep(i,0,n){
		rt=merge(rt,Newnode(0));
	}
	rep(i,1,n){
		int l,r;cin>>l>>r;
        assert(l>=1 && l<=r && r<=n);
		int rt0,rt1,rt2;
		int mx0,mn0;
		split(rt,r,rt,rt1);
		mx0=qmx(rt);
		split(rt,l-1,rt,rt0);
		mn0=qmn(rt0);
		
		rt0=merge(rt0,rt1);
		split_val(rt0,mx0,rt0,rt1);
		split(rt0,sz[rt0]-1,rt0,rt2);
		f(rt0,1);
		
		rt=merge(rt,Newnode(mn0));
		rt=merge(rt,rt0);
		rt=merge(rt,rt1);
	}
	cout<<qmx(rt)<<endl;
	return 0;
}

D. 最短路（path）

题目简介

存在一个 的网格图，所有格子之间都有长度为 的四连通边，以及存在 条边，从 连向 ，长度为 。

求出所有点对的最短路之和。对 取模。

数据范围：

首先离散化，视 同阶。

考虑怎么计算两点间的最短路，发现有最短路等于曼哈顿距离减去在不绕路的情况下最多能走到多少额外边。曼哈顿距离之和是好算的，考虑最多额外边个数之和怎么算。

将点对分为两类：左上到右下与左下到右上。这两类分别计算，下面以第一类为例。

我们枚举每一个起始点，考虑它到每个它右下点的点，最多能经过多少不绕路的额外边。

首先 出从额外边 的起点到额外边 的终点最多需要经过的额外边。

枚举起始点，用这个处理出的 进行转移，对于每一个作为某条额外边终点的点，到它最多经过多少条额外边，记其为 ，然后我们考虑对于每一个 ，有哪些点经过的额外边数不小于 ：我们找到所有 的点 ，将以它们为左上角、 为右下角的矩形并起来，这个并集中的所有点就是经过的额外边数不小于 的所有点。

发现以 的 为左上角的矩形并，一定包含了 的 为左上角的面积并，所以对于所有的 ，我们求出 的以 为左上角的面积并，再对所有的 的面积并求和即可。

枚举 求面积并的过程，首先按照终点排序，将所有枚举到的起始点在 的时间内处理贡献。

然后考虑更新 ，我们可以先枚举起始点所在的行，然后倒着枚举其所在的列，并用这一列中新加的起点去更新每个终点的 ，每个起点会被加入 次，更新为 ，所以总时间复杂度 。

实际为 。

AC 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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

const int N=1005,mod=998244353,i3=(mod+1)/3;
void chmax(int &x,const int &y){
	if(y>x){
		x=y;
	}
}
int n,m;
vector<array<int,4>> E;
int ans;
void solve(vector<array<int,4>> &ed){
	sort(ed.begin(),ed.end(),[](array<int,4>A,array<int,4>B){return A[3]<B[3];});
	m=ed.size();
	vi lis[2]{{1,n+1},{1,n+1}};
	rep(i,0,m-1){
		lis[0].pb( ed[i][0]+1 );
		lis[0].pb( ed[i][2] );
		lis[1].pb( ed[i][1]+1 );
		lis[1].pb( ed[i][3] );
	}
	rep(i,0,1){
		sort(lis[i].begin(),lis[i].end());
		lis[i].erase(unique(lis[i].begin(),lis[i].end()),lis[i].end());
		rep(j,0,m-1){
			ed[j][i]=upper_bound(lis[i].begin(),lis[i].end(),ed[j][i])-lis[i].begin()-1;
			ed[j][i+2]=lower_bound(lis[i].begin(),lis[i].end(),ed[j][i+2])-lis[i].begin();
		}
	}
	int cn=(int)lis[0].size()-2,cm=(int)lis[1].size()-2;
	vector<vi> f(m,vi(m,-1));
	rep(i,0,m-1){
		f[i][i]=0;
		rep(j,i,m-1){
			if(f[i][j]==-1){
				continue;
			}
			rep(k,i+1,m-1){
				if(ed[j][2]<=ed[k][0] && ed[j][3]<=ed[k][1]){
					chmax(f[i][k],f[i][j]+1);
				}
			}
		}
	}
	vector<vi> a(m),b(cm+1);
	rep(i,0,m-1){
		b[ed[i][1]].pb(i);
	}
	rep(i,0,cn){
		vi g(m,-1);
		int cnt=0;
		per(j,cm,0){
			int sz=(lis[0][i+1]-lis[0][i])*(lis[1][j+1]-lis[1][j])%mod;
			for(int id:b[j]){
				if(ed[id][0]>=i){
					rep(k,id,m-1){
						chmax(g[k],f[id][k]);
					}
					cnt++;
				}
			}
			rep(k,0,cnt-1){
				a[k].clear();
			}
			rep(k,0,m-1){
				if(g[k]!=-1){
					a[g[k]].pb(k);
				}
			}
			rep(k,0,cnt-1){
				if(a[k].empty()){
					break;
				}
				int mn=n+1,pre=0,cur=0;
				for(int id:a[k]){
					int x=lis[0][ ed[id][2] ],y=lis[1][ ed[id][3] ];
					cur+=(y-pre)*(n-mn+1);
					pre=y;
					mn=min(mn,x);
				}
				cur+=(n+1-pre)*(n-mn+1);
				(ans+=cur%mod*sz)%=mod;
			}
		}
	}
}
signed main(){
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>m>>n;
	E.resize(m);
	vector<array<int,4>> ed0,ed1;
	for(auto &x:E){
		rep(i,0,3){
			cin>>x[i];
		}
		if(x[0]>x[2]){
			swap(x[0],x[2]);
			swap(x[1],x[3]);
		}
		if(x[1]<x[3]){
			ed0.pb(x);
		}
		else{
			x[1]=n+1-x[1],x[3]=n+1-x[3];
			ed1.pb(x);
		}
	}
	solve(ed0);
	solve(ed1);
	int ans0=((n*n%mod*n-n)%mod+mod)%mod*n%mod*n%mod*i3%mod;
	ans=(ans0-ans+mod)%mod;
	cout<<ans<<endl;
	return 0;
}
相关文章