优化网站推广网站/seo优化推广教程

题意

你有一个长度为$n$，且仅包含$1$和$-1$的序列$a$，即a[i]∈{−1,1}a[i] \in \{-1,1\}a[i]∈{−1,1}

给你一个数$Q$，表示$Q$次询问

每次询问给定两个数$l,r$，要找到$[l,r]$内最少删除多少个数，使得其余数拼接后满足

${\sum }_{i=1}^n(-1{)}^{i-1}\ast a[i]=0$ 或者${\sum }_{i=1}^n(-1{)}^i\ast a[i]=0$

思路

因为要求区间内数的加权和为$0$，所以要么两种条件都符合，要么都不符合

用$sum[i]$表示$a[i]$的前缀加权和

若$sum[r]-sum[l-1]==0$ 不用删除数，直接输出即可

否则当区间长度为奇数时，只需要删除一个数（后面$tips$为证明），假设删除的数位置为$pos$

即有$sum[r]-sum[pos]==sum[pos-1]-sum[l-1]$

移项后即为$sum[r]+sum[l-1]==sum[pos]+sum[pos-1]$ ，$pos\in [1,n]$

由于区间$[l,r]$给定，只需要预处理出所有的$sum[pos]+sum[pos-1]$值的位置即可

当区间长度为偶数时，任意选择一个位置删除，再当作奇数时处理即可

tips

给定区间$[l,r]$

如果区间长度为偶数，那么我们一定能找到一个分割点$k$，使得$sum[r]-sum[k]==sum[k]-sum[l-1]$

为什么 ？ $sum$数组是连续的（每次最多变化1），且区间长度为偶数，那$sum[r]-sum[l-1]$一定是偶数

即一定能找到$(sum[r]-sum[l-1])/2$的位置，以此作为分割即可

Code

//D2
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
#define iss ios::sync_with_stdio(false)
#define debug(x) cout << #x << ": " << x << endl;
inline ll read() {ll s = 0, w = 1;char ch = getchar();while (ch < 48 || ch > 57) {if (ch == '-') w = -1;ch = getchar();}while (ch >= 48 && ch <= 57)s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();return s * w;
}
int sum[300005];//加权前缀和
char s[300005];
map<int, vector<int>> mp;//mp[i]为sum[pos]+sum[pos-1]==i的所有pos
int main() {int t = read();while (t--) {mp.clear();int n = read(), Q = read();scanf("%s", s + 1);for (int i = 1; i <= n; ++i) {int op = s[i] == '+' ? 1 : -1;if (i & 1) op = -op;sum[i] = sum[i - 1] + op;}for (int i = 1; i <= n; ++i) {mp[sum[i] + sum[i - 1]].push_back(i);}while (Q--) {int l = read(), r = read();if (sum[r] - sum[l - 1] == 0) {puts("0");} else {if ((r - l + 1) & 1) {int val = sum[r] + sum[l - 1];auto it = mp[val];int pos = lower_bound(it.begin(), it.end(), l)-it.begin();//只需要找到[l,r]内的任意posprintf("1\n%d\n",it[pos]);} else {int val = sum[r - 1] + sum[l - 1];auto it = mp[val];int pos = lower_bound(it.begin(), it.end(), l) - it.begin();printf("2\n%d %d\n",it[pos],r);//偶数随意删除即可，我这里删除最后一个位置}}}}
}