关于月赛

Yhy001 @ 2024-10-02 18:36:54

by Yhy001 @ 2024-10-02 18:41:19

@EityDawn 是c，不是b2...

by EityDawn @ 2024-10-02 18:41:39

@Yhy001 哦哦

by yangyang1000 @ 2024-10-02 18:42:34

set维护启发式合并似乎能做 @Yhy001

by EityDawn @ 2024-10-02 18:44:32

@Yhy001 一份假复杂度代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Int;
template<class T>
inline void read(T &x)
{
    x=0;short w=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') w=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+c-'0',c=getchar();
    x=x*w;
}
inline void read(char &x)
{
    x=getchar();
    while(isspace(x))
        x=getchar();
    return;
}
inline void read(char *x)
{
    char c=getchar();
    while(isspace(c)) c=getchar();
    while(!isspace(c)&&~c)
        *(x++)=c,c=getchar();
    *x=0;
}
inline void read(string &x)
{
    char c=getchar();x.clear();
    while(isspace(c)) c=getchar();
    while(!isspace(c)&&~c)
        x.push_back(c),c=getchar();
}
inline void read(double &x)
{
    x=0;short w=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') w=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
        x=x*10+c-'0',c=getchar();
    if(c=='.')
    {
        c=getchar();double f=0.1;
        while(c>='0'&&c<='9')
        {
            x+=(c-'0')*f,f*=0.1;
            c=getchar();
        }
    }
    x=x*w;
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^'0');
}
inline void write(char c){putchar(c);}
inline void write(string x){for(auto c:x) putchar(c);}
inline void write(char *x){while(*x) putchar(*(x++));}
inline void write(const char *x){while(*x) putchar(*(x++));}
inline void write(double x){printf("%.6lf",x);}
template<class type,class ...T>
inline void read(type &x,T&...y){read(x),read(y...);}
template<class type,class ...T>
inline void write(type x,T ...y){write(x),write(y...);}
const int N=2e5+10;
char S[N],T[N];
vector<int>Base[N];
int n,m;
int sum[N<<2],tag[N<<2];
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
void addtag(int x)
{
    sum[x]^=1;tag[x]^=1;
}
void push_down(int l,int r,int x)
{
    if(!tag[x]) return ;
    int mid=(l+r)>>1;
    addtag(lc(x)),addtag(rc(x)),tag[x]=0;
}
void push_up(int x){sum[x]=sum[lc(x)]+sum[rc(x)];}
void modify(int p,int q,int l,int r,int x)
{
    if(p<=l&&q>=r) return addtag(x);
    push_down(l,r,x);
    int mid=(l+r)>>1;
    if(p<=mid) modify(p,q,l,mid,lc(x));
    if(q>mid) modify(p,q,mid+1,r,rc(x));
    return push_up(x);
}
int query(int y,int l,int r,int x)
{
    if(l==r) return (sum[x]);
    push_down(l,r,x);
    int mid=(l+r)>>1;
    if(y<=mid) return query(y,l,mid,lc(x));
    else return query(y,mid+1,r,rc(x));
}
vector<int>de;
int main()
{
    read(n,m);
    read(S+1),read(T+1);
    for(int i=1;i<=n;++i) 
        if(S[i]^T[i]) de.push_back(i);
    de.push_back(n+1);
    for(int i=1,l,r;i<=m;++i)
    {
        read(l,r);
        l=lower_bound(de.begin(),de.end(),l)-de.begin()+1;
        r=upper_bound(de.begin(),de.end(),r)-de.begin();
        if(l>r) continue;
        Base[de[l-1]].push_back(de[r-1]);
    }
    for(int i=1;i<=n;++i)
    {
        if(S[i]==T[i]||!Base[i].size()) continue;
        sort(Base[i].begin(),Base[i].end());
        Base[i].erase(unique(Base[i].begin(),Base[i].end()),Base[i].end());
        for(int j=0;j<Base[i].size()-1;j++) 
        {
            int pos=*lower_bound(de.begin(),de.end(),Base[i][j]+1);
            Base[pos].push_back(Base[i].back());
        }
        if((query(i,1,n,1)&1)^(S[i]-'0')) continue;
        modify(i,Base[i].back(),1,n,1);
    }
    for(int i=1;i<=n;i++)
        write((query(i,1,n,1)&1)?T[i]:S[i]); 
    return 0;
}