Multi school provincial selection simulation 7

Passing Zhongdan

meaning of the title

Give you a string \ (s \), each time you ask if \ (s[l:r] \) can be worthy of Dan, and a string can be worthy of Dan, if and only if you can traverse each position of this substring through several walks. A walk is to move from a point \ (i \) to a different point \ (j \), so that the path is a palindrome string.

Problem solution

We found that if there is a palindrome string with a length of three, then it must be OK. This is obvious.

Then it is found that the palindrome string with even length can cover this interval.

Then, it is found that for covering a point, we only need to consider the shortest even palindrome string with him as the endpoint. We might as well set the length as \ (L_i \) and \ (R_i \).

Then for the case of \ (l\in (i-L_i+1,i] \) and \ (r\in [i,i+R_i-1) \), this \ (I \) must not be overwritten.

Then it is found that this is a matrix plus a single point query and a scan line.

#include <bits/stdc++.h>
using std::pair;
using std::set;
using std::vector;
const int MAXN = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 998244353, G = 3, MOD2 = 1e9 + 7, G2 = 7;
template<typename T>
inline T min(const T &x, const T &y) {
	return x < y ? x : y;
}
template<typename T>
inline T max(const T &x, const T &y) {
	return x > y ? x : y;
}
auto Mod = [] (int x) -> int {
	if (x < 0) {
		return x + MOD;
	}
	else if (x >= MOD) {
		return x - MOD;
	}
	else {
		return x;
	}
};
using std::cin;
using std::cout;
struct Line {
	int l, r, h, val;
} e[MAXN * 2];
pair<pair<int, int>, int> q[MAXN];
set<int> val;
vector<int> v[MAXN];
int N, Q, L[MAXN], R[MAXN], sum[MAXN], sc[MAXN], ANS[MAXN], H1[MAXN], H2[MAXN], pw[MAXN], H12[MAXN], H22[MAXN], pw2[MAXN];
char s[MAXN];
inline void add(int a, int b) {
	for (int i = a; i <= N; i += i & -i) {
		sc[i] += b;
	}
	return;
}
inline int qry(int pos) {
	int ret = 0;
	for (int i = pos; i; i -= i & -i) {
		ret += sc[i];
	}
	return ret;
}
int main() {
	freopen("pass.in", "r", stdin);
	freopen("pass.out", "w", stdout);
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	cin >> N >> s + 1 >> Q;
	pw[0] = 1;
	pw2[0] = 1;
	for (int i = 1; i <= N; ++i) {
		L[i] = R[i] = INF;
		H12[i] = ((long long) H12[i - 1] * G2 + s[i]) % MOD2;
		H1[i] = ((long long) H1[i - 1] * G + s[i]) % MOD;
		pw[i] = (long long) pw[i - 1] * G % MOD;
		pw2[i] = (long long) pw2[i - 1] * G2 % MOD2;
	}
	for (int i = N; i; --i) {
		H22[i] = ((long long) H22[i + 1] * G2 + s[i]) % MOD2;
		H2[i] = ((long long) H2[i + 1] * G + s[i]) % MOD;
	}
	auto h1 = [&] (int l, int r) -> int {
		return Mod(H1[r] - (long long) H1[l - 1] * pw[r - l + 1] % MOD);
	};
	auto h2 = [&] (int l, int r) -> int {
		return Mod(H2[l] - (long long) H2[r + 1] * pw[r - l + 1] % MOD);
	};
	auto h12 = [&] (int l, int r) -> int {
		return (H12[r] - (long long) H12[l - 1] * pw2[r - l + 1] % MOD2 + MOD2) % MOD2;
	};
	auto h22 = [&] (int l, int r) -> int {
		return (H22[l] - (long long) H22[r + 1] * pw2[r - l + 1] % MOD2 + MOD2) % MOD2;
	};
	for (int i = 1; i < N; ++i) {
		int l = 1, r = min(i, N - i), ret = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (h1(i - mid + 1, i + mid) == h2(i - mid + 1, i + mid) && h12(i - mid + 1, i + mid) == h22(i - mid + 1, i + mid)) {
				ret = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
		if (~ret) {
			v[i - ret + 1].push_back(i);
			v[i + ret + 1].push_back(-i);
		}
	}
	for (int i = 1; i <= N; ++i) {
		for (auto &j: v[i]) {
			if (j < 0) {
				val.erase(-j);
			}
			else {
				val.insert(j);
			}
		}
		auto it = val.lower_bound(i);
		if (it != val.end()) {
			R[i] = 2 * (*it - i + 1);
		}
		if (it != val.begin()) {
			--it;
			L[i] = 2 * (i - *it);
		}
	}
	for (int i = 2; i < N; ++i) {
		sum[i] = sum[i - 1] + (s[i - 1] == s[i + 1]);
	}
	for (int i = 1; i <= N; ++i) {
		int ql = max(1, i - L[i] + 2), qr = min(i + R[i] - 2, N);
		e[2 * i - 1] = {i, qr, ql, 1};
		e[2 * i] = {i, qr, i + 1, -1};
	}
	std::sort(e + 1, e + 1 + 2 * N, [&] (const Line &a, const Line &b) {
		return a.h < b.h;
	});
	for (int i = 1; i <= Q; ++i) {
		cin >> q[i].first.first >> q[i].first.second;
		q[i].second = i;
	}
	std::sort(q + 1, q + 1 + Q);
	for (int i = 1, j = 1; i <= Q; ++i) {
		while (j <= 2 * N && e[j].h <= q[i].first.first) {
			add(e[j].l, e[j].val);
			add(e[j].r + 1, -e[j].val);
			++j;
		}
		if (q[i].first.first != q[i].first.second) {
			if (sum[q[i].first.second - 1] - sum[q[i].first.first]) {
				ANS[q[i].second] = 1;
			}
			else {
				ANS[q[i].second] = !qry(q[i].first.second);
			}
		}
	}
	// for (int i = 1; i <= N; ++i) {
	// 	cout << L[i] << ' ' << R[i] << '\n';
	// }
	for (int i = 1; i <= Q; ++i) {
		cout << ANS[i];
	}
	return 0;
}

Worship the great pill

meaning of the title

There are \ (n \) class points \ (A \) and \ (m \) class points \ (B \), and then they have their own attributes \ (a_i \) or \ (b_i \) respectively, which meet the requirements that \ (A \) class points are connected to \ (B \) class points of \ (1\sim a_i \), and \ (B \) class points are connected to \ (A \) class points of \ (1\sim b_i \). On this graph, you should select A ring each time, and then there is an upper limit on the number of points, Ask how many rings you can choose at most.

Problem solution

First, we can find that a worship path is actually a binary ring, because if it is larger than the binary ring, it might as well be \ (A1 \ rightarrow B1 \ rightarrow A2 \ rightarrow B2 \ rightarrow A1 \).

Let \ (A1 < A2 \), then there should be \ (A1 < A2 < B [B1] \), then it is certain that a binary ring of \ (A1,B1 \) can be formed.

So since it's a binary ring, it's similar to bipartite graph matching. Let's consider running a network flow. That's a lot of points.

Next, consider simulating the maximum flow.

Think about it and find that if we map this point to A two-dimensional plane rectangular coordinate system, the point in \ (A \) is mapped to \ ((i,a_i) \), and then the point in \ (B \) is mapped to \ ((b_i,i) \), and then consider starting from right to left in the part of \ (A \). Each time, we always select the legal \ (y \) largest \ (B \) point.

Using this method, we are considering how to expand. It is found that it is impossible to retreat from the previous operation, and then run directly.

#include <bits/stdc++.h>
using std::pair;
using std::set;
using std::vector;
const int MAXN = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 998244353, G = 3, MOD2 = 1e9 + 7, G2 = 7;
template<typename T>
inline T min(const T &x, const T &y) {
	return x < y ? x : y;
}
template<typename T>
inline T max(const T &x, const T &y) {
	return x > y ? x : y;
}
auto Mod = [] (int x) -> int {
	if (x < 0) {
		return x + MOD;
	}
	else if (x >= MOD) {
		return x - MOD;
	}
	else {
		return x;
	}
};
using std::cin;
using std::cout;
struct Line {
	int l, r, h, val;
} e[MAXN * 2];
pair<pair<int, int>, int> q[MAXN];
set<int> val;
vector<int> v[MAXN];
int N, Q, L[MAXN], R[MAXN], sum[MAXN], sc[MAXN], ANS[MAXN], H1[MAXN], H2[MAXN], pw[MAXN], H12[MAXN], H22[MAXN], pw2[MAXN];
char s[MAXN];
inline void add(int a, int b) {
	for (int i = a; i <= N; i += i & -i) {
		sc[i] += b;
	}
	return;
}
inline int qry(int pos) {
	int ret = 0;
	for (int i = pos; i; i -= i & -i) {
		ret += sc[i];
	}
	return ret;
}
int main() {
	freopen("pass.in", "r", stdin);
	freopen("pass.out", "w", stdout);
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	cin >> N >> s + 1 >> Q;
	pw[0] = 1;
	pw2[0] = 1;
	for (int i = 1; i <= N; ++i) {
		L[i] = R[i] = INF;
		H12[i] = ((long long) H12[i - 1] * G2 + s[i]) % MOD2;
		H1[i] = ((long long) H1[i - 1] * G + s[i]) % MOD;
		pw[i] = (long long) pw[i - 1] * G % MOD;
		pw2[i] = (long long) pw2[i - 1] * G2 % MOD2;
	}
	for (int i = N; i; --i) {
		H22[i] = ((long long) H22[i + 1] * G2 + s[i]) % MOD2;
		H2[i] = ((long long) H2[i + 1] * G + s[i]) % MOD;
	}
	auto h1 = [&] (int l, int r) -> int {
		return Mod(H1[r] - (long long) H1[l - 1] * pw[r - l + 1] % MOD);
	};
	auto h2 = [&] (int l, int r) -> int {
		return Mod(H2[l] - (long long) H2[r + 1] * pw[r - l + 1] % MOD);
	};
	auto h12 = [&] (int l, int r) -> int {
		return (H12[r] - (long long) H12[l - 1] * pw2[r - l + 1] % MOD2 + MOD2) % MOD2;
	};
	auto h22 = [&] (int l, int r) -> int {
		return (H22[l] - (long long) H22[r + 1] * pw2[r - l + 1] % MOD2 + MOD2) % MOD2;
	};
	for (int i = 1; i < N; ++i) {
		int l = 1, r = min(i, N - i), ret = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (h1(i - mid + 1, i + mid) == h2(i - mid + 1, i + mid) && h12(i - mid + 1, i + mid) == h22(i - mid + 1, i + mid)) {
				ret = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
		if (~ret) {
			v[i - ret + 1].push_back(i);
			v[i + ret + 1].push_back(-i);
		}
	}
	for (int i = 1; i <= N; ++i) {
		for (auto &j: v[i]) {
			if (j < 0) {
				val.erase(-j);
			}
			else {
				val.insert(j);
			}
		}
		auto it = val.lower_bound(i);
		if (it != val.end()) {
			R[i] = 2 * (*it - i + 1);
		}
		if (it != val.begin()) {
			--it;
			L[i] = 2 * (i - *it);
		}
	}
	for (int i = 2; i < N; ++i) {
		sum[i] = sum[i - 1] + (s[i - 1] == s[i + 1]);
	}
	for (int i = 1; i <= N; ++i) {
		int ql = max(1, i - L[i] + 2), qr = min(i + R[i] - 2, N);
		e[2 * i - 1] = {i, qr, ql, 1};
		e[2 * i] = {i, qr, i + 1, -1};
	}
	std::sort(e + 1, e + 1 + 2 * N, [&] (const Line &a, const Line &b) {
		return a.h < b.h;
	});
	for (int i = 1; i <= Q; ++i) {
		cin >> q[i].first.first >> q[i].first.second;
		q[i].second = i;
	}
	std::sort(q + 1, q + 1 + Q);
	for (int i = 1, j = 1; i <= Q; ++i) {
		while (j <= 2 * N && e[j].h <= q[i].first.first) {
			add(e[j].l, e[j].val);
			add(e[j].r + 1, -e[j].val);
			++j;
		}
		if (q[i].first.first != q[i].first.second) {
			if (sum[q[i].first.second - 1] - sum[q[i].first.first]) {
				ANS[q[i].second] = 1;
			}
			else {
				ANS[q[i].second] = !qry(q[i].first.second);
			}
		}
	}
	// for (int i = 1; i <= N; ++i) {
	// 	cout << L[i] << ' ' << R[i] << '\n';
	// }
	for (int i = 1; i <= Q; ++i) {
		cout << ANS[i];
	}
	return 0;
}