Problem

连号区间数

给一个排列，问有多少个区间值域连续。
$n\leq 50000$

Two Segments

https://www.luogu.org/problemnew/show/CF193D

Solution

连号区间数

考虑 $f_{l,r}$ 为 自然数区间 $[l,r]$ 在 给定排列 中被分割成多少块。

我们需要统计 $f_{l, r}=1$ 的 $(l,r)$ 二元组个数。

考虑移动 $l\rightarrow l-1$，则考察 $f_{l, r}$ 的变化。

如果新加入的数 $l-1$ 在给定排列中与 $[l,r]$ 中有一个相邻：$f_{l-1,r}=f_{l,r}$

若有两个相邻：$f_{l-1,r}=f_{l,r}-1$

若都不相邻：$f_{l-1,r}=f_{l,r}+1$

令 $b_i=f_{l, i}$，则我们从大到小移动指针 $l$。考虑新加入的 $l$ 在原序列的左右两边为 $x,y$。假设 $l< x< y$，则一定有：
$$b_i=\left\{\begin{matrix} b_j+1 &\ (l\leq i< x) \\ b_j &\ (x\leq i < y) \\ b_j-1 &\ (y\leq i < n) \end{matrix}\right.$$

移动 $l$，线段树维护查询即可。

CF193D

多维护一个 $f_{l, r}=2$ 即可。

Code

// Code by ajcxsu
// Problem: two segments

#include<bits/stdc++.h>
using namespace std;

#define ls x<<1
#define rs x<<1|1
const int N=3e5+10;
int mi[N<<3], tol[N<<3], tol2[N<<3], tag[N<<3];
void pup(int x) {
    mi[x]=min(mi[ls], mi[rs]);
    tol[x]=(mi[ls]==mi[x])*tol[ls]+(mi[rs]==mi[x])*tol[rs];
    tol2[x]=(mi[ls]==mi[x]+1)*tol[ls]+(mi[rs]==mi[x]+1)*tol[rs];
    tol2[x]+=(mi[ls]==mi[x])*tol2[ls]+(mi[rs]==mi[x])*tol2[rs];
}
void pud(int x) {
    if(!tag[x]) return;
    mi[ls]+=tag[x], tag[ls]+=tag[x];
    mi[rs]+=tag[x], tag[rs]+=tag[x];
    tag[x]=0;
}
void build(int x, int l, int r) {
    if(l==r) { tol[x]=1; return; }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    pup(x);
}
void updata(int x, int l, int r, int xl, int xr, int d) {
    pud(x);
    if(xl<=l && r<=xr) { tag[x]+=d, mi[x]+=d; return; }
    int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr, d);
    if(xr>mid) updata(rs, mid+1, r, xl, xr, d);
    pup(x);
}
int query(int x, int l, int r, int xl, int xr) {
    pud(x);
    if(xl<=l && r<=xr) return (mi[x]<=2)*tol[x]+(mi[x]==1)*tol2[x];
    int mid=(l+r)>>1, ret=0;
    if(xl<=mid) ret+=query(ls, l, mid, xl, xr);
    if(xr>mid) ret+=query(rs, mid+1, r, xl, xr);
    return ret;
}

int a[N], p[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i], p[a[i]]=i;
    build(1, 1, n);
    int x, y;
    long long ans=0;
    for(int i=n;i>=1;i--) {
        x=a[p[i]-1], y=a[p[i]+1];
        if(x>y) swap(x, y);
        if(i<x) updata(1, 1, n, i, x-1, 1), updata(1, 1, n, y, n, -1);
        else if(i<y) updata(1, 1, n, i, y-1, 1);
        else updata(1, 1, n, i, n, 1);
        ans+=query(1, 1, n, i, n);
    }
    cout<<ans-n<<endl;
    return 0;
}