调到了天亮。。。。
很一眼 就是线段树区间加 然后回文串只有两种类型 aa aba
所以我们维护的信息就是 l r 最左边两个字母ls[2] 最右边两个字母rs[2] 是否发现回文串st
最重要的来了 我们不能初始化次左 次右 为当前字母
我们应该初始化为-1 然后注意pushdown不要影响他们
pushup时也要注意是-1时我们的赋值
就是这里调了一晚上 哎
struct node{
int l,r,lz,ls[2],rs[2],st;
}tr[800010];
int n,m;
string s;
void pushup(node &u,node &l,node &r){
if(u.r-u.l+1==2){
u.ls[0]=l.ls[0];
u.ls[1]=r.ls[0];
u.rs[0]=r.rs[0];
u.rs[1]=l.rs[0];
}else{
u.ls[0]=l.ls[0];
u.ls[1]=l.ls[1];
u.rs[0]=r.rs[0];
u.rs[1]=r.rs[1];
}
// if(!~u.ls[1])u.ls[1]=r.ls[0];
// if(!~u.rs[1])u.rs[1]=l.rs[0];
u.st=0;
u.st=l.st|r.st;
if(~l.rs[1]&&~r.ls[0]&&l.rs[1]==r.ls[0])u.st=1;
if(~l.rs[0]&&~r.ls[1]&&l.rs[0]==r.ls[1])u.st=1;
if(~l.rs[0]&&~r.ls[0]&&l.rs[0]==r.ls[0])u.st=1;
}
void pushup(int i){
auto &u=tr[i],&l=tr[i<<1],&r=tr[i<<1|1];
pushup(u,l,r);
}
void pushdown(int i) {
auto &u = tr[i], &l = tr[i << 1], &r = tr[i << 1 | 1];
if(u.lz){
l.lz+=u.lz;
if(~l.ls[0])(l.ls[0]+=u.lz)%=26;
if(~l.ls[1])(l.ls[1]+=u.lz)%=26;
if(~l.rs[0])(l.rs[0]+=u.lz)%=26;
if(~l.rs[1])(l.rs[1]+=u.lz)%=26;
r.lz+=u.lz;
if(~r.ls[0])(r.ls[0]+=u.lz)%=26;
if(~r.ls[1])(r.ls[1]+=u.lz)%=26;
if(~r.rs[0])(r.rs[0]+=u.lz)%=26;
if(~r.rs[1])(r.rs[1]+=u.lz)%=26;
u.lz=0;
}
}
void build(int i,int l,int r){
tr[i]={l,r,0,-1,-1,-1,-1,0};
if(l==r){
int x=s[l]-'a';
tr[i].ls[0]=tr[i].rs[0]=x;
return;
}
int mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
}
void modify(int i,int l,int r,int k){
if(tr[i].l>=l&&tr[i].r<=r){
auto &u=tr[i];
u.lz+=k;
if(~u.ls[0])(u.ls[0]+=k)%=26;
if(~u.ls[1])(u.ls[1]+=k)%=26;
if(~u.rs[0])(u.rs[0]+=k)%=26;
if(~u.rs[1])(u.rs[1]+=k)%=26;
return;
}
pushdown(i);
if(tr[i].l>r||tr[i].r<l)return;
if(tr[i<<1].r>=l)modify(i<<1,l,r,k);
if(tr[i<<1|1].l<=r)modify(i<<1|1,l,r,k);
pushup(i);
}
int query(int i,int x){
if(tr[i].l>=x&&tr[i].r<=x){
return tr[i].ls[0];
}
pushdown(i);
int c;
if(tr[i<<1].r>=x)c=query(i<<1,x);
if(tr[i<<1|1].l<=x)c=query(i<<1|1,x);
pushup(i);
return c;
}
inline node search(int i,int l,int r){
node s;
if(tr[i].l>=l && tr[i].r<=r)return tr[i];
else {
pushdown(i);
if (tr[i << 1].r >= r) s = search(i << 1, l, r);
else if (tr[i << 1 | 1].l <= l) s = search(i << 1 | 1, l, r);
else {
auto left = search(i << 1, l, r);
auto right = search(i << 1 | 1, l, r);
node res;
pushup(res, left, right);
return res;
}
}
pushup(i);
return s;
}
void solve(){
cin>>n>>m;
cin>>s;s='+'+s;
build(1,1,n);
// for(int j=1;j<=n;j++)cout<<(char)(query(1,j)+'a');cout<<endl;
for(int i=1;i<=m;i++){
int op;cin>>op;
if(op==1){
int l,r,x;cin>>l>>r>>x;
modify(1,l,r,x);
}else{
int l,r;cin>>l>>r;
auto st= search(1,l,r);
// cout<<l<<' '<<r<<' ';
if(st.st)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
// for(int j=1;j<=n;j++)cout<<(char)(query(1,j)+'a');cout<<endl;
}
}