CF193D Two Segments [线段树]

ajcxsu
ajcxsu 2018年10月31日
  • 58 次阅读

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;
}

本文链接:https://acxblog.site/archives/sol-cf-193D.html
本文采用 CC BY-NC-SA 3.0 协议进行许可