LGP6655 [YsOI2020] 制高 - Sol

zls_XICK · 2026-10-22 23:11:37 · 题解

Preface

这题的题解通道可以关闭了其实，没啥新东西了，本质简单题。

题目的 h_i 没给下界啊，离散化用朴素去重时：

for(int i=1;i<=n;i++)
  if(i==1||H[i]!=H[i-1])H[++t]=H[i];

这里的 i==1 还是很必要的，蒟蒻没看出来调了半小时。

这里提供两种解法，主席树与分块（似乎没人写分块，尽管它更简单）。

主席树

根据期望题的常规思考，我们记 f_i 为该点制高的期望。

由于 l_i \le r_i < i，不用担心环的问题，总方案数 all=\prod_{i=2}^n (r_i-l_i+1)，所以答案就是 all\times\sum_{i=1}^n f_i。

考虑转移，f_i 贡献来自其可成为制高的父节点，于是容易得到：

根节点则初始化 f_1=1，因为它必然制高。

对 h_i 离散化后建主席树，转移时就是对 l_i-1、r_i 两个版本的树求 1 \sim h_i 区间和，不会的回去重练一遍板子。

复杂度 O(n \log n)。

::::success[AC Code]

#include <bits/stdc++.h>
#define zls rp++
#define ll long long
#define pii pair<ll,int>
using namespace std;
const int inf=2e9;
const ll md=998244353;
const double eps=1e-7;
int n,h[100005],H[100005],t=0,id=0;
ll f[100005],all=1,ans=0;//f[i]:i制高的期望 
ll power(ll x,ll exp){
    ll res=1;
    while(exp)(exp&1)?res=(res*x)%md:1,exp>>=1,x=(x*x)%md;
    return res;
}
struct node{int l,r;}p[100005];
struct tree{int ls,rs;ll w;}tr[4000005];
int copy(int x){tr[++id]=tr[x];return id;}
int change(int x,int l,int r,int pos,ll v){
    x=copy(x);
    if(l==r){tr[x].w=(tr[x].w+v)%md;return x;}
    int mid=(l+r)/2;
    pos<=mid?tr[x].ls=change(tr[x].ls,l,mid,pos,v)
            :tr[x].rs=change(tr[x].rs,mid+1,r,pos,v);
    tr[x].w=(tr[tr[x].ls].w+tr[tr[x].rs].w)%md;
    return x;
}
ll fd(int lx,int rx,int l,int r,int ql,int qr){
    if(ql>qr)return 0;
    if(l>=ql&&r<=qr)return (tr[rx].w-tr[lx].w+md)%md;
    ll res=0;int mid=(l+r)/2;
    res=(res+(ql<=mid?fd(tr[lx].ls,tr[rx].ls,l,mid,ql,qr):0)
            +(qr> mid?fd(tr[lx].rs,tr[rx].rs,mid+1,r,ql,qr):0))%md;
    return res;
}
int rt[100005];
void work(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i],H[i]=h[i];
    sort(H+1,H+1+n);
    for(int i=1;i<=n;i++)if(i==1||H[i]!=H[i-1])H[++t]=H[i];
    for(int i=1;i<=n;i++)h[i]=lower_bound(H+1,H+1+t,h[i])-H;
    for(int i=2;i<=n;i++)cin>>p[i].l>>p[i].r,
                         all=all*(p[i].r-p[i].l+1)%md;
    //ans=all*sum(f[i])
    //f[i]=sum(f[j])/(r[i]-l[i]+1) (h[j]<=h[i])
    f[1]=1;
    rt[1]=change(rt[0],1,t,h[1],1);
    ans=all;
    for(int i=2;i<=n;i++){
        ll Z=fd(rt[p[i].l-1],rt[p[i].r],1,t,1,h[i]);
        ll F=power(p[i].r-p[i].l+1,md-2);
        f[i]=Z*F%md;
        rt[i]=change(rt[i-1],1,t,h[i],f[i]);
        ans=(ans+f[i]*all)%md;
    }
    cout<<ans;
}
int main(){
    //freopen("ansin.in","r",stdin);
    //freopen("ansout.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    work();
    return 0;
}

::::

分块

笔者本人是不喜欢分块的，但是它思维和代码都很简单。

我们把目光放到 h_i 上，以它排序，接下来的转移就不需要考虑高度的约束了。

因为能提供转移的 j 高度是不大于 h_i 的，所以按这个顺序处理是正确的。

类似的式子：

对于 l_i、r_i 所在块简单分讨，同一个块就 O(\sqrt n) 暴力加，不同块就把两边的散块 O(\sqrt n) 暴力加，中间的整块二分找到位置后直接加前缀和。

然后更新新下标所在块的前缀和就行了，总复杂度 O(n \sqrt n \log \sqrt n)，但是常数小。

::::success[AC Code]

#include <bits/stdc++.h>
#define zls rp++
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const int inf=2e9;
const ll md=998244353;
const double eps=1e-7;
int n,sz,cnt,h[100005],l[100005],r[100005],ord[100005];
ll f[100005],all=1,ans=0;
vector<pii>B[1005];//{高度,f值}
vector<ll>pre[1005];//对应块的前缀和
ll power(ll x,ll exp){
    ll res=1;
    while(exp)(exp&1)?res=(res*x)%md:1,exp>>=1,x=(x*x)%md;
    return res;
}
void work(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    if(n==1){cout<<1;return;}
    for(int i=2;i<=n;i++)cin>>l[i]>>r[i],all=all*(r[i]-l[i]+1)%md;
    sz=sqrt(n),cnt=(n+sz-1)/sz;
    for(int i=1;i<=n;i++)ord[i]=i;
    sort(ord+2,ord+n+1,[](int a,int b){return h[a]==h[b]?a<b:h[a]<h[b];});
    f[1]=1;
    B[1].push_back({h[1], 1});
    pre[1].push_back(1);
    for(int i=2;i<=n;i++){
        int u=ord[i];
        int bl=(l[u]-1)/sz+1,br=(r[u]-1)/sz+1;
        ll sum=0;
        if(bl==br){
            for(int j=l[u];j<=r[u];j++)
                if(f[j]&&h[j]<=h[u])sum=(sum+f[j])%md;
        }else{
            for(int j=l[u];j<=bl*sz;j++)
                if(f[j]&&h[j]<=h[u])sum=(sum+f[j])%md;
            for(int j=(br-1)*sz+1;j<=r[u];j++)
                if(f[j]&&h[j]<=h[u])sum=(sum+f[j])%md;
            for(int k=bl+1;k<br;k++){
                int pos=upper_bound(B[k].begin(),B[k].end(),make_pair((ll)h[u],(ll)inf))-B[k].begin();
                if(pos>0)sum=(sum+pre[k][pos-1])%md;
            }
        }
        f[u]=sum*power(r[u]-l[u]+1,md-2)%md;
        int bu=(u-1)/sz+1;
        B[bu].push_back({h[u],f[u]});
        ll lst=pre[bu].empty()?0:pre[bu].back();
        pre[bu].push_back((lst+f[u])%md);
    }
    for(int i=1;i<=n;i++)ans=(ans+f[i])%md;
    cout<<ans*all%md;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    work();
    return 0;
}

::::