链接 D2. Two Hundred Twenty One (hard version)

题意

给出以个只包含 + + + 和 − - − 的字符串，奇数位为 1 1 1，偶数位为 − 1 -1 −1， + + + 为 1 1 1， − - − 为 − 1 -1 −1，每一位的值 = （ 奇 o r 偶 ） =（奇or偶） =（奇or偶）数位 ∗ （ + o r − ） * （+or-） ∗（+or−）；给出 q q q 个询问，问需要删除几个数才能保证区间内的所有值加起来为 0 0 0；

e a s y − v e r s i o n easy-version easy−version：用前缀和处理，如果 s u m [ r ] − s u m [ l − 1 ] = = 0 sum[r] - sum[l - 1] == 0 sum[r]−sum[l−1]==0 直接输出 0 0 0 次就可以，如果区间里元素个数为奇数，那么可以证明（具体证明可以看cf题解证明）一定存在一个数，删除后保证整个区间为 0 0 0 ，偶数的情况就先删除 l l l ，再按照奇数情况处理。

h a r d − v e r s i o n hard-version hard−version：和简单版本的区别就是要输出删除的位置，稍做分析我们就知道删除一个位置后，后边的和会翻转，所以我们需要找到一个位置 s u m [ r ] − s u m [ x − 1 ] = s u m [ x ] − s u m [ l − 1 ] sum[r] - sum[x - 1] = sum[x] - sum[l-1] sum[r]−sum[x−1]=sum[x]−sum[l−1]，可以得到一个式子 s u m [ r ] + s u m [ l − 1 ] = s u m [ x ] + s u m [ x − 1 ] sum[r] + sum[l-1]=sum[x] + sum[x-1] sum[r]+sum[l−1]=sum[x]+sum[x−1]，这样我们就可以进行二分了，具体看代码qwq

AC代码

e a s y − v e r s i o n easy-version easy−version

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long ll;
const int N = 300010;

int T, n, q;
int a[N]; 

int main()
{
	cin >> T;
	while (T --) {
		cin >> n >> q;
		string s;
		cin >> s;
		for (int i = 0; i < s.size(); i ++) {
			if (s[i] == '-') a[i + 1] = -1;
			else a[i + 1] = 1;
			if ((i + 1) & 1) a[i + 1] *= 1;
			else a[i + 1] *= -1;
		}
		for (int i = 1; i <= n; i ++) {
			a[i] += a[i - 1];
		}
		
		while (q --) {
			int l, r;
			cin >> l >> r;
			if (a[r] - a[l - 1] == 0) cout << 0 << endl;
			else if ((r - l + 1) & 1) cout << 1 << endl;
			else cout << 2 << endl;
		}
	}
}

h a r d − v e r s i o n hard-version hard−version

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long ll;
const int N = 300010;

int T, n, q;
int a[N];
vector<int> v[6 * N];

int main()
{
	cin >> T;
	while (T --) {
		cin >> n >> q;
		string s;
		cin >> s;
		for (int i = 0; i < n; i ++) {
			a[i + 1] = a[i] + ((i & 1) ? 1 : -1) * ((s[i] == '+' ? 1 : -1));
			v[a[i + 1] + a[i] + 2 * n].push_back(i + 1);
		}
		
		while (q --) {
			int l, r;
			cin >> l >> r;
			if (a[r] - a[l - 1] == 0) cout << 0 << endl;
			else if ((r - l + 1) & 1) {
				puts("1");
				int x = a[r] + a[l - 1] + 2 * n;
				int t = *lower_bound(v[x].begin(), v[x].end(), l);
				cout << t << endl;
			}
			else {
				puts("2");
				cout << l << " ";
				int x = a[r] + a[l] + 2 * n;
				int t = *lower_bound(v[x].begin(), v[x].end(), l + 1);
				cout << t << endl;
			}
		}
		
		for (int i = 1; i <= n; i ++) v[a[i] + a[i - 1] + 2 * n].clear();
	}
}