P1901 发射站_牛客博客

看到这题我就想到了2018预赛的毒瘤双向链表。。。

然而现在我还是不会。

于是我用 $st$ 表水过了这题。

对于发射站 $i$ ，以找它左边第一个比它大的发射站为例：

我们可以通过二分来找到最大的 $l$ ，满足 $maxh(l,i-1)>h[i]$ 。

$maxh(l,r)$ 表示区间 $(l,r)$ 中的最大高度。

对于区间高度最小值，我们可以用线段树或者 $st$ 表来维护。

如果用线段树，预处理是 $O(nlogn)$ ，查询是 $O(nlognlogn)$ ，无法满足要求。

而 $st$ 表的查询是 $O(1)$ 的，就可以将总查询复杂度减小到 $O(nlogn)$ 。

于是复杂度就是 $O(nlogn)$ 。

#include<iostream>
#include<cstring>
#include<cstdio>
void read(int &s);
#define ll long long int
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int maxn=1000100;
int maxx(int a,int b){return a<b?b:a;}

int jie[maxn];
int n,h[maxn],v[maxn];
int st[maxn][23],lg2[maxn],mi2[23];
void csh(){
    memset(jie,0,sizeof(jie));
    lg2[1]=0;
    rep(i,2,n)
        lg2[i]=lg2[i/2]+1;
    mi2[0]=1;
    rep(k,1,lg2[n]+1)mi2[k]=mi2[k-1]+mi2[k-1];
    rep(i,1,n)st[i][0]=h[i];
    rep(k,1,lg2[n])
        for(int i=1;i+mi2[k]-1<=n;i++)
            st[i][k]=maxx(st[i][k-1],st[i+mi2[k-1]][k-1]);
}
int q(int l,int r){
    int k=lg2[r-l+1];
    return maxx(st[l][k],st[r-mi2[k]+1][k]);
}
int Ans=0;
void worrk(){
    rep(i,1,n){
        if(i!=1&&q(1,i-1)>h[i]){
            int l=1,r=i-1,mid;
            while(l<r){
                mid=(l+r+1)>>1;
                if(q(mid,i-1)>h[i])l=mid;
                else r=mid-1;
            }
            jie[l]+=v[i];
        }
        if(i!=n&&q(i+1,n)>h[i]){
            int l=i+1,r=n,mid;
            while(l<r){
                mid=(l+r)>>1;
                if(q(i+1,mid)>h[i])r=mid;
                else l=mid+1;
            }
            jie[l]+=v[i];
        }
    }
    rep(i,1,n)Ans=maxx(Ans,jie[i]);
    cout<<Ans;
}
int main(){
    read(n);
    rep(i,1,n)read(h[i]),read(v[i]);
    csh();
    worrk();
    return 0;
}
void read(int &s){
    s=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
}