小小小朋友的小小世界

题意

题目说的比较复杂，可以理解为一个地层对应一个点（它的右端点），然后再根据题面理解。注意所求的答案实际上就是地层的原层数。

做法

题面如此复杂，我们考虑离线后倒过来处理。这样子实际上要维护的只有一条线的变化，也就是所有 $y=0$ 上的点的原本位置。

然而两种操作还是很不清晰，我们对坐标系做一个变化，把 $A(x,y)$ 变为 $A'(x-y,x+y)$，也可以理解为做一个 $45$ 度的旋转。

这样来看，两种操作就变得非常清晰，它们是这样的：

对于 $A(x,y)\rightarrow A'(m=x-y,n=x+y)$ 满足 $y-x\geq X_i\rightarrow m\leq X_i$，$A(x+L_i,y+L_i)\rightarrow A'(m,n+2L_i)$。

对于 $A(x,y)\rightarrow A'(m=x-y,n=x+y)$ 满足 $x+y> X_i\rightarrow n> X_i$，$A(x+L_i,y+L_i)\rightarrow A'(m+2L_i,n)$。

倒过来做分别是这样的：

把所有横坐标（变换后）小于等于询问中的 $X_i$ 的点的纵坐标减去 $2L$。

把所有纵坐标（变换后）大于询问中的 $X_i$ 的点的横坐标加上 $2L$。

可以看出，这样操作后，原本点的顺序关系不会变化，即 $i<j$ 时 $X_i<X_j$，$Y_i<Y_j$。

于是我们可以想到二分。这道题数据比较一般，我们直接用两棵线段树分别维护每个点的变换后的横纵坐标，按照给出的操作进行修改，并直接在线段树上暴力二分，然后再把答案转换回来。在 O2 加持下可通过此题。

代码

#include<bits/stdc++.h>
#define int long long
const int N=2e5,inf=1e16;
using namespace std;
int seg[2][8*N+5],tag[2][8*N+5],n;
int quer[3][N+5];
void build(int id,int l,int r){
    if(l==r) {
        seg[0][id]=seg[1][id]=l;//第0层的点变换后坐标为(i,i)
        return ;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}
void push_down(int tp,int id){
    seg[tp][id*2]+=tag[tp][id];
    seg[tp][id*2+1]+=tag[tp][id];
    tag[tp][id*2]+=tag[tp][id];
    tag[tp][id*2+1]+=tag[tp][id];
    tag[tp][id]=0;
}
void update(int typ,int id,int x,int y,int l,int r,int L){
    if(l>r) return;
    if(r==n+1) r=n;
    if(l<=x&&y<=r){
        seg[typ][id]+=L;
        if(x!=y)tag[typ][id]+=L;
        return ;
    }
    int mid=(x+y)>>1;
    if(l<=mid) update(typ,id*2,x,mid,l,r,L);
    if(r>mid) update(typ,id*2+1,mid+1,y,l,r,L);
}
int ask(int typ,int id,int x,int y,int l){//线段树板子
    if(x==y) 
        return seg[typ][id];
    int mid=(x+y)>>1;
    push_down(typ,id);
    if(l<=mid) return ask(typ,id*2,x,mid,l);
    else return ask(typ,id*2+1,mid+1,y,l);
}
int searc(int typ,int x){//暴力二分出第一个大于 x 的位置
    int l=1,r=n+1;//注意边界条件
    while(l<r){
        int mid=(l+r)>>1;
        if(ask(typ,1,1,n,mid)>x) r=mid;
        else l=mid+1;
    }
    return l;
}
signed main(){
    ios::sync_with_stdio(0);
    int q;cin>>n>>q;
    build(1,1,n);
    for(int i=1;i<=q;i++) cin>>quer[0][i]>>quer[1][i]>>quer[2][i];
    for(int i=q;i>=1;i--){
        int typ=quer[1][i]-1,x=quer[0][i],L=quer[2][i];
        if(typ==0){
            int pos=searc(0,x);
            update(1,1,1,n,1,pos-1,-2*L);
        }
        else {
            int pos=searc(1,x);
            update(0,1,1,n,pos,n,2*L);
        }
    }
    for(int i=1;i<=n;i++){
        cout<<(ask(0,1,1,n,i)-ask(1,1,1,n,i))/2<<endl;//将变换后坐标变换回去 解方程组可得此式
    }
    return 0;
}

不理解可主页询问，我会尽快解答。