WC2024 水镜

考虑一张图，如下建边：

• \(h_i<h_{i+1}\)：\((i,0)\to (i+1,0)\)

• \(h_i>h_{i+1}\)：\((i,1)\to (i+1,1)\)

• \(h_i+h_{i+1}<L\)：\((i,0)\to (i+1,1)\)

• \(h_i+h_{i+1}>L\)：\((i,1)\to (i+1,0)\)

所以说边只会改变 \(n\) 次，一共 \(2n\) 条边。

对于每张图需要求出 \(\sum (f_u-u+1)\) 即可，其中 \(f_u\) 是每张图中 \(u\) 向右最远的扩展点。

尝试维护这个东西。

会发现 \(00\) 或 \(11\) 一定存在，将 \(L\) 从小往大扫描，于是一定是从 \(10\to 01\)。

于是一定可以钦定出若干个 \(i\) 一定是 \(0\)，\(i\) 一定是 \(1\) 这样的，这样如果存在矛盾就可以确定当前每一个点的最远延伸距离，可以做到 \(O(n^2)\)。

考虑无解的情况，共三种：

• \(h_i=h_{i+1}\)，\(h_i+h_{i+1}=L\)，也就意味着对于 \(h_i=h_{i+1}\)，\(L\not=h_i+h_{i+1}\)；

• \(h_{i-1}<h_i\)，\(h_{i-1}+h_{i}>L\)，\(h_i>h_{i+1}\)，\(h_{i}+h_{i+1}>L\)；

• \(h_{i-1}>h_i\)，\(h_{i-1}+h_{i}<L\)，\(h_i<h_{i+1}\)，\(h_{i}+h_{i+1}<L\)；

容易发现后两种都对应一个关于 \(L\) 的取值范围，第一种可以不用管，同时这个题 \(r\) 肯定关于 \(l\) 单调，于是枚举 \(l\) 之后二分即可，对于取值范围可以用 ST 表维护，\(O(n\log n)\)。

不得不说，我 WC 打得真唐，希望省选别这样发挥，不然真寄了。

/*
Author: cnyz
世界があたしを拒んでも今 愛の唄 歌わせてくれないかな
*/
#include<bits/stdc++.h>
using namespace std;

using db=double;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
using ull=unsigned long long;

#define fi first
#define se second
#define gc getchar
#define pb emplace_back
#define mkp make_pair
#define push emplace
#define sz(a) (int)a.size()
#define all(p) p.begin(),p.end()
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

void chkmax(int &x,int y) {if(x<y) x=y;}
void chkmin(int &x,int y) {if(x>y) x=y;}
void chkmax(ll &x,ll y) {if(x<y) x=y;}
void chkmin(ll &x,ll y) {if(x>y) x=y;}

const int N=5e5+5;
const ll inf=1e13;
ll h[N],mi[N][20],ma[N][20];
ll qma(int l,int r) {
    int k=__lg(r-l+1);
    return max(ma[l][k],ma[r-(1<<k)+1][k]);
}
ll qmi(int l,int r) {
    int k=__lg(r-l+1);
    return min(mi[l][k],mi[r-(1<<k)+1][k]);
}
void solve() {
    int n; cin>>n;
    FOR(i,1,n) cin>>h[i];
    FOR(i,1,n) mi[i][0]=inf,ma[i][0]=-inf;
    FOR(i,2,n-1) {
        if(h[i]>=h[i+1]&&h[i]>=h[i-1]) ma[i][0]=h[i]+min(h[i-1],h[i+1]);
        if(h[i]<=h[i+1]&&h[i]<=h[i-1]) mi[i][0]=h[i]+max(h[i-1],h[i+1]);
    }
    FOR(j,1,19) FOR(i,1,n-(1<<j)+1)
        ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]),
        mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
    ll o=0;
    FOR(i,1,n-1) {
        int R=i+1,l=i+2,r=n;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(qma(i+1,mid-1)<qmi(i+1,mid-1)) l=mid+1,R=mid;
            else r=mid-1;
        }
        o+=R-i;
    }
    cout<<o<<"\n";
}

bool Med;
int main() {
    ios::sync_with_stdio(false),cin.tie(0);
    // fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
    int T=1;
    while(T--) solve();
    // fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
}