题解：
原来动态开点平衡树是O(n)空间的。。
只需要在split的查找和出来之后动态开点就可以了
这题的结论是2^(b[a[i]+1]>b[a[i+1]+1]的个数）
前60分是普通的平衡树操作完之后再算
满分是动态开点平衡树
对于一个点内部的统计一下，边界上的特判一下
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define me(x) memset(x,0,sizeof(x))
#define ll long long
#define mid ((h+t)>>1)
#define mep(x,y) memcpy(x,y,sizeof(y))
namespace IO
{
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
rint f=,c;while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
char sr[<<],z[]; int C=-,Z;
template<class T>void wer(T x)
{
if (x<) sr[++C]='-',x=-x;
while (z[++Z]=x%+,x/=);
while (sr[++C]=z[Z],--Z);
}
IL void wer1() {sr[++C]=' ';}
IL void wer2() {sr[++C]='\n';}
template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}
template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}
template<class T>IL T MAX(T x,T y){ return x>y?x:y;}
template<class T>IL T MIN(T x,T y){ return x<y?x:y;}
}
using namespace IO;
const int N=9e5;
int a[N],b[N],xl[N],cnt,dy[N],d[N],tmp;
const int mo=1e9+;
struct re{
int a,b,kk,d;
}c[N],f[N],p[N],c1[N];
int nq;
struct phs{
int fa[N],rs[N],ls[N],num[N],o[N],v[N],cnt,cnt3;
bool rev[N],t[N];
IL void updata(int x)
{
num[x]=num[ls[x]]+num[rs[x]]+o[x];
}
IL void down(int x)
{
if (rev[x])
{
swap(ls[ls[x]],rs[ls[x]]);
swap(ls[rs[x]],rs[rs[x]]);
rev[ls[x]]^=; rev[rs[x]]^=;
t[ls[x]]^=; t[rs[x]]^=;
rev[x]=;
}
}
void rotate(int x,int y)
{
int f1=fa[x];
if (y==)
{
rs[f1]=ls[x];
if (ls[x]) fa[ls[x]]=f1;
} else
{
ls[f1]=rs[x];
if (rs[x]) fa[rs[x]]=f1;
}
fa[x]=fa[f1];
if (fa[f1])
{
if (ls[fa[f1]]==f1) ls[fa[f1]]=x; else rs[fa[f1]]=x;
}
fa[f1]=x;
if (y==) ls[x]=f1; else rs[x]=f1;
updata(f1); updata(x);
}
void dfs(int x)
{
if (fa[x]) dfs(fa[x]);
down(x);
}
IL void splay(int x,int y)
{
dfs(x);
int f1=fa[x];
while (f1!=y)
{
if (fa[f1]==y)
if (ls[f1]==x) rotate(x,); else rotate(x,);
else
if (ls[fa[f1]]==f1)
if (ls[f1]==x) rotate(f1,),rotate(x,);
else rotate(x,),rotate(x,);
else if (rs[f1]==x) rotate(f1,),rotate(x,);
else rotate(x,),rotate(x,);
f1=fa[x];
}
}
IL int sc(int x,int y)
{
if (t[x])
{
o[++nq]=y; num[nq]=y; fa[nq]=x; v[nq]=v[x];
ls[nq]=ls[x]; o[x]-=y;
v[x]+=y; ls[x]=nq; t[nq]=t[x];
} else
{
o[++nq]=y; num[nq]=y; fa[nq]=x; v[nq]=v[x]+o[x]-y;
ls[nq]=ls[x]; o[x]-=y;
ls[x]=nq; t[nq]=t[x];
}
if (ls[nq]) fa[ls[nq]]=nq;
num[nq]+=num[ls[nq]];
return nq;
}
IL int search(int y)
{
splay(,);
int x=;
while ()
{
down(x);
if (num[ls[x]]+o[x]>=y&&num[ls[x]]<y)
{
if (num[ls[x]]+o[x]==y) return(x);
return sc(x,y-num[ls[x]]);
}
if (num[ls[x]]+o[x]>y) x=ls[x];
else y-=num[ls[x]]+o[x],x=rs[x];
}
}
IL int split(int x,int y)
{
int k1=search(x),k2=search(y+);
splay(k1,);
splay(k2,k1);
if (o[k2]!=)
sc(k2,o[k2]-);
return ls[k2];
}
IL void reverse(int x,int y)
{
int k=split(x,y);
rev[k]^=; swap(ls[k],rs[k]); t[k]^=;
}
IL void change(int x,int y)
{
int k=split(x,y);;
int now=fa[k];
ls[now]=; fa[k]=; splay(now,);
now=search();
splay(now,); down(now); down();
rs[]=k; fa[k]=; splay(k,);
}
void dfs2(int x)
{
down(x);
if (ls[x]) dfs2(ls[x]);
// a[++cnt]=v[x];
c[++cnt]=(re){v[x],o[x],t[x],cnt3+};
cnt3+=o[x];
if (rs[x]) dfs2(rs[x]);
}
}S;
bool cmp(re x,re y)
{
return x.a<y.a;
}
IL int pos(int x)
{
if (x>tmp) return();
int h=,t=S.cnt-;
while (h<t)
{
if (f[mid].a+f[mid].b->=x) t=mid;
else h=mid+;
}
if (f[h].kk) return f[h].d+x-f[h].a;
else return f[h].d+f[h].b--(x-f[h].a);
}
IL int pos2(int x)
{
if (c[x].kk) return c[x].a;
else return c[x].a+c[x].b-;
}
IL int fsp(ll x,int y)
{
ll ans=;
while (y)
{
if (y&) ans=ans*x%mo;
x=x*x%mo; y>>=;
}
return ans;
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
int n,m;
read(n); read(m);
tmp=n;
int cnt=;
nq=;
S.rs[]=; S.rs[]=; S.fa[]=; S.fa[]=; S.t[]=;
S.o[]=; S.v[]=; S.o[]=n; S.v[]=; S.o[]=; S.v[]=n+;
S.splay(,);
rep(i,,m)
{
int kk,x,y;
read(kk); read(x); read(y);
if (kk==) S.change(x,y);
else S.reverse(x,y);
}
S.splay(,);
S.dfs2();
int l=S.cnt;
rep(i,,l-) f[i]=c[i+];
sort(f+,f+l-+,cmp);
cnt=;
rep(i,,l-)
{
if (c[i].b>=) cnt+=c[i].b-;
if (c[i].kk)
{
if (c[i].b>=&&i!=(l-))
{
int k1=c[i].a+c[i].b-,k2=pos2(i+);
if (pos(k1+)<pos(k2+)) cnt++;
}
if (c[i].b>=)
{
int k1=c[i].a+c[i].b-,k2=c[i].a+c[i].b-;
if (pos(k1+)<pos(k2+)) cnt++;
}
} else
{
if (c[i].b>=&&i!=(l-))
{
int k1=c[i].a,k2=pos2(i+);
if (pos(k1+)<pos(k2+)) cnt++;
}
if (c[i].b>=)
{
int k1=c[i].a+c[i].b-,k2=c[i].a+c[i].b-;
if (pos(k1+)<pos(k2+)) cnt++;
}
}
}
cout<<fsp(,cnt)<<endl;
return ;
}