区间切割
_O_v_O_
·
·
算法·理论
第一次知道算法理论也可以投 luogu 没有的难题的题解。
题目：互测 2023，强烈谴责洛谷不搬这题。
:::info[题面]
有 n 个值域为 m 的区间 [L_i,R_i]，然后有 m 次切割操作，每次操作由三元组 (x,l,r) 描述，对 i\in[l,r] 进行如下操作：
- 如果 x\notin [L_i,R_i]，那么啥都不做。
- 如果 x\in[L_i,R_i]，那么将 [L_i,R_i] 切成 [L_i,x],[x,R_i]。将其中较长的区间作为新的 [L_i,R_i]。
保证 x 构成一个排列。最后输出每个区间。
:::
# sol
从部分分入手。
- 性质 A：$x$ 随机生成。
- 性质 B：操作 $l=1,r=n$。
## 性质 A+B
这个东西在线没啥前途啊，考虑离线。
注意到 $x$ 随机。充分发扬人类智慧，猜测切割次数不多。
证明：
> 把整个区间分成四半，有 $\frac12$ 的概率切到中间两部分，$\frac12$ 的概率切到边上两部分。
>
> 注意到切到中间那么转化一下问题，一个区间，有 $\frac12$ 的概率不变，有 $\frac12$ 的概率将区间长度 $\times \frac34$。
>
> 那么期望 $2\log_{\frac34} m$ 次就能将区间变为 $1$。
>
> 因此切割次数 $O(\log m)$。
那么对于一个 $[L_i,R_i]$，我们每次找到处于 $[L_i,R_i]$ 的最先切点，然后用这个切点切割下去，一直递归。
考虑用线段树维护寻找切点的过程，时间复杂度 $O(m\log m+n\log^2 m)$，当然也可以用 ST 表，$O((n+m)\log m)$。
## 性质 A
全局操作没有了，怎么办？
我们发现，这个操作挺吻合扫描线的性质的，具体的，扫描线的过程可以套用在刚刚的过程中，把修改挂在 $l,r$ 上。有 $l$ 了再往线段树上加入当次的 $x$。有 $r$ 了再把 $x$ 给消掉。
所以还是用线段树维护扫描线 $x$，时间复杂度 $O(m\log m+n\log^2 m)$。
## 性质 B
止步于此。
不随机了，所以考虑优化切割过程。
把整个区间三分（这是人？），然后考虑只看落在区间中间的切割。
为啥？因为注意到假如落在了两边的部分，我们会发现，中间肯定会保留下来。
那么我们设三分出来的三个区间为 $[L_i,x],[x,y],[y,R_i]$，设 $[x,y]$ 的最小值为 $t$，那么我们要找到 $[L_i,x]$ 和 $[y,R_i]$ 中，最靠近中间的时间 $\le t$ 的切点。
考虑线段树上二分，具体的，维护一下区间时间最小值，然后看哪边最小时间 $\le t$，优先选靠近中间的区间。
那么时间复杂度还是 $O(m\log m+n\log^2 m)$。
## AC
那么就很简单了。
把上面两个性质融合起来，在线段树上二分的同时维护扫描线，很容易。
时间复杂度是 $O(m\log m+n\log^2 m)$。
:::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=1e5+5,M=1e6+5,inf=1e9;
int n,q,_;
int L[N],R[N];
int w[M];
vector<pii> ins[M];
vector<int> del[M];
struct node{
int l,r;
int mn;
}tr[M<<2];
#define lid id<<1
#define rid id<<1|1
void pushup(int id){tr[id].mn=min(tr[lid].mn,tr[rid].mn);}
void build(int id,int l,int r){
tr[id].l=l,tr[id].r=r;
if(l==r){tr[id].mn=inf;return;}
int mid=l+r>>1;
build(lid,l,mid),build(rid,mid+1,r);
pushup(id);
}
void change(int id,int x,int y){
if(tr[id].l==tr[id].r){tr[id].mn=y;return;}
int mid=tr[id].l+tr[id].r>>1;
if(x<=mid) change(lid,x,y);else change(rid,x,y);
pushup(id);
}
int qmn(int id,int l,int r){
if(l<=tr[id].l&&tr[id].r<=r) return tr[id].mn;
int mid=tr[id].l+tr[id].r>>1,res=inf;
if(l<=mid) res=min(res,qmn(lid,l,r));if(r>mid) res=min(res,qmn(rid,l,r));
return res;
}
int ql(int id,int x){
if(tr[id].mn>=x) return -1;
if(tr[id].l==tr[id].r) return tr[id].l;
if(tr[rid].mn<x) return ql(rid,x);else return ql(lid,x);
}
int qr(int id,int x){
if(tr[id].mn>=x) return -1;
if(tr[id].l==tr[id].r) return tr[id].l;
if(tr[lid].mn<x) return qr(lid,x);else return qr(rid,x);
}
int dol(int id,int x,int y){
if(tr[id].r<=x) return ql(id,y);
int mid=tr[id].l+tr[id].r>>1;
if(x<=mid) return dol(lid,x,y);
int tot=dol(rid,x,y);if(tot!=-1) return tot;
return dol(lid,x,y);
}
int dor(int id,int x,int y){
if(tr[id].l>=x) return qr(id,y);
int mid=tr[id].l+tr[id].r>>1;
if(x>mid) return dor(rid,x,y);
int tot=dor(lid,x,y);if(tot!=-1) return tot;
return dor(rid,x,y);
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>q>>_;
for(int i=1;i<=n;i++) cin>>L[i]>>R[i];
for(int i=1;i<=q;i++){
int l,r;cin>>w[i]>>l>>r;
ins[l].push_back({w[i],i});
del[r].push_back(w[i]);
}
build(1,1,q);
for(int i=1;i<=n;i++){
for(auto j:ins[i]) change(1,j.first,j.second);
int l=L[i],r=R[i];
while(l+1<r){
int df1=(l+l+r+1)/3;
int df2=(l+r+r-1)/3;
int t=qmn(1,df1,df2);
int nl=dol(1,df1,t),nr=dor(1,df2,t);
if(nl!=-1)l=max(l,nl);
if(nr!=-1)r=min(r,nr);
if(t==inf) break;
if(w[t]-l>=r-w[t]) r=w[t];
else l=w[t];
}
cout<<l<<' '<<r<<endl;
for(auto j:del[i]) change(1,j,inf);
}
return 0;
}
```
:::