笛卡尔树&标准rmq算法

发表于 分类于

两个挺偏门（？）的算法。

笛卡尔树

定义

笛卡尔树是一个维护数列的数据结构，它满足两个性质：

  • 中序遍历等于原序列，并且是二叉树（这就是$\rm BST$的性质）。
  • 任意一个点的权值都要小于（或者大于）儿子的权值（这就是堆的性质）。

所以根据定义容易得到一个暴力的构造方法：每次暴力找到当前区间的最小值，然后左右两边递归处理作为左右子树。

这个做法复杂度是$O(n^2)$的。

线性构造

线性构造其实很简单，考虑增量法，用一个栈来维护从根节点一直走右儿子的这条链，每次在序列最后添加一个值：

  • 如果它是全局最小值（即小于根节点），就把根节点接在它左儿子，然后暴力更新栈（清空栈，把当前点加进去）。
  • 否则一路弹栈，直到栈顶比当前点小，把当前点接在栈顶右儿子下，弹掉的那条链接在当前点左儿子下。

每个点只会被弹栈入栈一次，复杂度$O(n)$。

正确性显然。

应用

我是真的没找到什么题。。就两三个的样子。

[POJ2201] Cartesian Tree

模板题，放下代码吧（头文件之类的东西太占地方就去掉了）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct info {int k,x,id;}a[maxn];
int n,ls[maxn],rs[maxn],val[maxn],rt,sta[maxn],top,cnt,s[maxn],fa[maxn],t[maxn];

void insert(int v,int id) {
    int x=++cnt;val[x]=v;s[id]=x,t[x]=id;
    int p=0;
    while(top&&val[sta[top]]>v) p=sta[top],top--;
    if(top) rs[sta[top]]=x,fa[x]=sta[top];
    else rt=x;
    ls[x]=p,sta[++top]=x;
    if(p) fa[p]=x;
}

int cmp(info x,info y) {return x.k<y.k;}

int main() {
    read(n);for(int i=1;i<=n;i++) read(a[i].k),read(a[i].x),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) insert(a[i].x,a[i].id);
    puts("YES");
    for(int x=1;x<=n;x++)
        printf("%d %d %d\n",t[fa[s[x]]],t[ls[s[x]]],t[rs[s[x]]]);
    return 0;
}

[BZOJ2616] SPOJ PERIODNI

考虑把小根笛卡尔树搞出来，每个点$x$看做是一个$(val_x-val_{fa})\times size_x$的矩形，那么所有点的总和就是题目给出的图形。

考虑$\rm dp$，设$f_{x,i}$表示$x$子树放了$i$个点的方案数，那么首先弄一个辅助数组$t_i=\sum_{j=0}^{i} f_{ls,j}\cdot f_{rs,i-j}$表示子树的方案。

那么转移考虑枚举$x$代表的矩形放了几个：

复杂度$O(nk^2)$。

代码没啥重要的东西就不放了

[uoj424]【集训队作业2018】count

多项式不想写，O(n)做法看不懂，所以咕咕咕咕咕

标准rmq

问题转化

标准$\rm rmq$是一种预处理$O(n)$，每次询问$O(1)$的$\rm rmq$做法。

我们先把序列建成笛卡尔树，比较容易的可以得知，两个点之间的最小值就是笛卡尔树上的$\rm LCA$的权值。

问题转化为如何$O(n)-O(1)$求$\rm LCA$。

这个做法非常巧妙，首先我们可以利用欧拉序把$\rm LCA$再转化成深度的$\rm rmq$问题，而这个序列有一个性质：$|a_i-a_{i-1}|=1$一定成立。

根据这个性质我们可以得到一个$O(n)-O(1)$的特殊序列的$\rm rmq$算法，这个算法好像也被叫做$\rm \pm 1 rmq$或者约束$\rm rmq$。

接下来将阐述约束$\rm rmq$的做法。

约束rmq

首先对序列分块，设块大小$B=\dfrac{\log_2 n}{2}$，为什么待会解释。

那么首先很容易解决整块之间的询问：直接上$O(n\log n)$的$\rm ST$表就好了，因为一共只有$\dfrac{n}{B}=\dfrac{2n}{\log_2 n}$个块，所以这部分复杂度为$O(n)$。

现在难点就在如何求不全的块的贡献，注意到现在我们还没用到$\rm \pm1​$的特殊性质。

我们考虑一共有多少个不等价的块，我们说两个块等价当且仅当他们的大小关系相同，或者也可以表述为他们的差分数组不同：因为每次只有可能$\rm \pm 1$，所以说这两句话是完全等价的。

考虑一共有多少个本质不同的差分序列，容易发现个数为$2^{B-1}=2^{(\log _2 n)/2-1}= O(\sqrt n)$。

这就是为什么设块大小的时候要除以$2$，这么一来我们可以暴力预处理出$f_{s,i,j}$表示第$s$种块$[i,j]$的最小值位置在哪里，那么只需要一开始给每个块标号就好了，标号的复杂度是$O(n)$，预处理$f$的复杂度是$O(\sqrt n \log ^2 n)$。

所以总预处理的复杂度是$O(n)$，而询问显然可以根据上面的东西做到$O(1)$。

放个代码吧，由于我太懒了，所以只实现了$O(n)-O(1)$的$\rm LCA$。

并且说实话这东西没啥大用，可能是我实现有点慢，反正就只比带log的算法快了一倍，但是凭空多了$100$行代码。。。

以下这份代码可以通过洛谷LCA模板。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1.5e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int head[maxn],tot,n,rt,q,cnt,dfn[maxn],dep[maxn];
struct edge{int to,nxt;}e[maxn<<1];
pii r[maxn];

void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}

void dfs(int x,int fa) {
    dep[x]=dep[fa]+1,r[dfn[x]=++cnt]=mp(dep[x],x);
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=fa) dfs(e[i].to,x),r[++cnt]=mp(dep[x],x);
}

int bel[maxn],B,m,id[maxn],t[20],st[maxn],lg[maxn];
pii w[17][maxn>>3],f[1500][12][12];

pii min(pii a,pii b) {return a.fr<b.fr?a:b;}

void search(int x,int s) {
    if(x==B+1) {
        for(int i=1;i<=B;i++) {
            f[s][i][i]=mp(t[i],i);
            for(int j=i+1;j<=B;j++)
                f[s][i][j]=min(f[s][i][j-1],mp(t[j],j));
        }return ;
    }
    t[x]=t[x-1]+1;
    search(x+1,s<<1|1);
    t[x]=t[x-1]-1;
    search(x+1,s<<1);
}

void rmq_init() {
    B=log2(cnt)/2.0;
    for(int i=1;i<=cnt;i++) bel[i]=(i-1)/B+1;m=bel[cnt];
    for(int i=1;i<=m;i++) w[0][i].fr=1e9;
    for(int i=1;i<=cnt;i++) w[0][bel[i]]=min(w[0][bel[i]],r[i]);
    for(int i=2;i<=m;i++) lg[i]=lg[i>>1]+1;
    for(int j=1;j<=lg[m];j++) 
        for(int i=1;i<=m;i++)
            w[j][i]=min(w[j-1][i],w[j-1][i+(1<<(j-1))]);
    search(2,0);
    for(int i=1;i<=cnt;i+=B) {
        int s=0;st[bel[i]]=i;
        for(int j=i+1;j<i+B;j++)
            if(r[j].fr>r[j-1].fr) s=s<<1|1;else s<<=1;
        id[bel[i]]=s;
    }
}

pii get(int x,int a,int b) {
    int p=f[id[x]][a-st[x]+1][b-st[x]+1].sc;
    return r[st[x]+p-1];
}

pii block_rmq(int a,int b) {
    int x=lg[b-a+1];
    return min(w[x][a],w[x][b-(1<<x)+1]);
}

pii rmq(int a,int b) {
    if(a>b) swap(a,b);
    if(bel[a]==bel[b]) return get(bel[a],a,b);
    pii res=mp(1e9,0);
    if(bel[a]!=bel[b]-1) res=block_rmq(bel[a]+1,bel[b]-1);
    res=min(res,min(get(bel[a],a,st[bel[a]]+B-1),get(bel[b],st[bel[b]],b)));
    return res;
}

int main() {
    read(n),read(q),read(rt);
    for(int i=1,x,y;i<n;i++) read(x),read(y),ins(x,y),ins(y,x);
    dfs(rt,0);
    rmq_init();
    for(int i=1;i<=q;i++) {
        int l,r;read(l),read(r);
        write(rmq(dfn[l],dfn[r]).sc);
    }
    return 0;
}