[ABC341E] Alternating String 讲解

· · 题解

题目
考察：线段树，树状数组，set，差分。

方法一：

这道题与 P3870 有点相似，只不过它是区间求和，而这道题是判断是不是好字符串。
我们不难发现，好的字符串有以下特征：

  1. 好的字符串取反后必为好的字符串（不好的字符串取反后必为不好的字符串）。
  2. 好的字符串的子串必为好的字符串（不好的字符串的母串必为不好的字符串）。

然后我们来看个图：

所以说我们要存三个值：首端点值，尾端点值和判断变量，我们分别用 begin，end，vis 表示（当然懒标记也是需要的，我们用 lan 表示）。
我们得到状态转移方程：

vis_x=[vis_u\lor vis_v\lor (end_u\ne begin_v)] begin_x=begin_u end_x=end_v

边界条件为（l=r）：

vis_x=1 begin_x=end_x=a_l

修改时：

lan_x=1-lan_x

pushdown 函数：

begin_u=1-begin_u end_u=1-end_u begin_v=1-begin_v end_v=1-end_v lan_u=lan_v=1 lan_x=0

易得代码（时间：427ms，空间：47.53MB，代码长度：2.64KB，是三种做法之中最劣的一种做法）： 

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
using namespace std;
inl int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
}
const int N=5e5+5;
struct trees{
    int l,r,begin,end;
    bool vis,lan;
}t[N<<2];
string s;
int n,q,a[N],op,l,r;
inl void build(int x,int l,int r){
    t[x].l=l;
    t[x].r=r;
    if(l==r){
        t[x].vis=1;
        t[x].begin=a[l];
        t[x].end=a[r];
//      cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    t[x].vis=(t[x<<1].vis&&t[x<<1|1].vis&&t[x<<1].end!=t[x<<1|1].begin);
    t[x].begin=t[x<<1].begin;
    t[x].end=t[x<<1|1].end;
//  cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
}
inl void pushdown(int x){
    if(!t[x].lan) return;
    t[x<<1].begin^=1;
    t[x<<1].end^=1;
    t[x<<1|1].begin^=1;
    t[x<<1|1].end^=1;
    t[x<<1].lan^=1;
    t[x<<1|1].lan^=1;
//  cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
//  cout<<(x<<1)<<' '<<t[x<<1].l<<' '<<t[x<<1].r<<' '<<t[x<<1].begin<<' '<<t[x<<1].end<<' '<<t[x<<1].vis<<endl;
//  cout<<(x<<1|1)<<' '<<t[x<<1|1].l<<' '<<t[x<<1|1].r<<' '<<t[x<<1|1].begin<<' '<<t[x<<1|1].end<<' '<<t[x<<1|1].vis<<endl;
    t[x].lan=0;
}
inl void add(int x,int l,int r){
    if(l<=t[x].l&&t[x].r<=r){
        t[x].lan^=1;
        t[x].begin^=1;
        t[x].end^=1;
//      cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
        return;
    }
    pushdown(x);
    int mid=(t[x].l+t[x].r)>>1;
    if(l<=mid) add(x<<1,l,r);
    if(mid<r) add(x<<1|1,l,r);
    t[x].vis=(t[x<<1].vis&&t[x<<1|1].vis&&t[x<<1].end!=t[x<<1|1].begin);
    t[x].begin=t[x<<1].begin;
    t[x].end=t[x<<1|1].end;
//  cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
}
inl bool getans(int x,int l,int r){
    if(l<=t[x].l&&t[x].r<=r) return t[x].vis;
    pushdown(x);
    int mid=(t[x].l+t[x].r)>>1;
    bool vis=1;
    if(l<=mid) vis&=getans(x<<1,l,r);
    if(r>mid) vis&=getans(x<<1|1,l,r);
    if(l<=mid&&r>mid) vis&=(t[x<<1].end!=t[x<<1|1].begin);
    return vis;
}
signed main(){
    n=read();
    q=read();
    cin>>s;
    s=' '+s;
    for(int i=1;i<=n;++i) a[i]=s[i]^48;
    build(1,1,n);
    for(int i=1;i<=q;++i){
        op=read();
        l=read();
        r=read();
        if(op==1) add(1,l,r);
        else if(getans(1,l,r)) puts("Yes");
        else puts("No");
    }
    return 0;
}

做法 2：

看到相邻两个数不同，我们便想到差分，样例中的数列差分后就是下面这个样子：

c=\{1,1,1,1,0\}

恍然大悟，不就是转化成了单点修改（修改左右两个端点），区间求和（若区间内的和正好等于长度，也就是每个元素都为 1 时，就为好的字符串）嘛。
代码没什么好讲的，但需要注意两个点：

  1. 第 1 个点上的差分数组始终为 1。
  2. 第 l 个点上存的是第 l-1 个点与它的差分，不能算入查询区间里。

代码（时间：223ms，空间：31.55MB，代码长度：1.48KB，就时间来看，它是三种做法的最优解）： 

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
using namespace std;
inl int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
}
const int N=5e5+5;
struct trees{
    int l,r,sum;
}t[N<<2];
string s;
int n,q,a[N],op,l,r;
inl void build(int x,int l,int r){
    t[x].l=l;
    t[x].r=r;
    if(l==r){
        t[x].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
inl void add(int x,int vis){
    if(t[x].l==vis&&vis==t[x].r){
        t[x].sum^=1;
        return;
    }
    int mid=(t[x].l+t[x].r)>>1;
    if(vis<=mid) add(x<<1,vis);
    else add(x<<1|1,vis);
    t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
inl int getans(int x,int l,int r){
    if(l<=t[x].l&&t[x].r<=r) return t[x].sum;
    int mid=(t[x].l+t[x].r)>>1,sum=0;
    if(l<=mid) sum+=getans(x<<1,l,r);
    if(r>mid) sum+=getans(x<<1|1,l,r);
    return sum;
}
signed main(){
    n=read();
    q=read();
    cin>>s;
    s=' '+s;
    a[1]=1;
    for(int i=2;i<=n;++i) a[i]=s[i-1]^s[i];
    build(1,1,n);
    for(int i=1;i<=q;++i){
        op=read();
        l=read();
        r=read();
        if(op==1){
            if(l!=1) add(1,l);
            if(r!=n) add(1,r+1);
        }else if(getans(1,l+1,r)==r-l) puts("Yes");
        else puts("No");
    }
    return 0;
}

做法 3：

做法 3 很巧妙，同样做了差分，但把相同的放在了 set 里，修改的时候左右端点 set 里有就删除，没有就插入，最后直接查询。
要注意的还是上面那两个，不多说直接放代码（时间：705ms，空间：26.59MB，代码长度：982B，虽说跑的最慢，但代码空间大大减少）： 

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
using namespace std;
inl int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
}
#define T set<int>::iterator
string s;
int n,q,op,l,r;
set<int>st;
signed main(){
    n=read();
    q=read();
    cin>>s;
    s=' '+s;
    for(int i=1;i<=n;++i)
        if(s[i]==s[i-1]) st.insert(i);
    for(int i=1;i<=q;++i){
        op=read();
        l=read();
        r=read();
        if(op==1){
            if(st.find(l)==st.end()&&l!=1) st.insert(l);
            else st.erase(l);
            if(st.find(r+1)==st.end()) st.insert(r+1);
            else st.erase(r+1);
        }else{
            T it=st.upper_bound(l);
            if(it==st.end()||*it>r) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

（真的想吐槽一下专栏区）