ABC-382-F - Falling Bars · znzryb
## 思路讲解
```
// 首先，上面的块是不会影响下面的块，只有下面的块影响上面的块的份
// 思路其实也不复杂，就是看在这个块下面的块中最高的在哪里。
// 相当于一个range最小值查询，需要用线段树区间修改
```
## AC代码
[https://atcoder.jp/contests/abc382/submissions/64644331](https://atcoder.jp/contests/abc382/submissions/64644331)
::: 源代码
```cpp
// Problem: F - Falling Bars
// Contest: AtCoder - AtCoder Beginner Contest 382
// URL: https://atcoder.jp/contests/abc382/tasks/abc382_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
ll N,H,W;
struct BAR{ // 之前的代码，直接在这个结构体当中重载
ll x,y,len,idx;
bool operator<(const BAR &other) const{
if(x!=other.x) return x>other.x;
if(y!=other.y) return y<other.y;
if(len!=other.len) return len<other.len;
return false;
}
};
struct SegTreeRMQ{
ll l=0,r=0,val=INF;
}tr[MAXN*4];
ll lazy[MAXN*4];
inline ll ls(ll x){return x<<1;}
inline ll rs(ll x){return x<<1|1;}
inline bool isDisj(ll l,ll r,ll l_,ll r_){ // 是否不相交，isDisjoint
return (r_<l || l_>r);
}
inline void pushdown(ll node){
if(tr[node].l==tr[node].r) return;
if(lazy[node]!=0){
tr[ls(node)].val=lazy[node];
tr[rs(node)].val=lazy[node];
lazy[ls(node)]=lazy[node];
lazy[rs(node)]=lazy[node];
lazy[node]=0;
}
}
inline void pushup(ll node){
node>>=1;
while(node){
tr[node].val=min(tr[ls(node)].val,tr[rs(node)].val);
node>>=1;
}
}
void build(ll node,ll l,ll r){
if(l>r) return;
if(l==r){
tr[node].l=l;
tr[node].r=r;
return;
}
ll mid=l+r>>1;
tr[node].l=l;
tr[node].r=r;
build(ls(node),l,mid);
build(rs(node),mid+1,r);
}
void modify(ll node,ll l,ll r,ll val){
if(isDisj(l,r,tr[node].l,tr[node].r)) return;
pushdown(node);
if(l<=tr[node].l && tr[node].r<=r){
tr[node].val=val;
lazy[node]=val;
pushup(node);
return;
}
if(!isDisj(l,r,tr[ls(node)].l,tr[ls(node)].r)) modify(ls(node),l,r,val);
if(!isDisj(l,r,tr[rs(node)].l,tr[rs(node)].r)) modify(rs(node),l,r,val);
}
ll query(ll node,ll l,ll r){
if(isDisj(l,r,tr[node].l,tr[node].r)) return INF;
pushdown(node);
if(l<=tr[node].l && tr[node].r<=r){
return tr[node].val;
}
ll res=INF;
if(!isDisj(l,r,tr[ls(node)].l,tr[ls(node)].r)) res=min(res,query(ls(node),l,r));
if(!isDisj(l,r,tr[rs(node)].l,tr[rs(node)].r)) res=min(res,query(rs(node),l,r));
return res;
}
ll ans[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>H>>W>>N;
vector<BAR> bar(N+5,(BAR){0,0,0});
FOR(i, 1, N){
cin>>bar[i].x>>bar[i].y>>bar[i].len;
bar[i].idx=i;
}
sort(bar.begin()+1,bar.begin()+1+N);
// 首先，上面的块是不会影响下面的块，只有下面的块影响上面的块的份
// 思路其实也不复杂，就是看在这个块下面的块中最高的在哪里。
// 相当于一个range最小值查询，需要用线段树区间修改
build(1,1,W);
FOR(i,1,N){
ll x=bar[i].x,y=bar[i].y,len=bar[i].len,idx=bar[i].idx;
ll res=query(1,y,y+len-1);
if(res==INF) ans[idx]=H;
else ans[idx]=res-1;
modify(1,y,y+len-1,ans[idx]);
// #ifdef LOCAL
// FOR(i,1,W*4){
// cerr<<tr[i].l<<" "<<tr[i].r<<" "<<tr[i].val<<"\n";
// }
// cerr<<"\n";
// #endif
}
FOR(i,1,N){
cout<<ans[i]<<"\n";
}
return 0;
}
/*
AC
https://atcoder.jp/contests/abc382/submissions/64644331
*/
```
:::
## 心路历程（WA，TLE，MLE……）