D2. Two Hundred Twenty One (hard version)

题目

思路

预处理前缀和数组pre[N]，然后l ~ r 的和就是pre[r] - pre[l - 1]（当然可能和实际的l ~ r 的和是相反数，受到l的位置影响，不过不影响你让l ~ r 的和变为 0）
令 x = pre[r] - pre[l-1];

①x是奇数
那么你只要把 前缀和为 pre[l-1] + x/2 + ’1‘（注意这个１是和ｘ同符号）,并且位置在 l ~ r 的那个位置的杆子移除就行。

假设这个位置是p ，l ~ p - 1的贡献是 x/2,
因为移除了p,所以p + 1 ~ r 的贡献就会取反也就是 -x/2（因为p + 1 ~ r的每个‘+’，‘-’位置变化了 1，实际求和相当于翻转了），所以这么操作l ~ p - 1和p + 1 ~ r 的的贡献和就是 0 了

② x 是偶数 且不是 0（至少移除2个，不管你先移除哪一个都剩下奇数的贡献）

先移除掉位置r，这样贡献和就变成奇数，且不影响前面位置的贡献，这个时候，要考虑 ｒ的贡献是　＋１还是－１，这样移除ｒ后，贡献和就变成了ｘ＝ｘ－１，或ｘ＝ｘ＋１了，然后继续按奇数的情况把　前缀和为 pre[l-1] + x/2 + ‘1’,并且位置在 l ~ r 的那个位置的杆子移除就行．

代码

#include<bits/stdc++.h>
#define IOS std::ios_base::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);// 快读using namespace std;
struct ty{
    int p,s;ty(){
    }ty(int a,int b):p(a),s(b){
    }bool operator < (const ty &y) const {
    if(s == y.s)return p < y.p;return s > y.s;}
};const int N = 1e6 + 10;
vector<ty> a;
int pre[N];
string s;int main(){
    IOS//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout); int T;  cin >> T;for (int d = 1; d <= T; ++d){
    a.clear();int n,q;  cin >> n >> q >> s;for(int i = 0; i < n; ++i){
    ty x;x.p = i + 1;x.s = s[i] == '+' ? pow(-1,i%2):pow(-1,i%2 + 1);x.s += pre[i];pre[i + 1] = x.s;a.push_back(x);}sort(a.begin(), a.end()); while(q--){
    int l,r;    cin >> l >> r;int x = pre[r] - pre[l - 1];int f; if(x > 0) f = 1; else f = -1;if(!x){
    cout << 0 << '\n';}else if(abs(x)&1){
    x = x/2 + f;//加上与x同号的一个贡献auto it = lower_bound(a.begin(),a.end(),ty{
    l,pre[l - 1] + x});cout << 1 << '\n' << it->p <<'\n';}else{
    int y = s[r-1] == '+' ? pow(-1,r%2 + 1):pow(-1,r%2);if(y*x > 0) x = x/2;//x - y的贡献else x = x/2 - y;   //x + y的贡献auto it = lower_bound(a.begin(),a.end(),ty{
    l,pre[l - 1] + x});cout << 2 << '\n' << it->p << ' ' << r << '\n';}}}return 0;
}
//-++-