7.7 模拟赛

Day 4

T1. match

Description

在一个长度位 $2n$ 的序列中，有 $n$ 个黑点和白点。你需要将黑白点连线。每个黑点或白点只能连一条。$i$ 和 $j$ 连线起来的代价是 $|i-j|$。求最小代价。

$1\le n\le 10^5$

1s ,512MB

Solution

算是这几天最简单的 T1 了。直接栈模拟和最近的点配对即可。

Code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n;
int a[maxn];
int stac[maxn],tot,ans;
signed main(void){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int i;
	read(n);
	for (i=1;i<=n*2;i++) read(a[i]);
	for (i=1;i<=n*2;i++) {
		if (!tot) stac[++tot]=i;
		else if (a[i]!=a[stac[1]]) ans+=i-stac[tot],tot--;
		else stac[++tot]=i;
	} 
	printf("%lld",ans);
	return 0;
}

T2. photo

Description

$n,m\le 1000$

2s 512MB

Solution

问到连通块个数，容易联想到欧拉平面图定理。$\text{点}-\text{边}+{面}-1=\text{连通块个数}$。

其中面的个数是包含最外面的一个的。

根据启望的线性性，每个分开计算期望。

观察到颜色为黑色的点的连通块只有一个，所以我们统计白色连通块即可。应该是简单的。

Code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 1005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
const int mod=998244353;
inline void add(int &x,int y) {x=(x+(y%mod+mod))%mod;}
int n,m;
int p[maxn][maxn],q[maxn][maxn],sufp[maxn][maxn],sufq[maxn][maxn];
int ans1,ans2,ans3;
inline void solve1(void) {
	int i,j;
	add(ans1,n+m+1);
	for (i=2;i<=n;i++) {
		for (j=2;j<=m;j++) {
			add(ans1,sufp[i][j-1]*sufq[i-1][j]);
		}
	}
}
inline void solve2(void) {
	int i,j;
	for (i=2;i<=n;i++) {
		for (j=2;j<=m;j++) {
			if (j<m) add(ans2,sufp[i][j-1]*sufq[i-1][j]%mod*sufq[i-1][j+1]);
			else add(ans2,sufp[i][j-1]*sufq[i-1][j]);
			if (i<n) add(ans2,sufq[i-1][j]*sufp[i][j-1]%mod*sufp[i+1][j-1]);
			else add(ans2,sufq[i-1][j]*sufp[i][j-1]%mod);
		}
	}
	add(ans2,n+m);
}
inline void solve3(void) {
	int i,j;
	for (i=1;i<=n;i++) sufq[i][m+1]=1;
	for (i=1;i<=m;i++) sufp[n+1][i]=1;
	for (i=2;i<=n;i++) {
		for (j=2;j<=m;j++) {
			add(ans3,sufp[i][j-1]*sufp[i+1][j-1]%mod*sufq[i-1][j]%mod*sufq[i-1][j+1]%mod);
		}
	}
}
signed main(void){
  freopen("photo.in","r",stdin);
  	freopen("photo.out","w",stdout);
	int i,j;
	read(n);read(m);
	for (i=1;i<=n;i++) for (j=1;j<=m;j++) read(p[i][j]);
	for (i=1;i<=n;i++) for (j=1;j<=m;j++) read(q[i][j]);
	for (i=1;i<=n+2;i++) for (j=1;j<=m+2;j++) add(sufp[i][j],sufp[i][j-1]+p[i][j]),add(sufq[i][j],sufq[i-1][j]+q[i][j]);
	solve1();//dian
	solve2();//bian
	solve3();//mian
	printf("%lld\n",(1+ans1-ans2+ans3+mod)%mod);
	return 0;
}

T3. cover

Description

$n,q\le 2\times 10^6,m\le 2\times 10^5$

Solution

考虑先预处理出每个位置为左端点能到达的最右端的位置 $f_i$。用线段树维护是 $O(m\log n)$ 的，只有一次查询，查询的复杂度是 $O(n)$。

以 $(i,f_i)$ 为边建树。查询 $x,y$ 的时候，一个简单的想法是 $x$ 上不断向祖先跳，直到比 $y$ 大。可以用倍增处理，但这样查询的复杂度是 $O(q\log n)$，不是很好过。但是常数小的树剖表现的不错。

其实查询答案的时候，每次从 $x$ 跳到与 $y$ 深度相同的点 $z$，如果 $z<y$ ，则答案为 $deep_y-deep_x+1$，否则为 $deep_y-deep_x$。

离线下来用 dfs 处理。复杂度 $O(m\log n +n +q)$，但是实现比书剖还慢，大概是 vector 的问题。

Code

#include <iostream>
#include <utility>
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 2000005
#define put() putchar('\n')
using namespace std; 
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace RD {
    static unsigned long long splitmix64(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    unsigned long long n, s;
    void init(int N, int S) {
        n = N - 1, s = S;
    }
    pair<int, int> getquery() {
        s = splitmix64(s);
        int l = (s >> 32) % n;
        int r = (s & (~(unsigned)0)) % n;
        if (l > r)
            swap(l, r);
        return pair<int, int>(l + 1, r + 2);
    }
}
int n,m,q,fa[maxn],lg[maxn];
struct yyy{
	int lazy,L;
}f[maxn<<2];
inline void Update1(int l,int r,int rt,int head,int tail,int k) {
	if (head<=l&&r<=tail) return f[rt].lazy=max(f[rt].lazy,k),void();
	int mid=l+r>>1;
	if (head<=mid) Update1(l,mid,rt<<1,head,tail,k);
	if (tail>mid)  Update1(mid+1,r,rt<<1|1,head,tail,k);
}
inline void Update2(int l,int r,int rt,int head,int tail) {
	if (head<=l&&r<=tail) return f[rt].L=max(f[rt].L,tail-l+1),void();
	int mid=l+r>>1;
	if (head<=mid) Update2(l,mid,rt<<1,head,tail);
	if (tail>mid)  Update2(mid+1,r,rt<<1|1,head,tail);
}
inline void Query(int l,int r,int rt,int Max1,int Max2) {
	if (l==r) {
		fa[l]=l+max(max(Max1,f[rt].lazy),max(Max2,f[rt].L));
		return ;
	}
	int mid=l+r>>1;
	Query(l,mid,rt<<1,max(f[rt].lazy,Max1),max(f[rt].L,Max2));
	Query(mid+1,r,rt<<1|1,max(f[rt].lazy,Max1),max(f[rt].L+l-1-mid,Max2+l-1-mid));
}
int Ans,deep[maxn];
vector<int>O[maxn];
int head=1,to[maxn],z[maxn],h[maxn];
inline void add(int x,int y) {
	to[++head]=y;z[head]=h[x];h[x]=head;
}
int stac[maxn],tot;
inline void solve(int x) {
	stac[++tot]=x;
	for (auto y:O[x]) {
		if (stac[deep[y]]<y) Ans^=(deep[x]-deep[y]+1);
		else Ans^=(deep[x]-deep[y]);
	}
	for (int i=h[x];i;i=z[i]) solve(to[i]); 
	tot--;
}
signed main(void) {
//	freopen("2.in","r",stdin);
	freopen("cover.in","r",stdin);
	freopen("cover.out","w",stdout);
	int l,r,x,i,j,s,y,ans;
	pair<int, int> query_content;
	read(n);read(m);read(q);read(s);
	RD::init(n,s);
	for (i=1;i<=m;i++) {
		read(l);read(r);read(x);
		if (r-x>=l) Update1(1,n,1,l,r-x,x);
		if (r-x+1<=r-1) Update2(1,n,1,r-x+1,r-1);
	}
	Query(1,n,1,0,0);
	for (i=n;i>=1;i--) deep[i]=deep[fa[i]]+1;
	for (i=1;i<n;i++) add(fa[i],i);
	while (q--) {
		pair<int, int> query_content = RD::getquery();
		x = query_content.first, y = query_content.second;
		O[x].push_back(y);
	}
	solve(n);
	printf("%d",Ans);
	return 0;
}

T4

Description

$n,q\le 10^5$

5s , 512MB

Solution

考虑二分答案。检验行驶速度的最小值为 $val$ 是否可行。

我们只需要求出， $<val$ 的初始速度的点的升级代价之和，且这些点在 $a,b$ 上。

先不看 $val$ ，我们只需要维护点到根的路径上的代价之和，单点修改，区间查询，并且大概率需要用到树剖，这么做是 3log 的。

转化为 dfs 序，只需要在修改的点对整个子树修，查询就是单点的。这样做是区间修改，单点查询。

$val$ 的限制用主席树即可解决。

$o(n\log n+q\log^2n)$

Code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,q;
struct ed{
	int x,y,v,c,s;
}e[maxn],w[maxn];
vector<ed>O[maxn];
vector<int>to[maxn];
int dfn[maxn],top[maxn],fa[maxn],id[maxn],idnum,deep[maxn],siz[maxn],son[maxn];
inline void dfs1(int x,int pre) {
	int i;siz[x]=1,deep[x]=deep[pre]+1,fa[x]=pre;
	for (auto y:to[x]) if (y^pre) {
		dfs1(y,x);
		siz[x]+=siz[y];
		if (!son[x]||siz[son[x]]<siz[y]) son[x]=y;
	}
}
const int inf=1e9;
inline void dfs2(int x,int pre,int u) {
	top[x]=u;id[x]+=++idnum;
	if (!son[x]) return ;
	dfs2(son[x],x,u);
	for (auto y:to[x]) if (y!=pre&&y!=son[x]) dfs2(y,x,y);
}
inline bool cmp(ed x,ed y) {return x.s<y.s;}
int g[maxn],tot,cnt;
int root[maxn];
struct node{
	int ls,rs,sum;
}f[maxn*40];
inline int Update(int l,int r,int pre,int head,int c) {
	int rt=++cnt;f[rt]=f[pre];f[rt].sum+=c;
	if (l==r) return rt;
	int mid=l+r>>1;
	if (head<=mid) f[rt].ls=Update(l,mid,f[rt].ls,head,c);
	else f[rt].rs=Update(mid+1,r,f[rt].rs,head,c);
	return rt;
}
inline int Query(int l,int r,int rt,int head,int tail) {
	if (!rt) return 0;
	if (head<=l&&r<=tail) return f[rt].sum;
	int mid=l+r>>1,tmp1=0,tmp2=0;
	if (head<=mid) tmp1=Query(l,mid,f[rt].ls,head,tail);
	if (tail>mid)  tmp2=Query(mid+1,r,f[rt].rs,head,tail);
	return tmp1+tmp2;
}
int lca;
namespace seg{
	int f[maxn<<2];
	inline void init(void) {
		memset(f,0x3f,sizeof(f));
	}
	inline void Update(int l,int r,int rt,int head,int w) {
		f[rt]=min(f[rt],w);
		if (l==r) return f[rt]=w,void();
		int mid=l+r>>1;
		if (head<=mid) Update(l,mid,rt<<1,head,w);
		else Update(mid+1,r,rt<<1|1,head,w);
	} 
	inline int Query(int l,int r,int rt,int head,int tail) {
		if (head<=l&&r<=tail) return f[rt];
		int mid=l+r>>1,tmp1=inf,tmp2=inf;
		if (head<=mid) tmp1=Query(l,mid,rt<<1,head,tail);
		if (tail>mid)  tmp2=Query(mid+1,r,rt<<1|1,head,tail);
		return min(tmp1,tmp2);
	}
	inline int query(int x,int y) {
		int ans=inf;
		while (top[x]^top[y]) {
			if (deep[top[x]]<deep[top[y]]) swap(x,y);
			int tmp=Query(1ll,n,1ll,id[top[x]],id[x]);ans=min(ans,tmp);
			x=fa[top[x]];
		}
		if (deep[x]<deep[y]) swap(x,y);
		if (x^y) {
			ans=min(ans,Query(1ll,n,1ll,id[y]+1,id[x]));
		}
		lca=y;
		return ans;
	}
} 
inline bool check(int val,int x,int y,int z) {
	val--;
	int ans=0;
	ans=Query(1,n,root[val],1,id[x])+Query(1,n,root[val],1,id[y])-Query(1,n,root[val],1,id[lca])*2;
	return ans<=z;
}
signed main(void){
  	freopen("arozustan.in","r",stdin);
	freopen("arozustan.out","w",stdout);
	int i,x,y,z;
	read(n);
	for (i=1;i<n;i++) {
		read(e[i].x),read(e[i].y),read(e[i].v),read(e[i].c),read(e[i].s);
		g[++tot]=e[i].v,g[++tot]=e[i].s;
		to[e[i].x].push_back(e[i].y);
		to[e[i].y].push_back(e[i].x);
	}
	sort(g+1,g+1+tot);
	tot=unique(g+1,g+1+tot)-g-1;
	seg::init();
	for (i=1;i<n;i++) e[i].v=lower_bound(g+1,g+1+tot,e[i].v)-g,e[i].s=lower_bound(g+1,g+1+tot,e[i].s)-g;//,gdb(i,e[i].x,e[i].y,e[i].v,e[i].s);
	dfs1(1,0);
	dfs2(1,0,1);
	for (i=1;i<n;i++) if (deep[e[i].x]<deep[e[i].y]) w[e[i].y]=e[i];else w[e[i].x]=e[i];
	for (i=1;i<=n;i++) if (w[i].x) {
		w[i].x=i,O[w[i].v].push_back(w[i]);
		seg::Update(1,n,1,id[w[i].x],w[i].s);
	}
	for (i=1;i<=tot;i++) {
		root[i]=root[i-1];
		for (auto tmp:O[i]) {
			root[i]=Update(1,n,root[i],id[tmp.x],tmp.c);
			if (id[tmp.x]+siz[tmp.x]<=n) root[i]=Update(1,n,root[i],id[tmp.x]+siz[tmp.x],-tmp.c);
 		}
	}
	read(q);
	while (q--) {
		read(x),read(y),read(z);
		int l=0,r=seg::query(x,y)+1,mid;
		while (l+1<r) {
			mid=l+r>>1;
			if (check(mid,x,y,z)) l=mid;
			else r=mid;
		}
		printf("%lld\n",g[l]);
	}
	return 0;
}