楼房重建，但是画风奇怪
打死想不到正解但是能想到一车乱搞系列。
首先容易知道，一个点会被拦住当且仅当前面至少有一个点斜率大于它。
我：斜率这东西看着真不爽。支持离线？那我反手一个离散化啊。
（然后就此与依赖斜率性质的正解背道而驰，令人感慨）
然后就有了两个思路。
带修主席树
离线后离散化，值域范围降至 \(O(n)\) ，可以掏出权值线段树然后建主席树。
修改一个点后，直接权值线段树上二分算本次修改给后面带来的贡献就好了。
使用树状数组套主席树做到带修。
码量过大，赛时弃了。
搓（吉）出（老）来（师）的（线）乱（段）搞（树）
可以离线诶？
想到混凝土积木这题，并且注意到一个点是否被拦只与其前面的点有关，考虑离线后枚举每个点计算其对各个查询的贡献。
用线段树维护时间轴，那么每个点在这个时间轴上被拆成了若干个权值相等的区间。一次修改对应一段区间，所以区间总数是 \(O(m)\) 的。
从前往后枚举每个点，得到该点对应的区间后直接在当前线段树上查询&修改即可。
我们要做的就是两件事：
- 区间取 \(\max\)
- 查询区间是否存在子区间，使得该子区间 \(\max\) 小于指定权值
这个东西乍一看不能用线段树维护，因为失去了懒标记可以 “拦住” 区间修改的性质，很有可能一次区间修改当场 \(O(m)\) ，当场去世。
可不可以搞一个 “接近” 懒标记的实现，就是再维护一个 “区间 \(\max\) 的最小值”？设当前指定权值为 \(val\) ，这个最小值为 \(min\)，那么就有如下几种情况：
- \(val \le min\) ，那么整个区间都比 \(val\) 大，不会产生任何贡献，直接返回；
- \(val > max\) ，那么整个区间都比 \(val\) 小，打懒标记；
- \(min < val \le max\) ，递归修改；
这样貌似什么问题都没解决？毕竟递归修改最坏还是 \(O(m)\) 的？
再次注意，我们是在对时间轴操作，这个区间取 \(\max\) 是不带撤销的，意味着这个 \(\max\) 不会下降。
……？
也就是说，我们可以均摊地分析这个修改操作：修改失败显然会直接返回，不会产生贡献；而递归的情况只有一个节点最大值小于其父亲的最大值时发生，单个节点最多影响其 \(O(\log m)\) 个父亲，一次修改最多影响 \(O(\log m)\) 个节点，所以时间复杂度是 \(O(n \log^2 m)\) 。
于是就可以愉快地开始做了。考虑到加贡献操作也是区间修改，本来想再开一个线段树，忽然发现可以直接打差分标记然后返回，就选择了这种实现。
const ll maxn=2e5+5;
ll n,m;
ll ans[maxn];
namespace sgt{
#define mid ((l+r)>>1)
ll mn[maxn<<2],mx[maxn<<2],tag[maxn<<2];
void upd(ll x){
mn[x]=min(mn[x<<1],mn[x<<1|1]);
mx[x]=max(mx[x<<1],mx[x<<1|1]);
}
void push_down(ll x){
if(!tag[x])return ;
tag[x<<1]=max(tag[x<<1],tag[x]);
tag[x<<1|1]=max(tag[x<<1|1],tag[x]);
mn[x<<1]=max(tag[x],mn[x<<1]);
mn[x<<1|1]=max(tag[x],mn[x<<1|1]);
mx[x<<1]=max(tag[x],mx[x<<1]);
mx[x<<1|1]=max(tag[x],mx[x<<1|1]);
tag[x]=0;
}
void modify(ll x,ll l,ll r,ll ls,ll rs,ll val){
// cerr<<l<<" "<<r<<endl;
if(ls<=l&&r<=rs){
tag[x]=max(tag[x],val);
mx[x]=max(mx[x],val);
mn[x]=max(mn[x],val);
return ;
}
push_down(x);
if(ls<=mid)modify(x<<1,l,mid,ls,rs,val);
if(rs>mid)modify(x<<1|1,mid+1,r,ls,rs,val);
upd(x);
}
void query(ll x,ll l,ll r,ll ls,ll rs,ll val){
// cerr<<l<<" "<<r<<" "<<mx[x]<<" "<<mn[x]<<" "<<val<<endl;
if(ls<=l&&r<=rs){
if(val>mx[x]){
ans[l]++,ans[r+1]--;
return ;
}
if(val<=mn[x]){
return ;
}
push_down(x);
query(x<<1,l,mid,ls,rs,val);
query(x<<1|1,mid+1,r,ls,rs,val);
return ;
}
push_down(x);
if(ls<=mid)query(x<<1,l,mid,ls,rs,val);
if(rs>mid)query(x<<1|1,mid+1,r,ls,rs,val);
return ;
}
}
struct dat{
ll id,val;
}a[maxn<<1];
vector<dat>lst[maxn];
db b[maxn<<1];
ll tot;
void solve(){
n=R,m=R;
for(ll i=1;i<=m;i++){
a[i].id=R;
a[i].val=R;
b[++tot]=1.0*a[i].val/a[i].id;
}
sort(b+1,b+1+tot);
tot=unique(b+1,b+1+tot)-b-1;
for(ll i=1;i<=m;i++){
a[i].val=lower_bound(b+1,b+1+tot,1.0*a[i].val/a[i].id)-b;
lst[a[i].id].push_back((dat){i,a[i].val});
// wk(a[i].id),wk(a[i].val),we(i);
}
// cerr<<"ok"<<endl;
for(ll i=1;i<=n;i++){
ll p=0,val=0;
for(auto it:lst[i]){
// cerr<<i<<" "<<p<<" "<<it.id-1<<" "<<val<<endl;
sgt::query(1,0,m+1,p,it.id-1,val);
val=it.val;
p=it.id;
}
// cerr<<i<<endl;
// cerr<<i<<" "<<p<<" "<<n+m+1<<" "<<val<<endl;
if(lst[i].size())sgt::query(1,0,m+1,lst[i][lst[i].size()-1].id,m+1,val);
p=val=0;
for(auto it:lst[i]){
sgt::modify(1,0,m+1,p,it.id-1,val);
val=it.val;
p=it.id;
}
if(lst[i].size())sgt::modify(1,0,m+1,lst[i][lst[i].size()-1].id,m+1,val);
// cerr<<"ok "<<i<<endl;
}
ll cnt=0;
for(ll i=1;i<=m;i++){
ans[i]+=ans[i-1];
cnt++;
we(ans[i]);
}
return ;
}
……赛后和出题人对了一下解法，意外地发现做法不一样。去看了题解区发现我搓出来的这个东西好像是叫吉老师线段树。
大受震撼。
原文地址：http://www.cnblogs.com/rnfmabj/p/p4198.html
