CF193D Two Segments [线段树]
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://pst.iorinn.moe/archives/sol-cf-193D.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆