P11094 题解

· · 题解

Problem Link

题目大意

给定 n 棵树，位置在 a_1\sim a_n，一棵树能被砍当且仅当 (a_i-h_i,a_i] 或 [a_i,a_i+h_i) 中没有未被砍的树，且 a_i-h_i/a_i+h_i 不能超过出 [a_1,a_n] 的范围。

数据范围：$n,q\le 5\times 10^5$。

思路分析

对每棵树 i 分别考虑，容易发现一棵树能向左砍，当且仅当 (a_i-h_i,a_i] 中的其他树要么可以向右砍，要么可以在 [l,i] 范围内向左砍。

不难发现 i 能向左看当且仅当 L_i\ge l，其中 L_i 表示：如果想让 i 向左砍，至少要砍掉左边多少树，同理能求出 R_i。

我们要求的就是有多少 l\le L_i\le i\le r 或者 l\le i\le R_i\le r。

考虑二维数点，拆成 [L_i,i],[i,R_i] 两个线段，被包含答案 +1，为了去重，包含 [L_i,R_i] 的答案还要 -1。

然后考虑如何求 L_i：从 j=i-1 开始，如果 a_i-h_i<a_j，那么需要砍掉 j：

那么 L_i=j+1，容易发现我们只要求出 a_j+h_j>a_i 的线段并之外的第一个元素，线段树维护。

另一种做法是整体二分，即枚举一个左端点 l，从 l 出发尝试砍掉每棵树，用一个栈维护上面的过程，判断每个树能不能向左砍就知道 L_i\ge l 是否成立。

容易发现 L_i<l,L_i\ge l 的两部分点互不影响，然后可以直接递归。

时间复杂度 \mathcal O((n+q)\log n)。

代码查询

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+5;
int n,q,a[MAXN],h[MAXN],L[MAXN],R[MAXN],ans[MAXN];
vector <int> o[MAXN];
vector <array<int,2>> ql[MAXN],qr[MAXN];
struct FenwickTree {
    int tr[MAXN],s;
    void init() { memset(tr,0,sizeof(tr)); }
    void add(int x) { for(;x;x&=x-1) ++tr[x]; }
    int qry(int x) { for(s=0;x<=n;x+=x&-x) s+=tr[x]; return s; }
}   T;
int f[MAXN],stk[MAXN],tp;
void solve(int l,int r,const vector<int>&id) {
    if(l==r) {
        for(int x:id) f[x]=l;
        return ;
    }
    int mid=(l+r+1)>>1;
    stk[tp=0]=mid-1;
    vector <int> li,ri;
    for(int i:id) {
        if(i<mid) { li.push_back(i); continue; }
        while(tp&&a[stk[tp]]+h[stk[tp]]<=a[i]) --tp;
        if(a[stk[tp]]>a[i]-h[i]) li.push_back(i),stk[++tp]=i;
        else ri.push_back(i);
    }
    solve(l,mid-1,li),solve(mid,r,ri);
}
signed main() {
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i) scanf("%d%d",&a[i],&h[i]);
    vector <int> id(n);
    iota(id.begin(),id.end(),1);
    a[0]=a[1],solve(0,n,id);
    for(int i=1;i<=n;++i) L[i]=f[i];
    reverse(a+1,a+n+1),reverse(h+1,h+n+1);
    for(int i=n;i;--i) a[i]*=-1;
    a[0]=a[1],solve(0,n,id);
    for(int i=1;i<=n;++i) R[n-i+1]=n-f[i]+1;
    for(int i=1,l,r;i<=q;++i) {
        scanf("%d%d",&l,&r),ql[l].push_back({r,i}),qr[r].push_back({l,i});
    }
    for(int i=1;i<=n;++i) o[R[i]].push_back(L[i]);
    for(int i=1;i<=n;++i) {
        T.add(L[i]);
        for(auto z:qr[i]) ans[z[1]]+=T.qry(z[0]);
    }
    T.init();
    for(int i=n;i>=1;--i) {
        T.add(n-R[i]+1);
        for(auto z:ql[i]) ans[z[1]]+=T.qry(n-z[0]+1);
    }
    T.init();
    for(int i=1;i<=n;++i) {
        for(int z:o[i]) T.add(z);
        for(auto z:qr[i]) ans[z[1]]-=T.qry(z[0]);
    }
    for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
    return 0;
}