Codeforces Round #122 (Div. 1) D.Two Segments

发表于 更新于 分类于

链接

https://codeforces.com/contest/193/problem/D

题意

给一个$1 \sim n$ $(n\le 3e5)$ 的排列，在这个排列中选出两段不重合的区间，求使选出的元素排序后构成公差为 $1$ 的等差数列的方案数。

选出的两段区间中元素构成的集合相同时视为同一种方案。

思路

假设 $[l,r]$ 在排列中被分为不连续的 $k$ 段，此时加入 $r+1$，有如下情况：

  • $[l,r]$ 中没有数在排列中与 $r+1$ 相邻，那么 $[l,r+1]$ 被分为 $k+1$ 段。
  • $[l,r]$ 中有一个数在排列中与 $r+1$ 相邻，那么 $[l,r+1]$ 还是被分为 $k$ 段。
  • $[l,r]$ 中有两个数在排列中与 $r+1$ 相邻，那么会有两段合并，$[l,r+1]$ 被分为 $k-1$ 段。

线段树做法：

枚举右端点 $r$，记 $f_i$ 为 $[i,r]$ 在排列中被分为不连续的段数。

当 $1\le f_i\le 2$ 时，$[i,r]$ 为合法方案。

用线段树维护 $f$ 的区间最小值，最小值的个数，最小值$+1$ 的个数。

假设当前枚举到 $i$：

  • $[1,i-1]$ 中没有数在排列中与 $i$ 相邻，那么 $f_1\sim f_i$ 加一。
  • $[1,i-1]$ 中有一个数 $x$ 在排列中与 $i$ 相邻，那么 $f_{x+1}\sim f_i$ 加一。
  • $[1,i-1]$ 中有两个数 $x,y$ $(x<y)$ 在排列中与 $i$ 相邻，那么 $f_1\sim f_x$ 减一，$f_{y+1}\sim f_i$ 加一。

每次更新完询问 $f_1\sim f_{i-1}\le 2$ 的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=3e5+5;
int a[N],pos[N];
int ls[N<<2],rs[N<<2],add[N<<2],mn[N<<2],cnt1[N<<2],cnt2[N<<2];
void build(int p,int l,int r) {
    ls[p]=l,rs[p]=r;
    cnt1[p]=r-l+1;
    if(l==r) return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void push_down(int p) {
    if(add[p]) {
        mn[p<<1]+=add[p],mn[p<<1|1]+=add[p];
        add[p<<1]+=add[p],add[p<<1|1]+=add[p];
        add[p]=0;
    }
}
void update(int p,int l,int r,int v) {
    if(ls[p]>=l&&rs[p]<=r) {
        mn[p]+=v;
        add[p]+=v;
        return;
    }
    push_down(p);
    int mid=ls[p]+rs[p]>>1;
    if(l<=mid) update(p<<1,l,r,v);
    if(r>mid) update(p<<1|1,l,r,v);
    mn[p]=min(mn[p<<1],mn[p<<1|1]);
    cnt1[p]=cnt1[p<<1]*(mn[p<<1]==mn[p])+cnt1[p<<1|1]*(mn[p<<1|1]==mn[p]);
    cnt2[p]=cnt1[p<<1]*(mn[p<<1]==mn[p]+1)+cnt1[p<<1|1]*(mn[p<<1|1]==mn[p]+1);
    cnt2[p]+=cnt2[p<<1]*(mn[p<<1]==mn[p])+cnt2[p<<1|1]*(mn[p<<1|1]==mn[p]);
}
int query(int p,int l,int r) {
    if(ls[p]>=l&&rs[p]<=r) return cnt1[p]*(mn[p]<=2)+cnt2[p]*(mn[p]==1);
    push_down(p);
    int mid=ls[p]+rs[p]>>1;
    if(r<=mid) return query(p<<1,l,r);
    if(l>mid) return query(p<<1|1,l,r);
    return query(p<<1,l,r)+query(p<<1|1,l,r);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        int x;cin>>x;
        pos[x]=i;
    }
    build(1,1,n);
    LL res=0;
    for(int i=1;i<=n;i++) {
        a[pos[i]]=i;
        int x=a[pos[i]-1],y=a[pos[i]+1];
        if(x>y) swap(x,y);
        if(x&&y) update(1,1,x,-1),update(1,y+1,i,1);
        else update(1,y+1,i,1);
        if(i>1) res+=query(1,1,i-1);
    }
    cout<<res<<'\n';
    return 0;
}