题解：P16330 Just Because!
zhangwenyuxuan
·
·
题解
一棵树要么往左倒，要么往右倒，倒下后，它会覆盖一个区间，被它覆盖到的点上的树就不能再选了。
这样就可以将问题进行转化，把每种选树的方案转化为区间覆盖，每个区间可能是一棵树向左或向右倒得到的，贡献为 1，也有可能是两棵树向中间倒得到的，贡献为 2，我们要做的就是求出互不相交的覆盖方案，使得贡献之和最大。
贡献为 1 的区间是容易求的，二分找到树倒下时覆盖的最后一个点即可。贡献为 2 的区间总数是 O(n^2) 的，但以同一个点为左端点的区间中，显然只有最小的是最优的，所以我们可以对于每个点，找到它右边第一个不被它覆盖到并且不覆盖它的点。我们设 nx_{i,0/1} 为以 i 为左端点，贡献为 1 或 2 的区间的右端点。
处理完全部的区间后，可以用倍增求出答案，设 f_{i,j} 表示以 i 为左端点选择贡献为 2^j 的区间的最小右端点，由于区间的贡献可能是 2，转移与一般的倍增有所区别，还需要一个 g_{i,j} 表示以 i 为左端点选择贡献为 2^j-1 的区间的最小右端点。
现在考虑转移，2^j 可能由两个 2^{j-1} 拼成，也可能由 2^{j-1}-1 和 2^{j-1}+1 拼成，所以：
f_{i,j}=\min(f_{f_{i,j-1}+1,j-1},g_{nx_{g_{i,j-1}+1,1}+1,j-1})
$$
g_{i,j}=\min(g_{f_{i,j-1}+1,j-1},f_{g_{i,j-1}+1,j-1})
$$
对于一个区间 $[l,r]$，$l,r$ 分别往两边倒，一定都可以取到，只需要考虑 $[l+1,r-1]$。在倍增求答案时，也要考虑两种情况，若起点为 $a$，$x$ 表示从 $a$ 开始走到的位置，$y$ 表示从 $nx_{a,0}+1$ 开始走到的位置，考虑加入 $2^i$。
$$
x'=\min(f_{x,i},g_{y,i})+1\\
y'=\min(f_{y,i},g_{nx_{x,1},i})+1
$$
若 $y'\le r$ 则将 $x,y$ 分别赋值为 $x',y'$，并将答案增加 $2^i$，由于我们保证的是 $y\le r$，所以最终的答案还要加上 $1$。
:::info[参考代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,q,p[N],h[N],nx[N][2],f[N][20],g[N][20];
struct node1{
int p,id;
bool operator <(node1 x)const{
return p>x.p;
}
};
priority_queue<node1>pq;
struct node2{
int p,id;
bool operator <(node2 x)const{
if(p==x.p){
return id<x.id;
}
return p<x.p;
}
};
set<node2>s;
int nxt(int x){
return x==n+1?n+1:x+1;
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>p[i];
}
for(int i=1;i<=n;i++){
cin>>h[i];
}
for(int i=1;i<=n+1;i++){
nx[i][0]=nx[i][1]=n+1;
}
for(int i=1;i<=n;i++){
int x=upper_bound(p+1,p+n+1,p[i]+h[i])-p-1;
nx[i][0]=min(nx[i][0],x);
x=lower_bound(p+1,p+n+1,p[i]-h[i])-p;
nx[x][0]=min(nx[x][0],i);
}
for(int i=1;i<=n;i++){
pq.push({p[i]-h[i],i});
s.insert({p[i],i});
}
for(int i=1;i<=n;i++){
while(!pq.empty()&&pq.top().p<=p[i]){
int x=pq.top().id;
pq.pop();
s.erase({p[x],x});
}
if(!s.empty()){
auto x=s.upper_bound({p[i]+h[i],i});
if(x!=s.end()){
nx[i][1]=min(nx[i][1],(*x).id);
}
}
}
for(int i=n;i;i--){
nx[i][0]=min(nx[i][0],nx[i+1][0]);
nx[i][1]=min(nx[i][1],nx[i+1][1]);
f[i][0]=nx[i][0];
g[i][0]=i-1;
}
for(int i=0;i<20;i++){
f[n+1][i]=g[n+1][i]=n+1;
}
for(int j=1;j<20;j++){
for(int i=n;i;i--){
f[i][j]=min(f[nxt(f[i][j-1])][j-1],g[nxt(nx[nxt(g[i][j-1])][1])][j-1]);
g[i][j]=min(f[nxt(g[i][j-1])][j-1],g[nxt(f[i][j-1])][j-1]);
}
}
while(q--){
int l,r;
cin>>l>>r;
if(nx[nxt(l)][0]>=r){
cout<<(l==r?1:2)<<"\n";
continue;
}
int x=nxt(l),y=nxt(nx[nxt(l)][0]),ans=2;
for(int i=19;i>=0;i--){
int a=nxt(min(f[x][i],g[y][i]));
int b=nxt(min(f[y][i],g[nxt(nx[x][1])][i]));
if(b>r){
continue;
}
x=a;
y=b;
ans+=1<<i;
}
cout<<ans+1<<"\n";
}
return 0;
}
```
:::