一道十分有趣的烧脑题。

不仅考验了线段树的理解程度，还考验了很多很多的...细节？

我只想到了第一步：离线。

列出最后的状态

0------------
1------------
2------------
3------------

然后倒着做一遍，上升变成下降。

最后求出所有$0$被平移到了第几层就好了。

这其实就是挖掘出最初的$0$点是从哪一层平移上来的。

这样我们就成功的把风化这个毒瘤条件给搞掉了。

因此我们只需要维护所有0的横纵坐标。（注意我们规定原坐标系纵坐标正方向向上）

第二步：翻转坐标。

把一个点$(x,y)$翻转坐标成为$(x',y')$

$$x'=x-y,y'=x+y$$

这样坐标系就变成了这样

          0    
        0 _ 1
      0 _ 1 _
    0 _ 1 _ 2
  0 _ 1 _ 2 _ 
0 _ 1 _ 2 _ 3 

我们发现所有操作都简单多了，

$1$操作就是左边一整块向下平移，$2$操作就是上面一整块向右平移！

比如说我们随便移动一下，

借用一下$*Miracle*$巨佬的图就是

那么我们如何维护所有$0$点的横纵坐标变化呢？正解已经呼之欲出了。

第三步：线段树。

先把两个点之间的层转化成靠右的层。

用两棵线段树维护$0$点的$x,y$坐标

$1$操作，把$y$线段树中所有$x$坐标$\leq X_i$ 的$y$坐标减去$2L$

$2$操作，把$x$线段树中所有$y$坐标$>X_i$ 的$x$坐标加上$2L$

很显然$0$点的$x,y$坐标满足二分性：对于$i<j,x_i<x_j,y_i<y_j$

所以可以直接二分，或者线段树上二分。

前者是两个$\log$的，需要$O2$。

后者是一个$\log$的。

有人可能觉得很奇怪，为什么不是找第$X_i$个$0$点平移呢？

---

可能你感觉这个问题很蠢，但是我在独立思考的时候就被这个问题困扰了，也许是我太菜了吧...

第一：$X_i$很大。

第二：可以考虑用$-1,-2...$来填充原来对角线上的位置。这样就好理解很多了。$0$点到其他位置上去了，我们不可以直接平移。

---

关于线段树上怎么二分:比如说求第一个$x$坐标$\leq X_i$的点。

我们维护区间最小值。

对于线段树上一个节点，如果右儿子最小值$\leq X_i$，直接去右儿子里找 （根据刚才讲述的二分性质，右儿子一定比左儿子更优）

否则答案一定在左儿子里面。

那么求第一个$>X_i$的点怎么办呢？再维护一个区间最大值？？？这样常数会翻倍！

其实大大不必。由于二分单调性，我们可以用这样的方法：

对于一个节点，如果右儿子最小值$>X_i$，那么显然右儿子最小值是在$(\text{mid}+1)($右儿子编号最小的点的编号$)$处取到的

然后我们继续往左儿子去找是否存在更小的点，和当前答案取一个$\min$就好了。

否则答案一定在右儿子处，继续递归即可。

有一个小细节：如果找不到这个点的话就不需要执行本次操作了。

最后一步：

我们知道了所有0点在翻转坐标系中的横纵坐标$z',y'$，通过解方程可以知道我们最后真实纵坐标

$$y=\frac{(y'-x')}2$$

但是很坑的是我们求的是答案层数！ 所以答案

$$=\frac {(x'-y')}2\ \ !!!$$

代码很简单，我只写+调了$30$ min。只要思路清晰了这道题不算难写。

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
//x为0 y为1
ll seg[2][1000001],tag[2][1000001];//最小值和加法标记。
inline void pushup(int c,int rt){
    seg[c][rt]=min(seg[c][rt<<1],seg[c][rt<<1|1]);
}
#define mid ((lb+rb)>>1)
void build(int rt,int lb,int rb){
    if (lb==rb) return (void)(seg[0][rt]=seg[1][rt]=lb);
    build(rt<<1,lb,mid);build(rt<<1|1,mid+1,rb);
    pushup(0,rt);pushup(1,rt);
}
inline void pushdown(int c,int rt,int lb,int rb){
    if (!tag[c][rt]) return;
    int ls=rt<<1,rs=rt<<1|1;
    seg[c][ls]+=tag[c][rt];seg[c][rs]+=tag[c][rt];
    tag[c][ls]+=tag[c][rt];tag[c][rs]+=tag[c][rt];
    tag[c][rt]=0;
}
void update(int c,int rt,int lb,int rb,int l,int r,ll x){
    if (lb>r||rb<l) return;
    if (lb>=l&&rb<=r) return (void)(seg[c][rt]+=x,tag[c][rt]+=x);
    pushdown(c,rt,lb,rb);update(c,rt<<1,lb,mid,l,r,x);
    update(c,rt<<1|1,mid+1,rb,l,r,x);pushup(c,rt);
}
void Findx(int rt,int lb,int rb,int x,int &ans){
    if (lb==rb) return (void)(ans=(seg[0][rt]<=x?max(ans,lb):ans));
    pushdown(0,rt,lb,rb);
    if (seg[0][rt<<1|1]<=x) Findx(rt<<1|1,mid+1,rb,x,ans);
    else Findx(rt<<1,lb,mid,x,ans);
}
void Findy(int rt,int lb,int rb,int x,int &ans){
    if (lb==rb) return (void)(ans=(seg[1][rt]>x?min(ans,lb):ans));
    pushdown(1,rt,lb,rb);
    if (seg[1][rt<<1|1]>x) ans=min(ans,mid+1),Findy(rt<<1,lb,mid,x,ans);
    else Findy(rt<<1|1,mid+1,rb,x,ans);
}
ll ans[2][1000001];
void done(int rt,int lb,int rb){//获取最终答案信息 
    if (lb==rb) return (void)(ans[0][lb]=seg[0][rt],ans[1][lb]=seg[1][rt]);
    pushdown(1,rt,lb,rb);pushdown(0,rt,lb,rb);done(rt<<1,lb,mid);done(rt<<1|1,mid+1,rb);
}
int n,Q;
ll que[1000001][3];
signed main(){
    n=read();Q=read();
    build(1,1,n);
    for (int i=1;i<=Q;i++) que[i][0]=read(),que[i][1]=read(),que[i][2]=read();
    for (int i=Q;i;i--){
    	ll opt=que[i][1],X=que[i][0],L=que[i][2];
    	if (opt==1){
            int pos=-999999999;Findx(1,1,n,X,pos);
            if (pos!=-999999999) update(1,1,1,n,1,pos,-2*L);
        }else{
            int pos=999999999;Findy(1,1,n,X,pos);
            if (pos!=999999999) update(0,1,1,n,pos,n,2*L);
        }
    }
    done(1,1,n);
    for (int i=1;i<=n;i++){
        printf("%lld\n",(ans[0][i]-ans[1][i])/2);
    }
    return 0;
}