暑假集训CSP提高模拟8

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[5];
int main()
{
	cin>>a[1]>>a[2]>>a[3];
	sort(a+1,a+3+1);
	ll ans=(a[3]-a[1])/2+(a[3]-a[2])/2;
	a[1]+=(a[3]-a[1])/2*2;a[2]+=(a[3]-a[2])/2*2;
	if(a[1]==a[2]&&a[1]!=a[3])ans++;
	else if(a[1]!=a[2])ans+=2;
	cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N = 1e5+5;
vector <int> fa[N*2];
vector <pair<int,int>> G;
int n,m,q;
inline int find(int u,int id)
{
	if(fa[id][u]!=u)fa[id][u]=find(fa[id][u],id);
	return fa[id][u];
}
inline bool check(int mid,int L,int R)
{
	int c=find(L,mid);
//	cout<<c<<endl;
	for(int i=L+1;i<=R;i++)
	{
		if(find(i,mid)!=c)return 0;
	}
	
	return 1;
}
inline int fen(int l,int r,int L,int R)
{
	int ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid,L,R))
		{
			ans=mid;
			r=mid-1;
		}else
		{
			l=mid+1;
		}
	}
	return ans;
}
inline void work1()
{
	int u,v;
	for(int i=0;i<=m;i++)fa[i].resize(n+1);
	for(int i=1;i<=n;i++)fa[0][i]=i;
	for(int i=1;i<=m;i++)
	{
		copy(fa[i-1].begin(),fa[i-1].end(),fa[i].begin());
		u=G[i].first,v=G[i].second;
		int fu=find(u,i),fv=find(v,i);
		if(fu!=fv)fa[i][fu]=fv;
	}
	int l,r;
	while(q--)
	{
		cin>>l>>r;
		if(l==r)cout<<0<<endl;
		else
		{
			cout<<fen(1,m,l,r)<<endl;
		}
	}
}
int w2(int l,int r,int L,int R)
{
	int ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(0,L,R))
		{
			ans=mid;
			r=mid-1;
		}else
		{
			l=mid+1;
		}
	}
	return ans;
}
void work2()
{
	int l,r;
	cin>>l>>r;
//	cout<<l<<" "<<r<<endl;
	int u,v;
	fa[0].resize(n+1);
	for(int i=1;i<=n;i++)fa[0][i]=i;
	for(int i=1;i<=m;i++)
	{
		u=G[i].first,v=G[i].second;
		int fu=find(u,0),fv=find(v,0);
		if(fu!=fv)fa[0][fu]=fv;
//		if(i>=r-l+1)
//		{
		if(check(0,l,r))
		{
			cout<<i<<endl;
			break;
		}
//		}
//		cout<<fu<<" "<<fv<<endl;
	}	
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);	
//	freopen("lagrange2.in","r",stdin);
	
	cin>>n>>m>>q;int u,v;G.pb({0,0});
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;G.pb({u,v});
	}
	if(n<=100&&m<=100)
	{
		work1();
	}else if(q==1)
	{
//		cout<<"*****"<<endl;
		work2();
	}else
	{
		work1();
	}
	return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N = 1e5+5;
vector <pair<int,int>> edge[N];
int n,m,q;bool vis[N];
void dfs(int u,int fa,int lim)
{
	vis[u]=1;
//	cout<<u<<endl;
	for(int i=0;i<edge[u].size();i++)
	{
		int to=edge[u][i].first,id=edge[u][i].second;
		if(id>lim)continue;
		if(to==fa||vis[to])continue;
//		cout<<to<<" "<<u<<" "<<lim<<endl;
		dfs(to,u,lim);
	}
}
bool check(int mid,int L,int R)
{
//	cout<<"CHECK"<<mid<<" "<<L<<" "<<R<<endl;
	
//	for(int i=L;i<=R;i++)vis[i]=0;
	memset(vis,0,sizeof vis);
	dfs(L,0,mid);
	for(int i=L;i<=R;i++)
	{
		if(!vis[i])return 0;
	}
	return 1;
}
int fen(int l,int r,int L,int R)
{
	int ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid,L,R))
		{
			ans=mid;
			r=mid-1;
		}else
		{
			l=mid+1;
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);	
//	freopen("lagrange2.in","r",stdin);
	
	cin>>n>>m>>q;int u,v;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
//		cout<<"***"<<u<<" "<<v<<endl;
		edge[u].pb({v,i});
		edge[v].pb({u,i});
	}
	int l,r;
	while(q--)
	{
		cin>>l>>r;
		if(l==r)cout<<0<<endl;
		else
		{
			cout<<fen(1,m,l,r)<<endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N = 1e5+5;
//vector <pair<int,int>> edge[N];
int n,m,q,fa[N*2],f[N*2][25],now,st[N][25],val[N*3],dep[N*2];bool vis[N*3];
struct Node{int u,v,w;};vector <Node> G ;
//bool cmp(Node a,Node b){return a.w<b.w;}
vector <int> edge[N*2];
int find(int u)
{
	if(fa[u]!=u)fa[u]=find(fa[u]);
	return fa[u];
}
void dfs(int u,int fa)
{
	vis[u]=1;
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int j=1;j<=20;j++)
		f[u][j]=f[f[u][j-1]][j-1];
	for(auto to:edge[u])
	{
		if(to==fa)continue;
		dfs(to,u);	
	}	
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int j=20;j>=0;j--)
		if(dep[f[x][j]]>=dep[y])x=f[x][j];
	if(x==y)return x;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
void ST()
{
	for(int i=2;i<=n;i++)
	{
		st[i][0]=val[lca(i-1,i)];
//		cout<<"*&&&"<<lca(i,i+1)<<" "<<val[lca(i,i+1)]<<endl;
	}
	
	for(int j=1;j<=20;j++)
	{
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r)
{
	int k=log2(r-l+1);
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
void kruskal()
{
	for(int i=1;i<=2*n;i++)fa[i]=i;
	now=n;
	for(int i=1;i<=m;i++)
	{
		int fu=find(G[i].u),fv=find(G[i].v);
		if(fu!=fv)
		{
			++now;val[now]=G[i].w;
			fa[fv]=now;fa[fu]=now;
			edge[now].pb({fu});
			edge[now].pb({fv});
		}
	}
	dfs(now,0);
//	for(int i=now;i;i--)
//		if(!vis[i])dfs(i,0);
//	n*=2;
	ST();
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);	
//	freopen("lagrange2.in","r",stdin);
	
	cin>>n>>m>>q;int u,v;G.pb({0,0});
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		G.pb({u,v,i});
	}
	kruskal();
	int l,r;
	while(q--)
	{
		cin>>l>>r;
		if(l==r)cout<<0<<endl;
		else
		{
			cout<<query(l+1,r)<<endl;
		}
	}
	return 0;
}