题目链接
题目思路
由D1观察可以发现
对于奇数长度链 消去一个值一定可满足题意 对于偶数链 如果当前满足题意则跳过 如果不满足题意则消去两个值时一定可以满足题意
根据这个规律我们再去做D2
sum【i】代表 a1?a2+a3?a4+…的前缀和
当目前为偶数链且 已经满足题意时 直接输出0
当目前为奇数链时 我们需要找到一个 i 满足去掉这个下标为 i 的值以后
sum[i-1]-sum[l-1]=sum[r]-sum[i] 移项为
sum[i-1]+sum[i]=sum[r]+sum[l-1]
当目前为偶数链且不符合题意时
任意输出一个位置 后将情况转化为奇数链进行运算
对于每一种sum[i-1]+sum[i]的值在预处理时用vector进行存储
用vector存储这一块学习了这位大佬代码
对于每一次询问 l，r 用二分找到适合的下标 输出
ps 另外这个题时间卡得很死 去掉了很多memset 和优化了输入输出以后才跑了1996ms压线过
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int t,n,q;
int sum[maxn];
int sum2[maxn];
map<int ,vector<int > >a;
void init()
{a.clear();//memset(sum,0,sizeof sum);//memset(sum2,0,sizeof sum2);
}
int sol(int l,int r)
{int now=sum[r]+sum[l-1];int tp=lower_bound(a[now].begin(),a[now].end(),l)-a[now].begin();return a[now][tp];
}
int main()
{cin>>t;//int tmp=1e6;//while(tmp--);while(t--){scanf("%d %d",&n,&q);init();int x,y;char s[maxn];scanf("%s",s);for(int i=1;i<=n;i++){if(s[i-1]=='+')x=1;else x=-1;y=x;if(i%2==0){x*=-1;}else y*=-1;sum[i]=0;sum[i]+=sum[i-1]+x;a[sum[i]+sum[i-1]].push_back(i);//sum2[i]+=sum2[i-1]+y;}while(q--){cin>>x>>y;if((y-x+1)%2==1){printf("1\n%d\n",sol(x,y));continue;}if(sum[y]-sum[x-1]==0){printf("0\n");}else {printf("2\n%d %d\n",x,sol(x+1,y));}}}return 0;
}