noone___'s blog
0%

笛卡尔树笔记

发表于 更新于 分类于
笛卡尔树

构造

对于相匹配的两种键值作为点对 $(x_i,y_i)$ 放到二叉树上，满足：

  • 对于 $x_i$ ：满足 $\text{BST}$ 性质，即中序遍历有序
  • 对于 $y_i$ ：满足大根/小根二叉堆性质，即父节点的 $y$ 值 $\geq /\leq$ 所有子节点的 $y$ 值

保证 $x$ 有序的条件下，单调栈能做到 $O(n)$ 建树：

1
2
3
4
5
for(rei i=1;i<=n;++i){
    while(top && a[ stk[top] ]>a[i]) son[i][0]=stk[top--];
    if(stk[top]) son[ stk[top] ][1]=i;
    stk[++top]=i;
}

板子

性质(以小根笛卡尔树为例)

  • 以点 $u$ 为根的子树是一段连续极长区间，$y_u$ 是区间的最小值，区间在保证最小值不变的情况下不能再向两边延伸
  • 区间 $[a,b]$ 的最小值为 $y_{\text{lca}_{a,b}}$
  • 对于互不相同的 $x,y$ ，所得到的笛卡尔树结构唯一
  • 对于有序数列 $x$ 及随机排列 $y$ ，笛卡尔树的期望高度为 $E(depth_i)=H(i)+H(n-i+1)-1$ ，其中调和级数 $H(n)$ 与 $\log n$ 同阶，故期望高度 $\log n$
  • $\text{treap}$ 是满足性质 $4$ 的特殊笛卡尔树，那么可以通过 $\text{treap}$ 的操作动态维护笛卡尔树

笛卡尔树主要解决最大/最小值问题，以及(通过记录时间)关于插入删除的问题

例题

HDU 柱状图最大子矩阵

$n$ 个宽度为 $1$ ，高度不同的矩阵，求其最大子矩阵

不难发现，下标限制区间， $h$ 限制最大值，那么以 $(下标，h)$ 构建笛卡尔树

根据大根笛卡尔树的性质，最长区间就是子树大小，故节点 $u$ 的最大子矩阵就是 $Size_u\times h_u$

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
const int N=1e5+100;
int ans,a[N],son[N][2],Size[N];
int n,stk[N];

void dfs(int x){
    Size[x]=1;
    if(son[x][0]) dfs(son[x][0]),Size[x]+=Size[ son[x][0] ];
    if(son[x][1]) dfs(son[x][1]),Size[x]+=Size[ son[x][1] ];
    ans=ans>a[x]*Size[x] ? ans : a[x]*Size[x];
}

signed main(){
    while(~scanf("%lld",&n)){
        if(!n) return 0;
        for(rei i=1;i<=n;++i) scanf("%lld",&a[i]),son[i][0]=son[i][1]=0;
        rei top=0;
        for(rei i=1;i<=n;++i){
            while(top && a[ stk[top] ]>a[i]) son[i][0]=stk[top--];
            if(top) son[ stk[top] ][1]=i;
            stk[++top]=i;
        }
        ans=0; dfs(stk[1]);
        printf("%lld\n",ans);
    }
    getchar(),getchar();
    return 0;
}

AGC028 B

戳我

P1377 [TJOI2011]树的序

另一个板板题

显然满足题干条件的就是笛卡尔树，构建后先序遍历出 $x$ 值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N=1e5+100;
int n,a[N],son[N][2],stk[N],top;

void print(int u){
    if(!u) return;
    printf("%d ",u);
    print(son[u][0]),print(son[u][1]);
}

int main(){
    scanf("%d",&n);
    for(rei i=1,x;i<=n;++i) scanf("%d",&x),a[x]=i;
    for(rei i=1;i<=n;++i){
        while(top && a[ stk[top] ]>a[i]) son[i][0]=stk[top--];
        if(top) son[ stk[top] ][1]=i;
        stk[++top]=i;
    }
    rei x; while(top) x=stk[top--];
    print(x);
    getchar(),getchar();
    return 0;
}

SP3734 PERIODNI - Periodni

给出 $N$ 列表格，表格高度不同，向其中填入 $k$ 个数，要求不能有两个数相邻，其中相邻指能通过一条直线到达且中间路程均有格子，求填法方案数

由题，两个不同列的数是否相互影响取决于中间有没有一个高度小于两者的矩形将它们隔开，也就是说，关键值受矩形高度最小值影响，那么以 $(数列编号i,h)$ 构建小根笛卡尔树，将不规则图形拆成若干矩形

考虑每个矩形内的答案：树形 $\text{dp}$

对于点 $u$ ，将左右两颗子树对应区间里的棋盘分成两块，$\min \{h\}$ 下面的共有块$B$ ， $\min\{h\}$ 上面的高低不一的块 $A$

对于块 $A$ ，设 $f_{u,x}$ 表示 $u$ 的子树中，切掉 $fa_u$ 的长度后，放 $x$ 个物品的方案数

那么对于当前 $u$ ，对 $son_{u,0} , son_{u,1}$ 的 $f$ 做卷积即可得 $f_u$

对于块 $B$ ，要考虑底层的 $A$ 对其影响，对于点 $u$ ,当前有 $a_u-a_{fa_u}$ 行，$Size_u$ 列

对于 $f_{u,i}$ ，设在块 $B$ 中选择了 $j$ 个，此时 $A$ 中的 $i-j$ 个占据了 $B$ 的列，故 $B$ 的方案数为：$\binom{a_u-a_{fa_u}}{j}\times \binom{Size_u-(i-j)}{j}\times j!$ ，即选 $j$ 行和 $j$ 列并两两配对的方案数

最后把 $AB$ 的结果做卷积即可

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
#define int long long
const int N=510,M=1e6+100;
const int mod=1e9+7;
int n,k,a[N],Size[N],dp[N][N],tmp[N];
int fac[M],inv[M],fac_inv[M];
int son[N][2],stk[N],top,rt;

inline void init(){
    fac[0]=fac[1]=fac_inv[0]=fac_inv[1]=inv[1]=1;
    for(rei i=2;i<M;++i){
        fac[i]=(ll) fac[i-1]*i%mod;
        inv[i]=(ll) inv[mod%i]*(mod-mod/i)%mod;
        fac_inv[i]=(ll) fac_inv[i-1]*inv[i]%mod;
    }
}

inline int get_C(int n,int m){
    if(m>n || m<0) return 0;
    return (ll) fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;
}

inline void build(){
    stk[++top]=1; rt=1;
    for(rei i=2;i<=n;++i){
        if(a[i]<a[ stk[1] ]){
            son[i][0]=stk[1]; rt=i;
            while(top) stk[top--]=0; stk[++top]=i;
        }
        else{
            while(top && a[ stk[top] ]>a[i]) son[i][0]=stk[top--];
            if(stk[top]) son[ stk[top] ][1]=i;
            stk[++top]=i;
        }
    }
}

void dfs(int u,int fa_u){
    Size[u]=1;
    if(son[u][0]) dfs(son[u][0],a[u]),Size[u]+=Size[ son[u][0] ];
    if(son[u][1]) dfs(son[u][1],a[u]),Size[u]+=Size[ son[u][1] ];
    memset(tmp,0,sizeof tmp);
    for(rei i=0;i<=Size[u];++i) for(rei j=0;j<=i;++j) tmp[i]=((ll) tmp[i]+dp[ son[u][0] ][j]*dp[ son[u][1] ][i-j]%mod)%mod;//左右儿子的卷积
    for(rei i=0;i<=Size[u];++i) for(rei j=0;j<=i;++j) dp[u][i]=((ll) dp[u][i]+tmp[i-j]*get_C(a[u]-fa_u,j)%mod *get_C(Size[u]-i+j,j)%mod *fac[j]%mod)%mod;//AB卷积
}

signed main(){
    scanf("%d%d",&n,&k);
    for(rei i=1;i<=n;++i) scanf("%lld",&a[i]);
    init(); build();
    dp[0][0]=1; dfs(rt,0);
    // printf("%d\n",rt);
    printf("%lld\n",dp[rt][k]);
    getchar(),getchar();
    return 0;
}

P4755 Beautiful Pair

给定数列 $A$ ，当一个数对 $(i,j) \ , \ (i\leq j)$ 满足 $a_i,a_j$ 的积不大于 $\max\{a_i,…a_j\}$ ，认为这个数对是美丽的，求出美丽的数对的数量

笛卡尔树上做启发式合并就好了qwq

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
const int N=1e5+100;
int n,a[N],dd[N],ra[N];
ll ans;
int son[N][2],rt,stk[N],top;

inline int get_rk(int x){ return upper_bound(dd+1,dd+1+n,x)-dd-1;}
inline void discrease(){
    for(rei i=1;i<=n;++i) dd[i]=a[i]; sort(dd+1,dd+1+n);
    for(rei i=1;i<=n;++i) ra[i]=get_rk(a[i]);
}

inline void build(){
    for(rei i=1;i<=n;++i) a[i]=-a[i];
    stk[++top]=1,rt=1;
    for(rei i=2;i<=n;++i){
        if(a[i]<a[ stk[1] ]){
            rt=i; son[i][0]=stk[1];
            while(top) stk[top--]=0;
            stk[++top]=i;
        }
        else{
            while(top && a[ stk[top] ]>a[i]) son[i][0]=stk[top--];
            if(stk[top]) son[ stk[top] ][1]=i;
            stk[++top]=i;
        }
    }
    for(rei i=1;i<=n;++i) a[i]=-a[i];
}

namespace BIT{
    int t[::N];
    inline int lowbit(int x){ return x&(-x);}
    inline void add(int pos){ for(;pos<=n;pos+=lowbit(pos)) ++t[pos];}
    inline int query(int pos,int ans=0){ for(;pos;pos^=lowbit(pos)) ans+=t[pos]; return ans;}
}

void dfs(int now,int l,int r){
    if(!now) return ;
    rei cur=0;//跨点now的答案
    if(now-l>r-now){//右边小
        for(rei i=now;i<=r;++i){
            rei lim=get_rk(a[now]/a[i]);
            cur-=BIT::query(lim);//去重
        }
        dfs(son[now][0],l,now-1);
        BIT::add(ra[now]);
        for(rei i=now;i<=r;++i){
            rei lim=get_rk(a[now]/a[i]);
            cur+=BIT::query(lim);
        }
        dfs(son[now][1],now+1,r);
    }
    else{
        for(rei i=l;i<=now;++i){
            rei lim=get_rk(a[now]/a[i]);
            cur-=BIT::query(lim);
        }
        dfs(son[now][1],now+1,r);
        BIT::add(ra[now]);
        for(rei i=l;i<=now;++i){
            rei lim=get_rk(a[now]/a[i]);
            cur+=BIT::query(lim);
        }
        dfs(son[now][0],l,now-1);
    }
    ans+=cur;
}

int main(){
    scanf("%d",&n); for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
    discrease();
    build();
    dfs(rt,1,n);
    printf("%lld\n",ans);
    getchar(),getchar();
    return 0;
}

P2611 [ZJOI2012]小蓝的好友

一块 $R\times C$ 的地上会生成 $n$ 个资源点，第 $i$ 个位于 $x_i,y_i$ ，计算至少包含一个资源点区域的数量

$\text{FHQtreap}$ 动态维护笛卡尔树

显然容斥为：总子矩形个数-内部没有资源点的子矩形个数

这类问题的 $\text{trick}$ 是扫描线：枚举子矩形的下边界，从上到下扫描，并考虑维护一些东西

维护序列 $S_{p,i}$ 表示每一列的比 $i$ 小且最靠近 $i$ 的资源点的纵坐标

设 $M_p(a,b)$ 表示 $S_p$ 的区间 $[a,b]$ 中的最大值，每条扫描线的贡献为 $\displaystyle{\sum_{i,j\in[1,c],i\leq j} p-M_p(i,j)=\frac{c(c+1)}{2}p-\sum M[i,j]}$

对 $S_{p,i}$ 计算其贡献，即，对每个横坐标计算其作为最大值的最大区间长度，笛卡尔树即可

以 $(下标v，该列上点行数的最大值w)$ 构建关于 $S_p$ 的大根笛卡尔树，在每个节点统计贡献，即，对于每个 $S_p$ ，其贡献为 $\displaystyle{\frac{c(c+1)}{2}p-\sum_u w_u\times (son_{u,0}+1)\times (son_{u,1}+1)}$ ，其中考虑到自身贡献，故加 $1$

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
const int N=2e5+100;
int n,m,k,tot,root;
int son[N][2],val[N],Size[N];
ll ans,key[N],sum[N];
vector<int> v[N];

namespace FHQ{
    inline void pushup(int x){
        Size[x]=Size[ son[x][0] ]+Size[ son[x][1] ]+1;
        sum[x]=sum[ son[x][0] ]+sum[ son[x][1] ]+key[x]*(Size[ son[x][0] ]+1)*(Size[ son[x][1] ]+1);
    }
    void build(int l,int r,int &x){
        rei mid=l+r>>1;
        x=++tot; Size[x]=1,val[x]=mid;
        if(l<mid) build(l,mid-1,son[x][0]);
        if(r>mid) build(mid+1,r,son[x][1]);
        pushup(x);
    }
    void merge(int &p,int x,int y){
        if(!x || !y) return p=x+y,void();
        key[x]>key[y] ? (p=x,merge(son[p][1],son[p][1],y)) : (p=y,merge(son[p][0],x,son[p][0]));
        pushup(p);
    }
    void split(int p,int k,int &x,int &y){
        if(!p) return x=y=0,void();
        val[p]<=k ? (x=p,split(son[p][1],k,son[p][1],y)) : (y=p,split(son[p][0],k,x,son[p][0]));
        pushup(p);
    }
    inline void modify(int k,int v){
        rei x,y,z; split(root,k,x,y),split(x,k-1,x,z);
        key[z]=v; pushup(z);
        merge(x,x,z),merge(root,x,y);
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    FHQ::build(1,m,root);
    for(rei i=1,x,y;i<=k;++i) scanf("%d%d",&x,&y),v[x].push_back(y);
    for(rei i=1;i<=n;++i){
        for(rei j=0,sz=v[i].size();j<sz;++j) FHQ::modify(v[i][j],i);
        ans+=(ll) i*m*(m+1)/2-sum[root];
    }
    printf("%lld\n",(ll) n*(n+1)/2*m*(m+1)/2-ans);
    getchar(),getchar();
    return 0;
}