题解：P14528 [BYOI R1] 雨后屋檐

· · 题解

在模拟赛的时候用了一个自我感觉是紫的观察过了一道绿，不甘心。发现这题也可以用这个观察，而且这题是紫，于是就将其做掉，嘱以题解以记之。

思路

我们考虑把山画出图来：

蓝色的横线是水位线，不难发现积了水的部分可以被分成两类：

显然，对于被填满了的部分，无论水位线是多少，内部积的水量是固定的。对于位置 i 来说，我们记其后第一个高度大于等于 h_i 的位置为 nxt_i，则内部积的水量为：

h_i\times(nxt_i-i-1)-\sum_{k\in(i,nxt_i)}h_k

这是向后的部分，向前的部分也同样，我们把对应的积水量放到每一个位置上，这一部分可以通过两次单调栈求出。

我们把 i\to nxt_i 连一条边，则最终数列会呈现出森林的结构，于是被填满的水坑中的水我们就可以直接倍增跳树求出，时间复杂度单 \log。

现在考虑没被填满的部分怎么求？

考虑把整个图旋转 90\degree，我们可以得到：

现在，把纵轴看成是时间轴，横轴看成是值域，蓝色部分打上 1 的权值，则问题转化为了在某段时间中求值域上的一段前缀和。

这是什么？是可持久化线段树板子，时间复杂度单 \log，于是你就美美的做完了这一题。

实现细节

代码

写了不到 3k，还是很好实现的。

:::success[代码]

#include <iostream>
#include <cstdio>
#include <cassert>
#include <algorithm>
#define ll long long
#define mid ((l+r)>>1)
#define BUG cout<<"BUG\n";
using namespace std;
const ll N=5e5+10;
const ll V=1e9+2;
int lc[N*60],rc[N*60],tot,head[N];
ll sum[N*60],tag[N*60],h[N];
inline void push_up(int x,int l,int r){sum[x]=sum[lc[x]]+sum[rc[x]]+(ll)(l-mid+1)*tag[lc[x]]+(ll)(r-mid)*tag[rc[x]];}
void build(int &x,int lstx,int l,int r,int L,int R){
    if(!x) x=++tot;
    assert(tot<N*40);
    sum[x]=sum[lstx];
    tag[x]=tag[lstx];
    if(L<=l&&r<=R){
        tag[x]+=1;
        lc[x]=lc[lstx],rc[x]=rc[lstx];
        return;
    }
    if(L<=mid) build(lc[x],lc[lstx],l,mid,L,R);
    else lc[x]=lc[lstx];
    if(R>mid) build(rc[x],rc[lstx],mid+1,r,L,R);
    else rc[x]=rc[lstx];
    push_up(x,l,r);
}
ll query(int x,int l,int r,int L,int R,ll lazy){
    if(L<=l&&r<=R) return sum[x]+(ll)(r-l+1LL)*(lazy+tag[x]);
    ll ret=0;
    if(L<=mid) ret+=query(lc[x],l,mid,L,R,lazy+tag[x]);
    if(R>mid) ret+=query(rc[x],mid+1,r,L,R,lazy+tag[x]);
    return ret;
}
int nxt[N][20],stk[N],top,pre[N][20];
ll val_nxt[N],val_pre[N],presum[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll n,q,t;cin>>n>>q>>t;
    for(ll i=1;i<=n;i++){
        cin>>h[i];presum[i]=presum[i-1]+h[i];
        build(head[i],head[i-1],1,V,h[i]+1,V);
    }
    for(ll i=1;i<=n;i++){
        while(top&&h[i]>=h[stk[top]]){
            nxt[stk[top]][0]=i;
            val_nxt[stk[top]]=(ll)(i-stk[top]-1)*h[stk[top]];
            val_nxt[stk[top]]-=presum[i-1]-presum[stk[top]];
            top--;
        }
        stk[++top]=i;
    }
    for(ll i=n;i>=1;i--){
        for(ll j=1;j<20;j++) nxt[i][j]=nxt[nxt[i][j-1]][j-1];
        val_nxt[i]+=val_nxt[nxt[i][0]]; 
    }
    top=0;
    for(ll i=n;i>=1;i--){
        while(top&&h[i]>=h[stk[top]]){
            pre[stk[top]][0]=i;
            val_pre[stk[top]]=(ll)(stk[top]-i-1)*h[stk[top]];
            val_pre[stk[top]]-=presum[stk[top]-1]-presum[i];
            top--;
        }
        stk[++top]=i;
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<20;j++) pre[i][j]=pre[pre[i][j-1]][j-1];
        val_pre[i]+=val_pre[pre[i][0]];
    }
    ll lastans=0,ans=0;
    while(q--){
        ll lp,rp,Hp;
        cin>>lp>>rp>>Hp;
        lp^=t*lastans,rp^=t*lastans,Hp^=t*lastans;
        assert(lp<=rp&&lp<=n&&rp<=n&&lp>=1&&rp>=1&&Hp<=V);
        ll L=lp,R=rp;
        for(ll i=19;i>=0;i--){
            if(nxt[L][i]!=0&&nxt[L][i]<=rp&&h[nxt[L][i]]<Hp)
                L=nxt[L][i];
        }
        for(ll i=19;i>=0;i--){
            if(pre[R][i]!=0&&pre[R][i]>=lp&&h[pre[R][i]]<Hp&&pre[R][i]>=L)
                R=pre[R][i];
        }
        if(R==L){
            lastans=val_nxt[lp]-val_nxt[L]+val_pre[rp]-val_pre[R];
        }
        else{
            if(h[L]<Hp) L=nxt[L][0];
            if(h[R]<Hp) R=pre[R][0];
            lastans=val_nxt[lp]-val_nxt[L]+val_pre[rp]-val_pre[R];
            lastans+=query(head[R],1,V,1,Hp,0);
            lastans-=query(head[L-1],1,V,1,Hp,0);
        }
        ans^=lastans;
    }
    cout<<ans;
    return 0;
}

:::