一个数据结构题。
首先断环成链,发现对一个值修改只是修改了 4 个点,直接单点修改即可。
这里其实所有非零的值都是一样的,只用 0/1 来表示即可。
考虑查询,可以考虑二分最小长度,只要所有距离大于这个长度的这个区间内有符合条件的零串即可。
即我们需要去求一个区间内是否有被 1 包裹的 0 串,使用一个线段树即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2E5+5;
int n,m,a[N],op[N],opt;struct node{int l,r,c,s;node(bool x=0){l=r=c=x,s=0;}node friend operator + ( node a, node b){node res(0);res.l = a.l ;res.r = b.r ;res.c = a.c + b.c ;res.s = a.s + b.s + (a.c && b.c && (!a.r || !b.l ));return res; }
};struct SEGT{#define ls p<<1#define rs p<<1|1#define mid (l+r>>1) node c[N<<2];void pushup(int p){c[p]=c[ls]+c[rs];}void change(int p,int l,int r,int x,int w){if(l==r)return c[p]=node(w),void();if(x<=mid)change(ls,l,mid,x,w);else change(rs,mid+1,r,x,w);pushup(p);}node query(int p,int l,int r,int L,int R){if(R<L)return node(0);if(L<=l &&r<=R) return c[p];if(L<=mid && R>mid)return query(ls,l,mid,L,R) + query(rs,mid+1,r,L,R);if(L<=mid )return query(ls,l,mid,L,R);return query(rs,mid+1,r,L,R); }#undef mid
}seg;
char s[2];
inline int calc(int x,int y,bool op){return op?(x*y%10):(x+y)%10;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d%s",a+i,s+1);op[i]=(s[1]=='*');a[i+n] = a[i],op[i+n]=op[i];}for(int i=2;i<=2*n;i++)seg.change(1,1,n*2,i,calc(a[i-1],a[i],op[i])); while(m--){scanf("%d",&opt);if(opt==1){int x,pos,y;scanf("%d%d%s",&pos,&x,s+1);pos++;y=(s[1]=='*'); a[pos]=x;a[pos+n]=x;op[pos]=y,op[pos+n]=y;if(pos>1)seg.change(1,1,n*2,pos,calc(a[pos-1],a[pos],op[pos]));seg.change(1,1,n*2,pos+1,calc(a[pos],a[pos+1],op[pos+1]));seg.change(1,1,n*2,pos+n,calc(a[pos-1+n],a[pos+n],op[pos+n]));if(pos < n)seg.change(1,1,n*2,pos+1+n,calc(a[pos+n],a[pos+1+n],op[pos+1+n]));}else {int pos;scanf("%d",&pos);pos++;if(!a[pos] && !seg.query(1,1,n*2,pos+1,n+pos-1).s){puts("0");continue;} if(!seg.query(1,1,2*n,2,pos-1).s && !seg.query(1,1,2*n,pos+1,2*n).s) {puts("-1");continue; }int l=1,r=n/2,res=1;while(l<=r){int mid=l+r>>1; if(seg.query(1,1,2*n,pos+mid-1,pos-mid+n+1).s)res=mid,l=mid+1;else r=mid-1;}printf("%d\n",res);}}return 0;}