Solution for CEOI2022()

\(\cal T_1\) Abracadabra

Description

给定长度为 \(N\)(保证为偶数)的排列,每次操作将排列对半分,然后做归并。\(Q\) 次询问,求 \(t\) 次操作后的第 \(i\) 张牌。

\(N\leqslant 2\cdot 10^5,Q\leqslant 10^6,0\leqslant t\leqslant 10^9\).

Solution

一些闲话:黑心糖赛高!

可以发现归并到 \(a_i\) 时,它后面一段小于 \(a_i\) 的数列一定会紧跟着它被归并,我们不妨这样划分:先令 \(a_1\) 为第一组的 lead,领导后面 \(<a_1\) 的极长连续段,再令后面紧跟的数字为 lead……依此类推。

考察 \(\text{mid}=n/2+1\),如果 \(\rm mid\) 和 \({\rm mid}-1\) 不在一个段内,这个序列不会再发生变化;反之,可以将它们所在的段按 \(\text{mid}-1\) 和 \(\rm mid\) 的分界隔开。容易发现分割操作至多不超过 \(n\) 次。维护可以用树状数组之类的东西,以权值为下标,维护以这个权值为 lead 的段长。用这个可以二分出第 \(k\) 个位置属于哪个段,也可以确定它的权值,因为只涉及段的分裂操作,所以甚至不用改变原数列。复杂度 \(\mathcal O(n\log n)\).

Code

彩蛋:打开这题的 testdata 发现后缀全是 、 之类的鬼畜玩意,足足有八十组。于是学习了一下怎么用 \(\mathcal{C}\text{++}\) 进行替换,最后发现根本没有学懂 .

.1a
.2b
freopen()
# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T> 
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while(!isdigit(s=getchar())) f|=(s=='-');
	for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
	return f? -x: x;
}
template <class T>
inline void write(T x) {
	static int writ[50], w_tp=0;
	if(x<0) putchar('-'), x=-x;
	do writ[++w_tp]=x-x/10*10, x/=10; while(x);
	while(putchar(writ[w_tp--]^48), w_tp);
}

# include <vector>
# include <iostream>
using namespace std;
typedef pair <int,int> par;

const int MAXN = 2e5+5;
const int MAXM = 1e6+5;

vector <par> q[MAXN]; int ans[MAXM];
int n, Q, a[MAXN], stk[MAXN], tp, nxt[MAXN], pos[MAXN];

namespace fwt {
	int c[MAXN];
	int lowbit(int x) { return x&-x; }
	void add(int x,int k) {
		while(x<=n) c[x]+=k, x+=lowbit(x);
	}
	int ask(int x,int r=0) {
		for(; x; x-=lowbit(x)) r+=c[x]; return r;
	}
	int kth(int& k,int r=0) {
		for(int i=17; i>=0; --i) 
			if(r+(1<<i)<=n && c[r+(1<<i)]<k)
				k -= c[r=r+(1<<i)]; return r+1;
	}
}

int main() {
	n=read(9), Q=read(9);
	for(int i=1;i<=n;++i) pos[a[i]=read(9)]=i;
	for(int i=n; i; --i) {
		while(tp && a[i]>a[stk[tp]]) --tp;
		if(tp) nxt[i] = stk[tp];
		else nxt[i] = n+1; stk[++tp]=i;
	}
	for(int i=1;i<=n;i=nxt[i]) fwt::add(a[i],nxt[i]-i);
	for(int i=1;i<=Q;++i) {
		int t=min(read(9),n), x=read(9);
		q[t].emplace_back(make_pair(x,i));
	} 
	for(int t=0; t<=n; ++t) {
		for(auto& i:q[t]) {
			int lead = fwt::kth(i.first);
			ans[i.second] = a[pos[lead]+i.first-1];
		} int mid = (n>>1)+1, lead = fwt::kth(mid); 
		if(mid==1) continue;
		int all = fwt::ask(lead)-fwt::ask(lead-1), ed=pos[lead]+all;
		fwt::add(lead, -(all-(mid-1)));
		for(int i=pos[lead]+mid-1; i<ed; i=nxt[i])
			fwt::add(a[i], min(ed,nxt[i])-i);
	}
	for(int i=1;i<=Q;++i) print(ans[i],'\n');
	return 0;
}

\(\cal T_2\) Homework

Description

给定一个由 \(\min,\max\) 构成的表达式(这里的 \(\min,\max\) 都视作二元运算),其中表达式里面共 \(N\) 个参数。填入 \(1\) 到 \(N\) 这些数,共有 \(N!\) 种方案,那么 \(N!\) 种填数方案最后的运算结果有多少种。

\(N\leqslant 10^6\).

Solution

就是 \(\text{CF1153D Serval and Rooted Tree}\).

Code

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T> 
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while(!isdigit(s=getchar())) f|=(s=='-');
	for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
	return f? -x: x;
}
template <class T>
inline void write(T x) {
	static int writ[50], w_tp=0;
	if(x<0) putchar('-'), x=-x;
	do writ[++w_tp]=x-x/10*10, x/=10; while(x);
	while(putchar(writ[w_tp--]^48), w_tp);
}

# include <cstring>
# include <iostream>
using namespace std;

const int MAXN = 7e6+5;

char s[MAXN]; bool d[MAXN]; int dp[MAXN][2];
int len, stk[MAXN], tp, son[MAXN][2], n;

void dfs(int u) { 
	if(!son[u][0]) return; dp[u][d[u]^1]=0;
	for(int i=0, v=son[u][i]; i<2; v=son[u][++i]) {
		dfs(v); dp[u][d[u]^1] += dp[v][d[u]^1];
		dp[u][d[u]] = min(dp[u][d[u]], dp[v][d[u]]);
	}
}

int main() {
	scanf("%s",s+1), len=strlen(s+1);
	for(int i=1; i<=len; ++i) {
		if(s[i]=='m') stk[++tp]=++n,
			d[n] = (s[i+1]=='i'?0:1), i+=3;
		else if(s[i]==')') son[stk[tp-1]][1]=stk[tp], --tp;
		else if(s[i]==',') son[stk[tp-1]][0]=stk[tp], --tp;
		else stk[++tp]=++n;
	} int all=0;
	for(int i=1;i<=n;++i) 
		if(son[i][0]) dp[i][0]=dp[i][1]=n+1; 
		else dp[i][0]=dp[i][1]=1, ++ all;
	dfs(1); print(all-dp[1][0]-dp[1][1]+2,'\n');
	return 0;
}

\(\cal T_3\) Prize

Description

交互题。两棵 \(N\) 个点的有根树,树的形态给出,但边权未知。需要预先选出一个大小为 \(K\) 的点集 \(S_K\),需要注意的是,\(K\) 是题目已经给定的值。

然后你可以至多进行 \(Q\) 次询问 ,交互库回答 \(a, b\) 在两棵树上离 \(\operatorname{lca}(a, b)\) 的距离(分别给出,也就是说交互库需要回答 \(4\) 个数)。

? a b

最后交换库反过来给你两个参数 \(p,q\in S_K\),询问 \(p, q\) 在两棵树上(分别)的距离。询问 \(T\) 次。

\(N\leqslant 10^6,Q=K-1,0<w_i\leqslant 2000,2\leqslant K\leqslant 10^5,T\leqslant \min\{K^2,10^5\}\).

Solution

一些闲话:因为 Online Mirror Contest 时间已经过了,而且这题要用交互库,所以测不了,那么不写代码便是理所应当的 。可是为了登上那个网站搞了半天的 vpn,最后发现测不了还是很难受啊!

那就浅浅口胡一下吧!先假设点集中 \(K\) 个点是任选的,建出一棵关于 \(S_K\) 的虚树辅助思考,我们需要在 \(Q=K-1\) 次询问后得到这棵树的所有边权。事实上只用按先序遍历询问点 \((p_1,p_2),(p_2,p_3),\dots,(p_{k-1},p_k)\) 即可。

回到原题。第一棵树直接从根开始跑 dfs,将遍历到的前 \(K\) 个点加入集合;第二棵树沿用上文的方法即可。第二棵树的边权是容易复原的,我们考虑如何复原第一棵树。不妨将条件变得更劣,假设每次只给出 \(a,b\) 之间的距离,那么我们就得到了 \(K-1\) 个关于边权的方程,同时我们惊喜地发现未知数个数也是 \(K-1\) 个!另外也容易发现这 \(K-1\) 个方程是线性不相关的,因为线性相关就意味着有环,这与边条数是矛盾的。

哦,那我们就可以用 \(\mathcal O(K^3)\) 的优秀算法来做这道题辣!\(K\leqslant 10^5\) 啊,那没事了。

事实上给定 \(a,b\) 到 \(\text{lca}(a,b)\) 的距离是很有必要的。首先 \(K-1\) 组 \(a,b\) 中,至少存在一组的 \(\rm lca\) 是根节点,于是可以直接得到 \(a,b\) 的深度。利用这个深度大概可以直接枚举包含 \(a,b\) 的询问,求出另一个点的深度。于是可以做到 \(\mathcal O((N+K)\log N)\).

Code

为什么明知道没有代码你还要点开呢?
————————

\(\cal T_1\) Abracadabra

Description

给定长度为 \(N\)(保证为偶数)的排列,每次操作将排列对半分,然后做归并。\(Q\) 次询问,求 \(t\) 次操作后的第 \(i\) 张牌。

\(N\leqslant 2\cdot 10^5,Q\leqslant 10^6,0\leqslant t\leqslant 10^9\).

Solution

一些闲话:黑心糖赛高!

可以发现归并到 \(a_i\) 时,它后面一段小于 \(a_i\) 的数列一定会紧跟着它被归并,我们不妨这样划分:先令 \(a_1\) 为第一组的 lead,领导后面 \(<a_1\) 的极长连续段,再令后面紧跟的数字为 lead……依此类推。

考察 \(\text{mid}=n/2+1\),如果 \(\rm mid\) 和 \({\rm mid}-1\) 不在一个段内,这个序列不会再发生变化;反之,可以将它们所在的段按 \(\text{mid}-1\) 和 \(\rm mid\) 的分界隔开。容易发现分割操作至多不超过 \(n\) 次。维护可以用树状数组之类的东西,以权值为下标,维护以这个权值为 lead 的段长。用这个可以二分出第 \(k\) 个位置属于哪个段,也可以确定它的权值,因为只涉及段的分裂操作,所以甚至不用改变原数列。复杂度 \(\mathcal O(n\log n)\).

Code

彩蛋:打开这题的 testdata 发现后缀全是 、 之类的鬼畜玩意,足足有八十组。于是学习了一下怎么用 \(\mathcal{C}\text{++}\) 进行替换,最后发现根本没有学懂 .

.1a
.2b
freopen()
# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T> 
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while(!isdigit(s=getchar())) f|=(s=='-');
	for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
	return f? -x: x;
}
template <class T>
inline void write(T x) {
	static int writ[50], w_tp=0;
	if(x<0) putchar('-'), x=-x;
	do writ[++w_tp]=x-x/10*10, x/=10; while(x);
	while(putchar(writ[w_tp--]^48), w_tp);
}

# include <vector>
# include <iostream>
using namespace std;
typedef pair <int,int> par;

const int MAXN = 2e5+5;
const int MAXM = 1e6+5;

vector <par> q[MAXN]; int ans[MAXM];
int n, Q, a[MAXN], stk[MAXN], tp, nxt[MAXN], pos[MAXN];

namespace fwt {
	int c[MAXN];
	int lowbit(int x) { return x&-x; }
	void add(int x,int k) {
		while(x<=n) c[x]+=k, x+=lowbit(x);
	}
	int ask(int x,int r=0) {
		for(; x; x-=lowbit(x)) r+=c[x]; return r;
	}
	int kth(int& k,int r=0) {
		for(int i=17; i>=0; --i) 
			if(r+(1<<i)<=n && c[r+(1<<i)]<k)
				k -= c[r=r+(1<<i)]; return r+1;
	}
}

int main() {
	n=read(9), Q=read(9);
	for(int i=1;i<=n;++i) pos[a[i]=read(9)]=i;
	for(int i=n; i; --i) {
		while(tp && a[i]>a[stk[tp]]) --tp;
		if(tp) nxt[i] = stk[tp];
		else nxt[i] = n+1; stk[++tp]=i;
	}
	for(int i=1;i<=n;i=nxt[i]) fwt::add(a[i],nxt[i]-i);
	for(int i=1;i<=Q;++i) {
		int t=min(read(9),n), x=read(9);
		q[t].emplace_back(make_pair(x,i));
	} 
	for(int t=0; t<=n; ++t) {
		for(auto& i:q[t]) {
			int lead = fwt::kth(i.first);
			ans[i.second] = a[pos[lead]+i.first-1];
		} int mid = (n>>1)+1, lead = fwt::kth(mid); 
		if(mid==1) continue;
		int all = fwt::ask(lead)-fwt::ask(lead-1), ed=pos[lead]+all;
		fwt::add(lead, -(all-(mid-1)));
		for(int i=pos[lead]+mid-1; i<ed; i=nxt[i])
			fwt::add(a[i], min(ed,nxt[i])-i);
	}
	for(int i=1;i<=Q;++i) print(ans[i],'\n');
	return 0;
}

\(\cal T_2\) Homework

Description

给定一个由 \(\min,\max\) 构成的表达式(这里的 \(\min,\max\) 都视作二元运算),其中表达式里面共 \(N\) 个参数。填入 \(1\) 到 \(N\) 这些数,共有 \(N!\) 种方案,那么 \(N!\) 种填数方案最后的运算结果有多少种。

\(N\leqslant 10^6\).

Solution

就是 \(\text{CF1153D Serval and Rooted Tree}\).

Code

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T> 
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while(!isdigit(s=getchar())) f|=(s=='-');
	for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
	return f? -x: x;
}
template <class T>
inline void write(T x) {
	static int writ[50], w_tp=0;
	if(x<0) putchar('-'), x=-x;
	do writ[++w_tp]=x-x/10*10, x/=10; while(x);
	while(putchar(writ[w_tp--]^48), w_tp);
}

# include <cstring>
# include <iostream>
using namespace std;

const int MAXN = 7e6+5;

char s[MAXN]; bool d[MAXN]; int dp[MAXN][2];
int len, stk[MAXN], tp, son[MAXN][2], n;

void dfs(int u) { 
	if(!son[u][0]) return; dp[u][d[u]^1]=0;
	for(int i=0, v=son[u][i]; i<2; v=son[u][++i]) {
		dfs(v); dp[u][d[u]^1] += dp[v][d[u]^1];
		dp[u][d[u]] = min(dp[u][d[u]], dp[v][d[u]]);
	}
}

int main() {
	scanf("%s",s+1), len=strlen(s+1);
	for(int i=1; i<=len; ++i) {
		if(s[i]=='m') stk[++tp]=++n,
			d[n] = (s[i+1]=='i'?0:1), i+=3;
		else if(s[i]==')') son[stk[tp-1]][1]=stk[tp], --tp;
		else if(s[i]==',') son[stk[tp-1]][0]=stk[tp], --tp;
		else stk[++tp]=++n;
	} int all=0;
	for(int i=1;i<=n;++i) 
		if(son[i][0]) dp[i][0]=dp[i][1]=n+1; 
		else dp[i][0]=dp[i][1]=1, ++ all;
	dfs(1); print(all-dp[1][0]-dp[1][1]+2,'\n');
	return 0;
}

\(\cal T_3\) Prize

Description

交互题。两棵 \(N\) 个点的有根树,树的形态给出,但边权未知。需要预先选出一个大小为 \(K\) 的点集 \(S_K\),需要注意的是,\(K\) 是题目已经给定的值。

然后你可以至多进行 \(Q\) 次询问 ,交互库回答 \(a, b\) 在两棵树上离 \(\operatorname{lca}(a, b)\) 的距离(分别给出,也就是说交互库需要回答 \(4\) 个数)。

? a b

最后交换库反过来给你两个参数 \(p,q\in S_K\),询问 \(p, q\) 在两棵树上(分别)的距离。询问 \(T\) 次。

\(N\leqslant 10^6,Q=K-1,0<w_i\leqslant 2000,2\leqslant K\leqslant 10^5,T\leqslant \min\{K^2,10^5\}\).

Solution

一些闲话:因为 Online Mirror Contest 时间已经过了,而且这题要用交互库,所以测不了,那么不写代码便是理所应当的 。可是为了登上那个网站搞了半天的 vpn,最后发现测不了还是很难受啊!

那就浅浅口胡一下吧!先假设点集中 \(K\) 个点是任选的,建出一棵关于 \(S_K\) 的虚树辅助思考,我们需要在 \(Q=K-1\) 次询问后得到这棵树的所有边权。事实上只用按先序遍历询问点 \((p_1,p_2),(p_2,p_3),\dots,(p_{k-1},p_k)\) 即可。

回到原题。第一棵树直接从根开始跑 dfs,将遍历到的前 \(K\) 个点加入集合;第二棵树沿用上文的方法即可。第二棵树的边权是容易复原的,我们考虑如何复原第一棵树。不妨将条件变得更劣,假设每次只给出 \(a,b\) 之间的距离,那么我们就得到了 \(K-1\) 个关于边权的方程,同时我们惊喜地发现未知数个数也是 \(K-1\) 个!另外也容易发现这 \(K-1\) 个方程是线性不相关的,因为线性相关就意味着有环,这与边条数是矛盾的。

哦,那我们就可以用 \(\mathcal O(K^3)\) 的优秀算法来做这道题辣!\(K\leqslant 10^5\) 啊,那没事了。

事实上给定 \(a,b\) 到 \(\text{lca}(a,b)\) 的距离是很有必要的。首先 \(K-1\) 组 \(a,b\) 中,至少存在一组的 \(\rm lca\) 是根节点,于是可以直接得到 \(a,b\) 的深度。利用这个深度大概可以直接枚举包含 \(a,b\) 的询问,求出另一个点的深度。于是可以做到 \(\mathcal O((N+K)\log N)\).

Code

为什么明知道没有代码你还要点开呢?