关于 set 启发式合并

#include<bits/stdc++.h>
using namespace std;
#define ve vector
#define x first
#define y second
#define ep emplace
#define pb emplace_back
#define de(b) #b,'=',b
#define Sz(k) int((k).size())
#define all(b) begin(b),end(b)
#define rll(k) rbegin(k),rend(k)
namespace BK0717 {
#ifdef Bella
ifstream cin("BK.in"); ofstream cout("BK.out");
void clg(auto x){cerr<<x;} void clg(auto x,auto...y){clg(x),clg(y...);}
#endif
int cn(auto&x,auto y){return x>y?x=y,1:0;}
int cx(auto&x,auto y){return x<y?x=y,1:0;}
template<class T> constexpr T inf=numeric_limits<T>::max()/2;
using LL=long long; using db=double; using pii=pair<int,int>;
constexpr int $N=2e5+7;
set<int>S[$N];
struct BITS {
  ve<int>t;
  void Init(int n) {
    t.assign(n+2,0);
  }
  void _M(int x,int y) {
    for(++x;x<Sz(t);x+=x&-x) t[x]+=y;
  }
  void M(int l,int r) {
    _M(l,1),_M(r,-1);
  }
  int Q(int x) {
    int s=0;
    for(++x;x;x-=x&-x) s+=t[x];
    return s&1;
  }
}T;
void Solve() {
  int n,m; cin>>n>>m; T.Init(n);
  string a,b; cin>>a>>b;
  for(;m--;) {
    int l,r; cin>>l>>r,--l;
    S[l].ep(r);
  }
  for(int i=0;i<n;++i) if(Sz(S[i])) {
    if(a[i]==b[i]) {
      // if(Sz(S[i])>Sz(S[i+1])) S[i].swap(S[i+1]); // add this line is wrong.
      for(int r:S[i]) if(i+1<r) S[i+1].ep(r);
    }
    else {
      int lst=*begin(S[i]); S[i].erase(begin(S[i]));
      if(a[i]<b[i]!=T.Q(i)) T.M(i,lst);
      for(int r:S[i]) S[lst].ep(r),lst=r;
    }
  }
  for(int i=0;i<n;++i) if(T.Q(i)) swap(a[i],b[i]);
  cout<<a;
  return;
}
void main() {
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int T=1;
  // cin>>T;
  for(;T--;) Solve();
} } main(){BK0717::main();}