Two Hundred Twenty One (hard version)（思维/前缀和/二分）

题目 题意：符串的贡献为正，偶数位上的字符串贡献为逆（+符号做-贡献，-符号做+贡献），字符串的权值为字符串上所有位的贡献和。有若干次查询，每次查询区间[l,r]的字符串，需要删掉最少多少字符，才能使该子串的权值刚好为0。要求把要删除的位置下标输出。 官方题解 思路：同easy version。现在多出了要输出对应的下标，由于b数组是有序的，我们可以直接二分查找下标。

#include
using namespace std;
const int maxn = 300010; 
typedef long long ll;

char s[maxn];
int n, q, l, r;
int a[maxn];
int pre[maxn];
void init() {
	pre[0] = 0;
	for (int i = 1; i  r) return 0;
	int sum = pre[r] - pre[l-1];
	if (l % 2 == 0) sum = -sum;
	return sum;
}
int check(int l, int r, int m) {// 计算删了下标m后的区间[l,r]的和 
	if (!((l & 1) ^ (m & 1))) {// 判断l和m下标的奇偶性是否相同 
		return get_sum(l, m - 1) + get_sum(m + 1, r);
	}
	return get_sum(l, m - 1) - get_sum(m + 1, r);
}
int find1(int L, int R) {
	int l = L, r = R;
	while (l