询问为什么 l 要加一

写的 treap，因为个人习惯喜欢在平衡树内加上 -\infty 和 +\infty。

按照我的理解，Split(u,a,b,k) 的意思是，将 u 分裂为 a 和 b 两颗子树。其中 a 中有 k 个节点，b 中包含剩下的节点。

在 Split(root, x, y, l + 1); 一句话中，我不理解为什么 l 要 +1。按理说我应该把 [1,l-1] 的所有点全都分到 x 这个子树中，算上那个 -\infty，总计应该分 l 个点才对，可是为什么要写 l + 1？我不是很理解

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <random>
#include <string>
#include <type_traits>
#include <utility>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;

#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto &&i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define dbg(x) (cerr << "(dbg) " << #x " = " << (x) << '\n')
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define up(x, y) (((x) < (y)) && ((x) = (y)))
#define down(x, y) (((x) > (y)) && ((x) = (y)))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))

// clang-format off
namespace FastIO {
  const int SZ=(1<<21)+1;
  struct I {
    char ibuf[SZ],*iS,*iT,c;int f,_eof;FILE*fi;
    I(FILE*f):fi(f){}
    inline char Gc(){return iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SZ,fi),(iS==iT?EOF:*iS++)):*iS++;}
    inline ll operator()(){ll x;operator()(x);return x;}
    inline I&operator()(char&x){x=Gc();return*this;}
    inline I&operator()(char*s){for(c=Gc();c<32||c>126||c==' ';)c=Gc();for(;c>31&&c<127&&c!=' '&&c!='\n'&&c!='\r';++s,c=Gc())*s=c;*s=0;return*this;}
    template<class T>inline I&operator()(T&x){_eof=0;for(f=1,c=Gc();(c<'0'||c>'9')&&!_eof;c=Gc()){if(c=='-')f=-1;_eof|=c==EOF;}for(x=0;c<='9'&&c>='0'&&!_eof;c=Gc())x=x*10+(c&15),_eof|=c==EOF;x*=f;return*this;}
    template<class T>I&operator()(T*x,const int&n,const int&st=1){rep(i,st,n){operator()(x[i]);}return*this;}
  } in(stdin);
  struct O {
    char obuf[SZ],*oS=obuf,*oT=oS+SZ-1,qu[55];int f,qr;FILE*fi;
    O(FILE*f):fi(f){}
    ~O(){Flush();}
    inline void Flush(){fwrite(obuf,1,oS-obuf,fi),oS=obuf;}
    inline O&operator()(char x){*oS++=x;if(oS==oT)Flush();return*this;}
    inline O&operator()(char*s){int len=strlen(s);for(f=0;f<len;++f)operator()(s[f]);return*this;}
    inline O&operator()(const char*s){return operator()((char*)s);}
    template<class T>inline O&operator()(T x){if(!x)operator()('0');if(x<0)operator()('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)operator()(qu[qr--]);return*this;}
    template<class T>O&operator()(T*x,const int&n,const char&ed=' ',const int&st=1){rep(i,st,n)operator()(x[i])(ed);return*this;}
  } out(stdout);
}
using FastIO::in;using FastIO::out;
template<class K,class V>ostream&operator<<(ostream&s,const pair<K,V>&p){s<<'<'<<p.first<<", "<<p.second<<'>';return s;}
template<class T,class=typename T::value_type,class=typename enable_if<!is_same<T,string>::value>::type>ostream&operator<<(ostream&s,const T&v){s<<'[';each(x,v)s<<x<<", ";if(!v.empty())s<<"\b\b";s<<']';return s;}
template<class T>T Abs(const T&a){return a>0?a:-a;}
ll Pow(ll a,ll b,const ll&m){ll res=1;a%=m;while(b>0){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res;}
ll Gcd(ll a,ll b){ll t;while(b!=0)t=a%b,a=b,b=t;return a;}
ll C(ll n,ll m){if(m>n)return 0;ll a=1;re(i,m)a*=(n-i+1),a/=i;return a;}
ll C(ll n,ll m,ll p){if(m>n)return 0;ll x=1;re(i,m){ll a=(n+i-m)%p,b=i%p;x=x*(a*Pow(b,p-2,p)%p)%p;}return x;}
// clang-format on

#define NewNode(k, sz, ls, rs) \
  new Node { (int)k, sz, (int)(rnd() >> 1), ls, rs, false }
#define ULS u->ls, a, u->ls
#define URS u->rs, u->rs, b

struct Node {
  int k, sz, p;
  Node *ls, *rs;
  bool lz;
} * root, *nil;
int tp;
mt19937 rnd;

void Down(Node *u) {
  if (u == nil || !u->lz) return;
  swap(u->ls, u->rs);
  if (u->ls != nil) u->ls->lz ^= 1;
  if (u->rs != nil) u->rs->lz ^= 1;
  u->lz = 0;
}

void Up(Node *u) { u->sz = u->ls->sz + u->rs->sz + 1; }

void Split(Node *u, Node *&a, Node *&b, int k) {
  // cerr << u->k << ' ' << k << '\n';
  if (u == nil) return a = nil, b = nil, void();
  Down(u);
  if (u->ls->sz < k)
    a = u, Split(URS, k - u->ls->sz - 1);
  else
    b = u, Split(ULS, k);
  Up(u);
}

void Merge(Node *&u, Node *a, Node *b) {
  if (a == nil) return u = b, void();
  if (b == nil) return u = a, void();
  if (a->p < b->p)
    u = a, Down(a), Merge(URS);
  else
    u = b, Down(b), Merge(ULS);
  Up(u);
}

void Ins(Node *&u, int k) {
  Node *x = nil, *y = nil;
  Split(u, x, y, k - 1);
  Merge(y, y, NewNode(k, 1, nil, nil));
  Merge(u, x, y);
}

const int INF = 2147483647;

void Print(Node *u) {
  Down(u);
  if (u->ls != nil) Print(u->ls);
  if (Abs(u->k) != INF) out(u->k)(' ');
  if (u->rs != nil) Print(u->rs);
}

int n, m;

signed main() {
  nil = NewNode(0, 0, 0, 0);
  root = NewNode(-INF, 1, nil, nil);
  Ins(root, INF);
  in(n)(m);
  re (i, n)
    Ins(root, i);
  while (m--) {
    int l = in(), r = in();
    Node *x, *y, *z;
    Split(root, x, y, l + 1); 
    Split(y, y, z, r - l + 1);
    y->lz ^= 1;
    Merge(y, y, z), Merge(root, x, y);
  }
  Print(root), out('\n');
  return 0;
}