Codechef 2500+ problems

TAEDITOR

题目描述

你需要维护一个字符串，支持插入字符串和查询子串。

大体思路

题解给的是 BIT。

然而事实上，这题相当于维护一个序列，支持区间插入和区间查询。

这就是文艺平衡树的板子题。实现时使用 fhqTreap，区间插入的建树利用笛卡尔树性质可以 \(O(n)\) 实现，区间查询就是 split 之后中序遍历。

时间复杂度 \(O(n\log n)\)。

但这样代码其实很长。

对于字符串的题，我们要敢于暴力。于是我用 STL::string 直接暴力然后过了。

int Q, x;
string s, op, str;
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> Q;
	while(Q --) {
		cin >> op >> x;
		if(op[0] == '+') {
			cin >> str;
			s.insert(x, str);
		} else {
			int len;
			cin >> len;
			cout << s.substr(x - 1, len) << "\n";
		}
	}
	
	return 0;
}

MEOW1234

题目描述

有一个 \(10^5\) 行和 \(10^5\) 列的网格（行列编号均为 \(1\) 到 \(10^5\)）。\(N\) 个不同的格子被标记了（编号为 \(1\) 到 \(N\)）。第 \(i\) 个被标记的格子是 \((x_i,y_i)\)。

一个格子的集合是合适的如果满足：

• 所有被标记的格子都属于这个集合
• 对于任意一对属于集合的格子 \(A,B\)，它们之间存在一条路径长度等于 \(|x_A-x_B|+|y_A-y_B|\)，且该路径只包含集合中的点。路径中每一对相邻的格子必须有共同的边。

你需要求出最小的合适的集合的大小以及个数。由于合适的集合的个数巨大，输出对 \(10^9+7\) 取模。