题解

本题使用树状数组 + 二分 + 逆序操作求解断层变化问题。

算法思路：

1. 逆序处理：

   • 将所有操作倒序执行
   • 从最终状态开始，逆向模拟每个操作的影响
   • 这样可以避免处理复杂的中间状态

2. 两个树状数组：

   • T1：维护每个位置的"左侧累积值"
   • T2：维护每个位置的"右侧累积值"
   • 初始时所有位置的值都为 $1$

3. 操作处理：

   • 操作类型1（$d = 1$）：从左边抬升
     • 二分查找第 $x$ 个位置（基于 T1 的前缀和）
     • 对区间 $[1, pos]$ 进行差分更新：T2.add(1, -l), T2.add(pos+1, l)
   • 操作类型2（$d = 2$）：从右边抬升
     • 二分查找满足条件的位置（基于 T2 的前缀和）
     • 对该位置进行单点更新：T1.add(pos, l)

4. 二分查找：

   • 在树状数组上二分找到满足前缀和条件的位置
   • 对于类型1：找到最大的 $pos$ 使得 $T1.ask(pos) \leq x$
   • 对于类型2：找到最小的 $pos$ 使得 $T2.ask(pos) > x$

5. 答案计算：

   • 对于每个位置 $i$，答案为 $\frac{T1.ask(i) - T2.ask(i)}{2}$
   • 除以2是因为每个操作的长度 $l$ 在输入时乘以了2

时间复杂度：$O((n + q) \log n)$

这是一道结合了树状数组、二分查找和逆序思维的综合性问题。

//By smilemask
#include<bits/stdc++.h>
#include<ctime>
using namespace std;

namespace Smilemask{
#define rd read()
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> PII;
#define debug(...) fprintf(stderr, __VA_ARGS__)

    inline int read(){
        int num=0,sign=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-'){sign=-1;}ch=getchar();}
        while(isdigit(ch)) num=(num<<1)+(num<<3)+ch-'0',ch=getchar();
        return num*sign;
    }

    const int N=2e5+10;

    struct node{
        ll x,d,l;
    }a[N];
    int n,q;

    struct fenwick{
        ll t[N];
        void add(int x,int y){
            while(x<=n) t[x]+=y,x+=(x&(-x));
        }
        ll ask(int x){
            ll res=0;
            while(x) res+=t[x],x-=(x&(-x));
            return res;
        }
    }T1,T2;

    void Main(){
        n=rd,q=rd;
        for(int i=1;i<=q;i++)
            a[i].x=rd,a[i].d=rd,a[i].l=rd,a[i].l<<=1;
        for(int i=1;i<=n;i++)
            T1.add(i,1),T2.add(i,1);
        for(int j=q;j;j--){
            if(a[j].d==1){
                int l=1,r=n;
                while(l<r){
                    int mid=(l+r+1)>>1;
                    if(T1.ask(mid)<=a[j].x) l=mid;
                    else r=mid-1;
                }
                if(T1.ask(l)<=a[j].x)
                    T2.add(1,-a[j].l),T2.add(l+1,a[j].l);
            }else{
                int l=1,r=n;
                while(l<r){
                    int mid=(l+r)>>1;
                    if(T2.ask(mid)>a[j].x) r=mid;
                    else l=mid+1;
                }
                if(T2.ask(l)>a[j].x) T1.add(l,a[j].l);
            }
        }
        for(int i=1;i<=n;i++)
            printf("%lld\n",(T1.ask(i)-T2.ask(i))>>1);
    }
}

signed main(){
    Smilemask::Main();
    return 0;
}
/*
start thinking:

finish thinking:
*/