ZYCode Updating Round 赛后题解

# ZYCode Round #5 题解

## 参天大树 2

先考虑一条链上的情况，不难发现在链上走 $m$ 步可以到达 $m+1$ 个点。

然后把它放到一棵树上，除这条链以外每再多走1个点显然要用两步（来回）。

于是先求出树的直径，再数学计算就做完了。

## FAKE

`FAKE` 的情况显然是所有不确定的键全部漏掉还大于限制。

否则，答案满足单调性，考虑二分漏掉的键数。

check 中，因为已经有了漏掉的个数，所以可以直接算出他获得的基础分，也就是最大的连击分也可以算出。

于是问题转化为给定最大连击数，问至少再漏掉多少个键才能不超过最大值。

这个东西随便用什么维护。扫一遍过去，当连击超过阈值时只要贪心地选离自己最近的 0 点漏掉就行。如果不存在这样的 0 点使连击小于等于阈值，check 函数返回 0 即可。

[YZB的deque拉低效率的垃圾代码](https://www.luogu.com.cn/paste/gcklp6ms)

[lxy跑得飞快的神仙代码](https://www.luogu.com.cn/paste/7f8239ko)

## 造龙舟

**30pts**

可以先做 $O(n^3)$ 的 `floyd` ，然后枚举三个互不相同的点，如果它们的部件各不相同就更新答案。

时间复杂度 $O(n^3)$ 。

**Another 30pts**

将起点设为 $s$ ，有龙头的点设为 $p$ ，有龙尾的点设为 $q$ 。

我们以这三个点为源点分别跑一次 `dijkstra` 。

然后枚举每个有龙身的点 $i$ ，更新答案。有六种情况：
- $dis_{s,i}+dis_{i,p}+dis_{p,q}$
- $dis_{s,i}+dis_{i,q}+dis_{q,p}$
- $dis_{s,p}+dis_{p,i}+dis_{i,q}$
- $dis_{s,p}+dis_{p,q}+dis_{q,i}$
- $dis_{s,q}+dis_{q,i}+dis_{i,p}$
- $dis_{s,q}+dis_{q,p}+dis_{p,i}$

两档部分分代码：

```
#include <bits/stdc++.h>
using namespace std;
namespace sub1{
	#define int long long
	int dis[105][105];
	int a[105],n,m,s;
	void solve(){
		cin>>n>>m>>s;
		memset(dis,0x3f,sizeof dis);
		for(int i=1;i<=n;i++)cin>>a[i],dis[i][i]=0;
		for(int u,v,w,i=1;i<=m;i++){
			cin>>u>>v>>w;
			dis[u][v]=dis[v][u]=min(dis[u][v],w);
		}
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		int ans=1e18;
		for(int i=1;i<=n;i++){
			if(a[i]!=1)continue;
			for(int j=1;j<=n;j++){
				if(a[j]!=2)continue;
				for(int k=1;k<=n;k++){
					if(a[k]!=3)continue;
					ans=min(ans,min(min(dis[s][i]+dis[i][j]+dis[j][k],min(dis[s][i]+dis[i][k]+dis[j][k],dis[s][j]+dis[j][i]+dis[i][k])),min(min(dis[s][j]+dis[j][k]+dis[k][i],dis[s][k]+dis[k][i]+dis[i][j]),dis[s][k]+dis[k][j]+dis[j][i])));
				}
			}
		}
		cout<<ans<<endl;
	}
}
namespace sub2{
	#define int long long
	vector<pair<int,int> > vc[100005];
	int d1[100005],d2[100005],d3[100005];
	int n,m,s,p,q,a[100005],dis[100005];
	bool vis[100005];
	void dijkstra(int k){
		memset(dis,0x3f,sizeof dis);
		memset(vis,0,sizeof vis);
		dis[k]=0;
		priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
		q.push({0,k});
		while(q.size()){
			pair<int,int> pi=q.top();
			q.pop();
			if(vis[pi.second]) continue;
			vis[pi.second]=1;
			int x=pi.second;
			for(auto to:vc[pi.second]){
				int y=to.first;
				if(dis[x]+to.second<dis[y]){
					dis[y]=dis[x]+to.second;
					q.push({dis[y],y});
				}
			}
		}
	}
	void solve(){
		cin>>n>>m>>s;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]==1) p=i;
			if(a[i]==3) q=i;
		}
		for(int u,v,w,i=1;i<=m;i++){
			cin>>u>>v>>w;
			vc[u].push_back({v,w});
			vc[v].push_back({u,w});
		}
		dijkstra(s);for(int i=1;i<=n;i++)d1[i]=dis[i];
		dijkstra(p);for(int i=1;i<=n;i++)d2[i]=dis[i];
		dijkstra(q);for(int i=1;i<=n;i++)d3[i]=dis[i];
		int ans=1e18;
		for(int i=1;i<=n;i++){
			if(a[i]!=2)continue;
			ans=min(ans,min(d1[i]+d2[i]+d3[p],min(d1[i]+d3[i]+d2[q],min(d1[p]+d2[i]+d3[i],min(d1[p]+d2[q]+d3[i],min(d1[q]+d3[i]+d2[i],d1[q]+d3[p]+d2[i]))))));
		}
		cout<<ans<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T;
	cin>>T;
	if(T>=1&&T<=3) sub1::solve();
	if(T>=4&&T<=6) sub2::solve();
	return 0;
}

```

**100pts**

相当于在最短路上多了三维记录三个部件是否出现过。因为三维太烦所以写的时候压成一维了。

```
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int> > vc[100005];
int a[100005],dis[8][100005];
bool vis[8][100005]; 
priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > q;
void dijkstra(int s){
	memset(dis,0x3f,sizeof dis);
	dis[0][s]=0;
	q.push({0,{s,0}});
	pair<int,pair<int,int> > p;
	while(q.size()){
		p=q.top();
		q.pop();
		int ndis=p.first,now=p.second.first,st=p.second.second;
		if(vis[st][now]) continue;
		vis[st][now]=1;
		for(auto x:vc[now]){
			if(x.first!=s){
				if(dis[st|(1<<a[x.first])][x.first]>ndis+x.second){
					dis[st|(1<<a[x.first])][x.first]=ndis+x.second;
					q.push({ndis+x.second,{x.first,st|(1<<a[x.first])}});
				}
			}
			else{
				if(dis[st][s]>ndis+x.second){
					dis[st][s]=ndis+x.second;
					q.push({dis[st][s],{s,st}});
				}
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T;
	scanf("%lld",&T);
	int n,m,s;
	scanf("%lld%lld%lld",&n,&m,&s);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]--;
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		vc[u].push_back({v,w});
		vc[v].push_back({u,w});
	}
	dijkstra(s);
	int ans=1e18;
	for(int i=1;i<=n;i++) ans=min(ans,dis[7][i]);
	if(ans==1e18) printf("-1\n");
	else printf("%lld\n",ans);
	return 0;
}

```

## 数学题

**20pts**

真-暴力能过。每次询问把区间排序后硬做，时间复杂度 $O(nm\log n)$。

**Another 20pts**

因为 $k=1$ ，前两个询问前缀和做，后两个询问即为区间最小值。

**Yet Another 20pts**

将数组和询问中的 $k$ 分别排递增序。这样后面做的时候可以用各种乱搞通过。时间复杂度应该不超过 $n\log n$ 。

三档部分分整合：

```
#include <bits/stdc++.h>
using namespace std;
namespace sub1{
	int a[100005];
	int b[100005];
	bitset<100005> f;
	void solve(){
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=m;i++){
			int l,r,k;
			cin>>l>>r>>k;
			for(int j=l;j<=r;j++) b[j]=a[j];
			sort(b+l,b+r+1);
			int x=upper_bound(b+l,b+r+1,k)-&b[l-1]-1;
			cout<<x<<' ';
			f.reset();
			int ans=0;
			for(int j=l;j<=l+x-1;j++){
				if(!f[b[j]]) f[b[j]]=1,ans++;
			}cout<<ans<<' ';
			if(l+k-1<=r)cout<<b[l+k-1]<<' ';
			else cout<<"-1 ";
			f.reset();
			for(int j=l;j<=r;j++){
				if(!f[b[j]]){
					f[b[j]]=1;
					k--;
					if(k==0){
						cout<<b[j]<<endl;
						goto end;
					}
				}
			}
			cout<<"-1\n";
			end:;
		}
	}
}
namespace sub2{
	int a[100005];
	struct Segtree{
		int mn[120005];
		void init(){memset(mn,0x3f,sizeof mn);}
		void build(int p,int l,int r){
			if(l==r){
				mn[p]=a[l];
				return;
			}
			int mid=(l+r)>>1;
			build(p<<1,l,mid);
			build(p<<1|1,mid+1,r);
			mn[p]=min(mn[p<<1],mn[p<<1|1]);
		}
		int query(int p,int l,int r,int ql,int qr){
			if(qr<l||r<ql) return 1e9;
			if(ql<=l&&r<=qr) return mn[p];
			int mid=(l+r)>>1,res=1e9;
			if(ql<=mid)res=min(res,query(p<<1,l,mid,ql,qr));
			if(qr>mid)res=min(res,query(p<<1|1,mid+1,r,ql,qr));
			return res;
		}
	}sgt; 
	int sm[100005];
	void solve(){
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>a[i],sm[i]=sm[i-1]+(a[i]==1?1:0);
		sgt.build(1,1,n);
		for(int i=1;i<=m;i++){
			int l,r,k;
			cin>>l>>r>>k;
			cout<<sm[r]-sm[l-1]<<' ';
			if(sm[r]-sm[l-1])cout<<1<<' ';
			else cout<<0<<' ';
			cout<<sgt.query(1,1,n,l,r)<<' '<<sgt.query(1,1,n,l,r)<<endl;
		}
	}
}
namespace sub3{
	vector<int> id[100005];
	int ans[4][100005];
	int a[100005];
	bitset<100005> f;
	void solve(){
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=m;i++){
			int l,r,x;
			cin>>l>>r>>x;
			id[x].push_back(i);
		}
		sort(a+1,a+n+1);
		int cnt=0;
		int j=0,cc=0;
		for(int x,i=1;i<=1e5;i++){
			if(!(int)id[i].size()) continue;
			while(j<n&&a[j+1]<=i){
				j++;
				if(!f[a[j]]) f[a[j]]=1,cc++;
			}
			for(auto x:id[i])ans[0][x]=upper_bound(a+1,a+n+1,i)-&a[0]-1;
			for(auto x:id[i])ans[1][x]=cc;
			if(i<=n)for(auto x:id[i])ans[2][x]=a[i];
			else for(auto x:id[i])ans[2][x]=-1;
		}
		f.reset();
		j=0;
		cc=0;
		for(int x,i=1;i<=1e5;i++){
			if(!(int)id[i].size()) continue;
			while(j<n&&cc<i){
				j++;
				if(!f[a[j]]) f[a[j]]=1,cc++;
			}
			if(cc==i) for(auto x:id[i])ans[3][x]=a[j];
			else for(auto x:id[i])ans[3][x]=-1;
		}
		for(int i=1;i<=m;i++) printf("%d %d %d %d\n",ans[0][i],ans[1][i],ans[2][i],ans[3][i]);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T;
	cin>>T;
	if(T==1||T==2)sub1::solve();
	if(T==3||T==4)sub2::solve();
	if(T==5||T==6)sub3::solve();
	return 0;
}

```

**100pts**

莫队+值域分块。分块的时候记录块内出现的值的种数、出现次数。莫队扩展的时候对应修改即可。设值域为 $num$ ，时间复杂度：$ O(n\sqrt{n} + m\sqrt{num})$ 。

~~可持久化平衡树是个什么东西。常数大还难调。~~

```
#include <bits/stdc++.h>
using namespace std;
int a[100005],ans1[100005],ans2[100005],ans3[100005],ans4[100005],n,m,siz,C;
struct Q{
	int l,r,k,id;
}q[100005];
bool cmp(Q x,Q y){
	if(x.l/siz!=y.l/siz) return x.l/siz<y.l/siz;
	if((x.l/siz)%2==0) return x.r>y.r;
	return x.r<y.r;
}
int bl[100005];
int c[100005];
int tot[505],t2[505];
void add(int x){
	if(c[x])tot[bl[x]]--;
	c[x]++;
	t2[bl[x]]++;
	if(c[x])tot[bl[x]]++;
}
void del(int x){
	if(c[x])tot[bl[x]]--;
	c[x]--;
	t2[bl[x]]--;
	if(c[x])tot[bl[x]]++;
}
int ask1(int l,int r){
	int res=0;
	for(int i=l;i<=min(bl[l]*siz,r);i++) res+=c[i];
	if(bl[l]!=bl[r]) for(int i=(bl[r]-1)*siz+1;i<=r;i++) res+=c[i];
	for(int i=bl[l]+1;i<bl[r];i++) res+=t2[i];
	return res;
}
int ask2(int l,int r){
	int res=0;
	for(int i=l;i<=min(bl[l]*siz,r);i++) res+=(c[i]?1:0);
	if(bl[l]!=bl[r]) for(int i=(bl[r]-1)*siz+1;i<=r;i++) res+=(c[i]?1:0);
	for(int i=bl[l]+1;i<bl[r];i++) res+=tot[i];
	return res;
}
int ask3(int k){
	int res=0;
	for(int i=1;i<=C;i++){
		if(res+t2[i]>=k){
			for(int j=(i-1)*siz+1;j<=i*siz;j++){
				if(res+c[j]>=k)
					return j;
				res+=c[j];
			}
		}
		else res+=t2[i];
	}
	return -1;
}
int ask4(int k){
	int res=0;
	for(int i=1;i<=C;i++){
		if(res+tot[i]>=k){
			for(int j=(i-1)*siz+1;j<=i*siz;j++){
				if(res+(c[j]?1:0)>=k)
					return j;
				res+=(c[j]?1:0);
			}
		}
		else res+=tot[i];
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
  	int T;
   	cin>>T;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	siz=sqrt((int)(1e5)); 
	for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r>>q[i].k,q[i].id=i;
	sort(q+1,q+m+1,cmp);
	C=(99999)/siz+1;
	for(int i=1;i<=(int)(1e5);i++) bl[i]=(i-1)/siz+1;
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(r<q[i].r) add(a[++r]);
		while(l>q[i].l) add(a[--l]);
		while(r>q[i].r) del(a[r--]);
		while(l<q[i].l) del(a[l++]);
		ans1[q[i].id]=ask1(1,q[i].k);
		ans2[q[i].id]=ask2(1,q[i].k);
		ans3[q[i].id]=ask3(q[i].k);
		ans4[q[i].id]=ask4(q[i].k);
	}
	for(int i=1;i<=m;i++) printf("%d %d %d %d\n",ans1[i],ans2[i],ans3[i],ans4[i]);
	return 0;
}
```