paulzrm's blog

发表于 分类于

本文迁移自洛谷原文。

模拟赛考了这题，花了2h刚了个弱智的点分治做法。

假设当前我们分治到的重心是 ，那么我们此时钦定重合部分一定要经过点 。

这时候就会有两种情况：

  1. 不是一个端点。

那么我们可以对 的所有儿子排序，以 为第一关键字（该有根子树中最深的有两个及以上儿子的节点的深度），以 为第二关键字（该有根子树中满足第一关键字下最大的深度的节点的两个距离该节点距离最大的两个点的距离之和，说人话就是两个分叉的长度）进行排序。

排序后，由于可能存在多个直径，我们需要找到所有经过点 的直径的答案。但是，我们按照上述规则排完序后，直接比较前两大的即可。

证明：

  • 如果有多个儿子的深度最大，那么该方法肯定只在他们之间选。而且，根据第二关键字，我们选前两个就足以凑到在公共部分最长的情况下总长度最长的 方案了。

  • 如果只有一个儿子深度最大，那么按照第二关键字还是能把所有深度第二大的儿子按照分叉从大到小排序，仍然可以选择前两大的配对。

  1. 是一个直径的端点。

这种情况可能在一个蒲公英一样的图上出现（一个菊花接了一条链和一个小分叉）。

那么 的所有儿子中有两个及以上叶子的节点只有一个（伸出去的那条链），我们不得不看 的所有其他直接儿子作为分叉。就是记录每个儿子的 表示其最深的叶子到它的距离，和 表示 对应的叶子的编号。

然后套一个点分治模板就行了。

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
#include<bits/stdc++.h>
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn];
int ban[mxn];
int root=-1,ma=mxn,totn;
int sz[mxn],n;
inline void findroot(int x,int fa=0){
	sz[x]=1;int cm=0;
	for(int y:g[x])if(y!=fa and !ban[y]){
		findroot(y,x);
		sz[x]+=sz[y];
		cm=max(cm,sz[y]);
	}
	cm=max(cm,totn-sz[x]);
	if(cm<ma){
		ma=cm;
		root=x;
	}
}
vector<int>v,o;
int deg[mxn],dt[mxn],lt[mxn],fa[mxn],id[mxn],dep[mxn],sm[mxn],par[mxn];
pair<int,int>ch[mxn];
inline void dfs(int x,int fa=0){
	par[x]=fa,v.push_back(x),deg[x]=0,lt[x]=0,id[x]=x,sz[x]=1,dep[x]=-mxn;
	for(int y:g[x])if(!ban[y] and y!=fa){
		dfs(y,x),++deg[x];sz[x]+=sz[y];
		if(lt[x]<lt[y]+1){
			lt[x]=lt[y]+1;
			id[x]=id[y];
		}
	}
}
inline void dfs2(int x,int fa=0){
	vector<pair<int,int> >cv;cv.clear();
	sm[x]=-mxn;ch[x]={-mxn,-mxn};dep[x]=-mxn;
	for(int y:g[x])if(!ban[y] and y!=fa){
		dfs2(y,x);
		if(dep[y]+1>dep[x] and sm[y]>=0){
			sm[x]=sm[y],ch[x]=ch[y];dep[x]=dep[y]+1;
		}else if(dep[y]+1==dep[x] and sm[y]>=0){
			if(sm[y]>sm[x]){
				sm[x]=sm[y];
				ch[x]=ch[y];
			}
		}
		cv.push_back({lt[y],id[y]});
		sort(cv.rbegin(),cv.rend());
		if(cv.size()>3)cv.pop_back();
	}
	if(sm[x]<0 and cv.size()>1){
		if(cv[0].first+cv[1].first>sm[x]){
			sm[x]=cv[0].first+cv[1].first;
			ch[x]={cv[0].second,cv[1].second};
			dep[x]=0;
		}
	}
}
#define x1 x114514
#define y1 y114514
#define x2 x1919810
#define y2 y1919810
int cml,sml,x1,y1,x2,y2,bp[mxn];
vector<int>ee;bool fd;
int cnt=0;
inline void go(int x){
	v.clear(),dfs(x);
	if(v.size()<=5){
		for(int i:v)ban[i]=1;
		return;
	}
	dfs2(x);
	vector<pair<int,pair<int,pair<int,int> > > >cv;cv.clear();
	for(int y:g[x])if(!ban[y] and sm[y]>=0 and dep[y]>=0)cv.push_back({dep[y]+1,{sm[y],ch[y]}});
	if(cv.size()>1){
		sort(cv.rbegin(),cv.rend());
		if(cml<cv[0].first+cv[1].first or (cml==cv[0].first+cv[1].first and sml<cv[0].second.first+cv[1].second.first)){
			cml=cv[0].first+cv[1].first;
			sml=cv[0].second.first+cv[1].second.first;
			x1=cv[0].second.second.first,x2=cv[0].second.second.second;
			y1=cv[1].second.second.first,y2=cv[1].second.second.second;
		}
	}else if(cv.size()==1){
		vector<pair<int,int> >wr;wr.clear();
		for(int y:g[x])if(!ban[y] and dep[y]<0)wr.push_back({lt[y],id[y]});
		sort(wr.rbegin(),wr.rend());
		if(wr.size()>1){
			int tc=cv[0].first,ts=cv[0].second.first+wr[0].first+wr[1].first;
			if(tc>cml or (tc==cml and ts>sml)){
				cml=tc,sml=ts;
				x1=wr[0].second,x2=wr[1].second;
				y1=cv[0].second.second.first,y2=cv[0].second.second.second;
			}
		}
	}
	ban[x]=1;
	for(int y:g[x]){
		if(ban[y])continue;
		totn=sz[y];ma=mxn;
		findroot(y);
		go(root);
	}
}
int main(){
//	freopen("reveal.in","r",stdin);
//	freopen("reveal.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;for(int i=1,u,v;i<n;++i)cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
	totn=n;findroot(1,0);
	go(root);
	cout<<x1<<' '<<y1<<'\n'<<x2<<' '<<y2<<'\n';
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

CF372C Watching Fireworks is Fun

我们可以换种思考方式来解决这个问题。

显然 是一个很无关紧要的东西，我们可以把它们先全部累加到 里。然后题目就变成了要让 最大，所以就可以看为要使得 最小。

令 表示考虑到某个时间点，此时你的坐标为 的最小的 。

假设我们已经考虑了前 场烟花，此时我们要考虑加入第 场烟花带来的影响。

令 ，则我们就相当于执行 。

然后每燃放一场烟花，我们就相当于对 加上一个 的函数。

综上，可以发现，这个 是一个折线函数，且段数是 的，计算相邻时间和加入新烟花秀都可以在 的时间内解决，故我们得到了一个时间复杂度为 的做法。

考虑继续优化。

发现这个 的每条折线的斜率从左往右可以看作依次为 。

这启发我们可以维护两个优先队列一样的东西，一个维护左半段斜率小于 的部分的转折点的 坐标，另一个维护右半段的东西。

我们考虑在这种维护方式下，等待时间和加入烟花秀各有什么影响。

由于这个 是先降后增的，所以这个等待一段时间就变得非常好处理。就是让 中的所有元素减去 ， 中的所有元素加上 ，中间多出一段斜率为 的段。

当然，我们没有必要真的去减一遍，我们只需要维护两个全局减去/加上的 和 ，每次就让 ，然后再 中加入新元素的时候就加入 。

再考虑这个加入烟花的操作。

令左半段最右边的转折点横坐标为 ，右半段最左边的转折点横坐标为 。

此时就相当于 都多了一个转折点 ，都push。

此时 的最右边的转折点就成为了 ，且斜率为 的转折点消失了，但不妨碍我们维护，因为我们可以想象它和斜率为 的转折点重合了。

所以我们加入两边 至 ，然后把 加到 即可。

和上一种情况同理。

综上，时间复杂度 ，可以加强到 ，甚至比原题的单调队列优化dp好写的多。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,d,ans,tag,pre;
priority_queue<int>L;
priority_queue<int,vector<int>,greater<int> >R;
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>d;
	for(int i=1;i<=m;++i){
		int a,b,t;cin>>a>>b>>t;
		ans+=b;
		if(i==1)L.push(a),R.push(a),pre=t;
		else{
			tag+=d*(t-pre);
			int l=L.top()-tag,r=R.top()+tag;
			if(a<l)L.pop(),L.push(a+tag),L.push(a+tag),R.push(l-tag),ans-=l-a;
			else if(a>r)R.pop(),R.push(a-tag),R.push(a-tag),L.push(r+tag),ans-=a-r;
			else L.push(a+tag),R.push(a-tag);
		}
		pre=t;
	}
	cout<<ans<<'\n';
}

发表于 分类于

本文迁移自洛谷原文。

这里是 [CSP-S 2022]假期计划 的另类做法。

  • 先暴力bfs把所有能在 步内达到的点互相连边，复杂度

  • 然后随机染色。对于每个点，随机染上 这四种颜色中的任意一种，然后就相当于选出有4个颜色不同的点的包含点1的环。这样就避免了重复经过某个点的情况。

  • 显然这是原问题的弱化版，每次有 的可能性对，随个 次就能过洛谷的民间数据了。

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
//start coding at 2:35
//finish coding at 2:47
//finish debuging at 2:55
//Code by paulzrm
/*
虽千万人逆我之我仍执着
侠客行遍九州恩仇奔波
刀光剑影里是谁的明眸粲粲如星火
纵使我双掌倚天苍龙俘获
奈何降不住这人心如魔
所谓天下第一 怎囿我天高海阔
*/
/*
此战 我战与我！
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=2505;
vector<int>g[mxn],ng[mxn];
ll n,m,k;
ll a[mxn];
int dist[mxn][mxn];
inline void bfs(int x){
	queue<int>q;for(;q.size();)q.pop();
	q.push(x);memset(dist[x],63,sizeof(dist[x]));dist[x][x]=0;
	for(;q.size();){
		int u=q.front();q.pop();
		for(int v:g[u])if(dist[x][v]>dist[x][u]+1){
			dist[x][v]=dist[x][u]+1;
			q.push(v);
		}
	}
}
int col[mxn];
ll dp[mxn],ans;
inline ll dfs(int x,int d){
	if(dp[x]!=-1)return dp[x];
	dp[x]=-5000000000000000000ll;
	if(d==4){
		if(dist[1][x]<=k+1)dp[x]=a[x];
		else dp[x]=-5000000000000000000ll;
		return dp[x];
	}
	for(int y:ng[x])
		if(col[y]==d+1)
			dp[x]=max(dp[x],dfs(y,d+1)+a[x]);
	return dp[x];
}
int main(){
	ios_base::sync_with_stdio(false);
	srand(1145141);
	cin>>n>>m>>k;
	for(int i=2;i<=n;++i)cin>>a[i];
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;++i)bfs(i);
	for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(dist[i][j]<=k+1){
		ng[i].push_back(j);
		ng[j].push_back(i);
	}
	for(int ee=0;ee<200;++ee){
		if(rand()%3==1)rand();
		for(int i=2;i<=n;++i)col[i]=rand()%4+1;
		memset(dp,-1,sizeof(dp));
		dfs(1,0);
		ans=max(ans,dp[1]);
	}
	cout<<ans<<endl;
	return 0;
}

upd：这份没有卡时的代码在官方数据下获得了整整 65pts，但我们可以通过一个 clock() 来进行卡时，获得 100pts。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=2505;
vector<int>g[mxn],ng[mxn];
ll n,m,k;
ll a[mxn];
int dist[mxn][mxn];
inline void bfs(int x){
	queue<int>q;for(;q.size();)q.pop();
	q.push(x);memset(dist[x],63,sizeof(dist[x]));dist[x][x]=0;
	for(;q.size();){
		int u=q.front();q.pop();
		for(int v:g[u])if(dist[x][v]>dist[x][u]+1){
			dist[x][v]=dist[x][u]+1;
			q.push(v);
		}
	}
}
int col[mxn];
ll dp[mxn],ans;
inline ll dfs(int x,int d){
	if(dp[x]!=-1)return dp[x];
	dp[x]=-5000000000000000000ll;
	if(d==4){
		if(dist[1][x]<=k+1)dp[x]=a[x];
		else dp[x]=-5000000000000000000ll;
		return dp[x];
	}
	for(int y:ng[x])
		if(col[y]==d+1)
			dp[x]=max(dp[x],dfs(y,d+1)+a[x]);
	return dp[x];
}
int main(){
    clock_t st=clock();
	ios_base::sync_with_stdio(false);
	srand(1919810);
	cin>>n>>m>>k;
	for(int i=2;i<=n;++i)cin>>a[i];
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;++i)bfs(i);
	for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(dist[i][j]<=k+1){
		ng[i].push_back(j);
		ng[j].push_back(i);
	}
	for(int ee=0;ee<10000;++ee){
	    if(clock()-st>1.98*CLOCKS_PER_SEC)break;
		if(rand()%3==1)rand();
		for(int i=2;i<=n;++i)col[i]=rand()%4+1;
		memset(dp,-1,sizeof(dp));
		dfs(1,0);
		ans=max(ans,dp[1]);
	}
	cout<<ans<<endl;
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

题目意思很清楚不解释。

我们一共有 个点，但只有 条有向边，还想让这张图强连通，显然是要求我们把这张图变为一个环。

稍微思考一下即可发现，这个题目等价于保留代价最大的那些链，然后删掉剩余的边进行缝缝补补。（因为最后是要变为一个环，换上每个点的入读和出度均为 ，如果保留的不是链的形式那么肯定有点出度或者入度大于 ，肯定不合法）

回头看看这个图。 个点， 条边，是一个基环树的形式。按照套路把环和树分开来看。

对于一个树点，由于要删掉大部分边使得它的入度变为 ，我们就可以只保留到它的边权最大的那条边。

由于这张图可能是个基环树森林，我们需要把所有的环也拼接起来，所以说，每个环上至少要断开一个点。

对于一个环，我们令 表示点 的所有树节点儿子到 的那条边上权值的最大值， 为这些权值的和。令 表示环上指向 的那个点到 的这条边的边权。

统计 为对于一个环 上面的点，满足 的点的个数。

如果这个环的 ，那么我们想不断白不断（管它是环点还是树点，都只能有一条入边，且断了环边仍是合法的）。

如果这个环的 ，那么为了满足“每个环至少要断开一个点”这个条件，我们就要找到 最小的那个点断开，使得代价最小。

ps. 有一个特例，整张图只有一个大环，且这个大环包括了所有点的时候，它既不需要和其他环拼接，也不需要让其他树点挤进来，所以答案就是 。

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
#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn];
vector<pair<int,int> >tos[mxn];
int n,a[mxn],c[mxn];
int used[mxn],cused;
int ord[mxn],cord;
int inring[mxn];
int sum[mxn],ma[mxn];
vector<vector<int> >rings;
inline void dfs(int x){
	if(used[x]==cused){//find a ring
		ord[++cord]=x;
		vector<int>ring;
		for(int i=cord-1;i;--i){
			inring[ord[i]]=1;
			ring.push_back(ord[i]);
			if(ord[i]==x)break;
		}
		rings.push_back(ring);
		return;
	}
	if(used[x])return;
	ord[++cord]=x;
	used[x]=cused;
	dfs(a[x]);
	--cord;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>c[i];
		g[i].push_back(a[i]);
		tos[a[i]].push_back({i,c[i]});
	}
	for(int i=1;i<=n;++i){
		if(!used[i]){
			++cused;
			cord=0;
			dfs(i);
		}
	}
	if(rings.size()==1 and rings[0].size()==n){
		cout<<0<<endl;
		return 0;
	}
	ll ans=0;
	for(int i=1;i<=n;++i){
		if(!inring[i]){
			int mx=0,sm=0;
			for(auto p:tos[i]){
				mx=max(mx,p.second);
				sm+=p.second;
			}
			ans+=sm-mx;
		}
	}
	for(vector<int>ring:rings){
		ll tot=0;
		int cnt=0,tval,delta=0;
		for(int i:ring){
			int mx=0,sm=0;
			for(auto p:tos[i]){
				if(!inring[p.first]){
					mx=max(mx,p.second);
					sm+=p.second;
				}else tval=c[p.first];
			}
			ma[i]=mx;
			sum[i]=sm;
			tot+=sum[i];
			if(tval<mx)++cnt,delta+=mx-tval;
		}
		if(cnt==0){
			ll res=11451491919810;
			for(int i:ring){
				int j=a[i];
				res=min(res,tot-ma[j]+c[i]);
			}
			ans+=res;
		}else ans+=tot-delta;
	}
	cout<<ans<<endl;
}

发表于 分类于

本文迁移自洛谷原文。

题目意思很清楚不用说。

看到每个点都有颜色，然后询问和颜色的种类有关，时限开了很【】的 8s，就可以往根号分治方面想了。

按照常理，我们钦定一个 ，所有颜色为 的点的集合为 。

如果 且 ，则他们都是小块，可以直接建立出虚树暴力跑，单次询问时间复杂度 。

如果 且 ，那么我们可以进行预处理。对于所有的大块（设其颜色为 ），我们处理处其 数组， 表示在第 个节点到根结点的路上，有多少个颜色为 的节点，然后在询问的时候直接计算 即可。预处理时间复杂度 ，单次询问时间复杂度 。

同理，如果 且 ，那么我们可以预处理 表示第 个节点的子树中有多少个节点的颜色为 ，询问时计算 。时间复杂度同上。

最后，如果 且 ，那么和小块对小块一样，可以预处理，对于所有可能的大块对建出虚树算一遍答案，询问时直接调用即可。时间复杂度 。

上述全部为口胡，如果实现不精细的话，时间复杂度会写成 且常数巨大，导致你可能只有 60pts 的好成绩。

  1. 普通的倍增LCA的询问是 的，我们要用 ST 表做到 预处理， 求 LCA。

  2. 在建立虚树的时候，有一步要对所有点按照 dfs 序排序。如果不想写基数排序怎么办？可以在询问前先对每个 中的元素先按照字典序排序，在询问的时候用类似归并排序的方法 merge 两个有序的 和 ，就可以把这个 砍掉了。

现在的时间复杂度已经降到了正好的 ，但是巨大的常数仍让你在 94pts 和 97pts 之间徘徊。

为了减小常数：

  1. 加入快读快输

  2. 小对小和大对大中暴力统计答案的dfs看起来很累赘，那么短。如果我们能够想办法把这一步放入建立虚树的过程中，那么就可以避免存虚树的边，从而大幅减小常数（感谢 w23c3c3 的指导）

然后这样就能过了。

Talk is cheap, show me the 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
188
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define reg register
const int maxn=10005;        //很好的快读板子
char buffer[maxn],*S,*T;
inline char Get_Char(){
    if(S==T){
        T=(S=buffer)+fread(buffer,1,maxn,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}
inline int read(){
    reg char c;
    reg int re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)return -re;
    return re;
}
inline void read(int&x){
    reg char c;
    reg int re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)x=-re;
    else x=re;
}
inline void read(ll&x){
    reg char c;
    reg ll re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)x=-re;
    else x=re;
}
inline void print(int x){
	if(x<10){
		putchar(x+'0');
		return;
	}
	print(x/10);
	putchar(x%10+'0');
}
const int mxn=2e5+5;
vector<int>g[mxn];
int n,R,q,r[mxn];
int dep[mxn*2];
int ord[mxn*2],cco,cord[mxn*2];
int mi[mxn*2][22];
int lg[mxn*2],co;
int st[mxn*2],ed[mxn*2];
inline void dfs(int x,int par=0,int deep=1){
	cord[++cco]=x;
	st[x]=cco;ed[x]=cco;
	dep[x]=deep;ord[x]=++co;
	for(int y:g[x]){
		if(par==y)continue;
		dfs(y,x,deep+1);
		cord[++cco]=x;
		ed[x]=cco;
	}
}
inline void init(){     //预处理ST表
	lg[1]=0;
	for(int i=2;i<mxn*2;++i)lg[i]=lg[i>>1]+1;
	for(int i=1;i<=cco;++i)mi[i][0]=cord[i];
	for(int k=1;k<22;++k){
		for(int i=1;i<=cco-(1<<k)+1;++i){
			int x=mi[i][k-1],y=mi[i+(1<<(k-1))][k-1];
			if(dep[x]<dep[y])mi[i][k]=x;
			else mi[i][k]=y;
		}
	}
}
inline int lca(int x,int y){
	int fx=st[x],fy=ed[y];
	if(fx>fy)swap(fx,fy);
	int ax=mi[fx][lg[fy-fx]],ay=mi[fy-(1<<lg[fy-fx])+1][lg[fy-fx]];
	if(dep[ax]<dep[ay])return ax;
	else return ay;
}
inline bool cmp(int x,int y){return ord[x]<ord[y];}
int sta[mxn],top=0;
int sz[mxn];
int up[404][mxn],dw[404][mxn];
inline vector<int>mer(vector<int>x,vector<int>y){  //类似归并的操作
	vector<int>rt;rt.clear();
	int i=0,j=0;
	for(;i<x.size() and j<y.size();)
		if(cmp(x[i],y[j]))rt.push_back(x[i]),++i;
		else rt.push_back(y[j]),++j;
	for(;i<x.size();++i)rt.push_back(x[i]);
	for(;j<y.size();++j)rt.push_back(y[j]);
	return rt;
}
inline void gen(vector<int>v,int y){  //建立虚树
	top=0;
	sta[++top]=1;
	sz[1]=r[1]==y;
	for(int i:v){
		if(i!=1){
			int l=lca(sta[top],i);
			if(l!=sta[top]){
				for(;ord[l]<ord[sta[top-1]];)sz[sta[top-1]]+=sz[sta[top]],--top;
				if(ord[l]>ord[sta[top-1]]){
					sz[l]=r[l]==y;
					sz[l]+=sz[sta[top]];
					sta[top]=l;
				}else sz[l]+=sz[sta[top]],top--;
			}
			sz[i]=r[i]==y;
			sta[++top]=i;
		}
	}
	for(int i=top-1;i>=1;--i)sz[sta[i]]+=sz[sta[i+1]];
}
vector<int>col[mxn];
vector<int>hea;
int ans[404][404];
int id[mxn];
//inline void getans(int x,int fa,int cl){//on ng[]    //原来的暴力统计小对小和大对大的答案
//	if(r[x]==cl)sz[x]=1;
//	else sz[x]=0;
//	for(int y:ng[x])if(y!=fa)getans(y,x,cl),sz[x]+=sz[y];
//}
inline void prep(int x,int fa,int cl,int flg=0){   //预处理小对大和大对小的up和dw数组
	if(r[x]==hea[cl])dw[cl][x]=1,++flg;
	up[cl][x]=flg;
	for(int y:g[x])if(y!=fa){
		prep(y,x,cl,flg);
		dw[cl][x]+=dw[cl][y];
	}
}
inline void solve(){
	memset(id,-1,sizeof(id));
	read(n),read(R),read(q);
	read(r[1]);col[r[1]].push_back(1);
	for(int i=2;i<=n;++i){
		int x;read(x),read(r[i]);
		g[x].push_back(i);
		g[i].push_back(x);
		col[r[i]].push_back(i);
	}
	dfs(1);
	init();
	int bound=500;
	for(int i=1;i<=R;++i)if(col[i].size()>=bound)hea.push_back(i);  //这里我的B定为了500
	for(int i=0;i<hea.size();++i)id[hea[i]]=i;
	for(int i=1;i<=n;++i)sort(col[i].begin(),col[i].end(),cmp);
	for(int i=0;i<hea.size();++i)for(int j=0;j<hea.size();++j)if(i!=j){
		gen(mer(col[hea[i]],col[hea[j]]),hea[j]);
//		getans(1,0,hea[j]);
		ll res=0;
		for(int f:col[hea[i]])res+=sz[f];
		ans[i][j]=res;
	}
	for(int i=0;i<hea.size();++i)prep(1,0,i);
	for(;q--;){
		int x,y;read(x),read(y);
		if(~id[x] and ~id[y])print(ans[id[x]][id[y]]),putchar('\n');
		else if(~id[x] and id[y]==-1){
			ll res=0;
			for(int i:col[y])res+=up[id[x]][i];
			print(res),putchar('\n');
		}else if(id[x]==-1 and ~id[y]){
			ll res=0;
			for(int i:col[x])res+=dw[id[y]][i];
			print(res),putchar('\n');
		}else{
			gen(mer(col[x],col[y]),y);
//			getans(1,0,y);
			ll res=0;
			for(int f:col[x])res+=sz[f];
			print(res),putchar('\n');
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	//cin>>T;
	for(;T--;)solve();
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

上架建议：套路模板题，蓝。
z
我们把这个平面可以旋转 。

也就是说，原来是一个斜着的正方形求和，现在变成了水平的了，直接用前缀和即可。

原来：

旋转后：

实现有点丑陋，仅供参考。

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
#include<bits/stdc++.h>
const int mxn=2008;
using namespace std;
int n,m,k,q;
int a[mxn][mxn];
pair<int,int> rid[mxn][mxn];
pair<int,int>id[mxn][mxn];
int usef[mxn][mxn];
int TT;
inline int get(int x,int y,int xx,int yy){
	if(xx>2*max(n,m)+7)xx=2*max(n,m)+7;
	if(yy>2*max(n,m)+7)yy=2*max(n,m)+7;
	if(x<1)x=1;
	if(y<1)y=1;
	return a[xx][yy]-a[xx][y-1]-a[x-1][yy]+a[x-1][y-1];
}
inline void solve(){
	memset(a,0,sizeof(a));
	memset(usef,0,sizeof(usef));
	int lst=max(n,m)+3;
	for(int i=1;i<=n+m-1;++i){
		int y=1,x=i+1-y;
		int ee=lst;
		for(;x>=1 and y<=m;){
			if(x<=n){
				rid[x][y]={i,ee};
				id[i][ee]={x,y};
				usef[i][ee]=1;
			}
			--x;
			++y;
			ee+=2;
		}
		--lst;
	}
	for(int i=1;i<=k;++i){
		int x,y;cin>>x>>y;
		int tx=rid[x][y].first,ty=rid[x][y].second;
		++a[tx][ty];
	}
	for(int i=0;i<=max(n,m)*2+7;++i)for(int j=0;j<=max(n,m)*2+7;++j){
		if(i)a[i][j]+=a[i-1][j];
		if(j)a[i][j]+=a[i][j-1];
		if(i and j)a[i][j]-=a[i-1][j-1];
	}
	cout<<"Case "<<TT<<":\n";
	for(int ee=0;ee<q;++ee){
		int d;cin>>d;
		int ans=0;pair<int,int>pos;pos={1,1};
		for(int i=0;i<=max(n,m)*2+8;++i)for(int j=0;j<=max(n,m)*2+8;++j){
			if(!usef[i][j])continue;
			int t=get(i-d,j-d,i+d,j+d);
			if(t>ans)ans=t,pos=id[i][j];
			else if(t==ans){
				pair<int,int>tpos=id[i][j];
				if(tpos.second<pos.second or (tpos.second==pos.second and tpos.first<pos.first))pos=tpos;
			}
		}
		cout<<ans<<" ("<<pos.first<<","<<pos.second<<")\n";
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	while(cin>>n>>m>>k>>q){
		if(!n)break;
		++TT;
		solve();
	}
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

单调性可以被感性发现。

但是我们要注意一点，就是“在碰到一个人之后立刻点燃烟花棒”是不优的。

显然，我们可以让上一个人一直跟着这个人跑，直到烟花棒耗完。同样，无论在耗完的路上遇到了多少人，他们都可以一起跑。可以发现，我们这么做，即等到它耗尽再传递，能够延长火种运输的时间。因为你不用考虑这些人是否会累死

然后我们贪心的考虑，肯定是 号人向右跑， 号人向左跑。然后第 个人每传递到一个人后就选择下一个传递到左边还是右边。

如果一些人一直同向跑的话，那么他们之间的距离不会变。所以说，在这个过程中，只有 号和他的目标之间的距离在变。（我们这种模式就保证了在一个时刻只会有一个烟花棒是点燃的，而为了方便起见我们让 号人一直跟着这个烟花棒跑，反正也累不死）

所以，这道题就可以转化成有两列人，每次一个一个撞掉开头的一个，会消耗一定的时间，如果撞掉了就可以获得 的时间，问你能否撞完。（每撞上一个人会让这个烟花棒续命 时间）

考虑把前面的人和后面的人都分成一些连续的小段，满足每个段的所有前缀都满足 而到了结束则 。（ 代表这一段前缀中人的个数， 代表总消耗时间）

如果这两列能够正好被分为一些小段，那么我们执行以下操作：

每次选择一个段然后撞完，如果不能撞则一定不行了。

证明：

如果你没有把一个段撞完就去撞另外一个段，那么你肯定不如不撞这个段直接去撞另外一个段来的优，毕竟我们这个“段”的定义是所有前缀的前缀和都是要亏本的。

那么撞段的顺序会不会影响呢？也是不会的，因为这个段同时还满足了总的是要赚时间的，所以撞完就一定会有盈利。假设你面对的是两个段，你都能撞完，那么你先撞完第一个是肯定能撞完第二个的，先撞第二个同理。

综上，这个贪心策略是可行的。

如果不能被正好分完，那么就可以发现这个后缀满足 。由于最后剩下的时间是可以求出的，我们就可以把后缀的 和 翻转过来，然后用上述方法再求一遍即可。

感性证明的时候感觉会可能出现还需要再翻转再递归求下去的情况，但其实不会。因为如果出现了，那么我们可以吧这个后缀提出来，发现是满足 的，就可以组成一个段，分到第一次求解的末尾。

Talk is cheap, show me the 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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int ll inf=1e9;
const int mxn=1e5+5;
ll n,k,t;
ll a[mxn],b[mxn];
inline bool check(int x){
	for(int i=1;i<=n;++i)b[i]=a[i]-2ll*t*x*i; //预处理然后就可以直接比大小
	if(b[1]<b[n])return 0;
	int lx=k,rx=k;
	for(int i=k-1;i;--i)if(b[i]>=b[lx])lx=i;
	for(int i=k+1;i<=n;++i)if(b[i]<=b[rx])rx=i;
	int l=k,r=k;
	for(;lx<l or r<rx;){//正着
		bool ok=0,f=0;
		int tl=l,tr=r;
		for(;tl>lx and b[tl-1]>=b[r];)if(b[--tl]>=b[l]){
			f=1;
			break;
		}
		if(f)ok=1,l=tl;
		f=0;
		for(;tr<rx and b[tr+1]<=b[l];)if(b[++tr]<=b[r]){
			f=1;
			break;
		}
		if(f)ok=1,r=tr;
		if(!ok)return 0;
	}
	l=1,r=n;
	for(;l<lx or rx<r;){//处理后缀
		bool ok=0,f=0;
		int tl=l,tr=r;
		for(;tl<lx and b[tl+1]>=b[r];)if(b[++tl]>=b[l]){
			f=1;
			break;
		}
		if(f)ok=1,l=tl;
		f=0;
		for(;tr>rx and b[tr-1]<=b[l];)if(b[--tr]<=b[r]){
			f=1;
			break;
		}
		if(f)ok=1,r=tr;
		if(!ok)return 0;
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k>>t;
	for(int i=1;i<=n;++i)cin>>a[i];
	int l=0,r=inf/t+1,md;
	for(;l<r-1;){
		md=l+r>>1;
		if(check(md))r=md;
		else l=md;
	}
	if(check(0))r=0;
	cout<<r<<endl;
}
0%