笛卡尔树

(Updated: )
(9 mins to read)

类似treap，权值满足二叉搜索树，键值满足堆一般用在序列上，以下标为权值，值为键值，利用单调栈可以$O(n)$建树因为下标是单调递增的，所以只需要在单调栈中维护出最右链，在插入一个新点的时候，不断排掉大于自己值的点，然后自己成为栈顶的右儿子，排掉的最后一个点作其左儿子有什么用呢笛卡尔树上两个点的LCA就代表这个区间的RMQ对一个点，它是其代表的区间的最值，左子树是左区间，右子树是右区间，这就形成了良好的递归性质，可以方便思考和解题

P4755

定义点对$(i,j)$是好的，当且仅当$a_i\times a_j \leq \max(a_i,…,a_j)$显然可以启发式分治做，利用st表找到最值的位置，然后启发式遍历左右区间中小的那一边然后求最值即可。其实这种思想放在笛卡尔树上也是一样的，dfs遍历，然后通过遍历小的那颗子树来统计答案。统计答案可以直接用动态开点线段树，然后线段树合并即可

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, inf = 1e9;
int n, a[N], sz[N];
int64_t ans;
struct seg
{
  int l, r, cnt;
}t[N<<5];
int rt[N<<5], tot;
void up(int p) { t[p].cnt = t[t[p].l].cnt + t[t[p].r].cnt; }
void upd(int &p, int l, int r, int x)
{
  if(!p) p = ++tot;
  t[p].cnt++;
  if(l==r) return;
  int mid = (l+r)>>1;
  if(x<=mid) upd(t[p].l, l, mid, x);
  else upd(t[p].r, mid+1, r, x);
}
int ask(int p, int l, int r, int v)
{
  if(!p) return 0;
  if(r<=v) return t[p].cnt;
  int mid = (l+r)>>1;
  int ans = ask(t[p].l, l, mid, v);
  if(v>mid) ans += ask(t[p].r, mid+1, r, v);
  return ans;
}
int merge(int x, int y, int l, int r)
{
  if(!x||!y) return x|y;
  if(l==r)
  {
    t[x].cnt += t[y].cnt;
    return x;
  }
  int mid = (l+r)>>1;
  t[x].l = merge(t[x].l, t[y].l, l, mid);
  t[x].r = merge(t[x].r, t[y].r, mid+1, r);
  up(x);
  return x;
}
int st[N], ch[N][2], top;
void build()
{
  top = 0;
  for(int i=1, j; i<=n; i++)
  {
    j = top;
    while(j&&a[st[j]]<a[i]) j--;
    if(j) ch[st[j]][1] = i;
    if(j<top) ch[i][0] = st[j+1];
    top = j;
    st[++top] = i;
  }
}
void dfs(int p, int l, int r)
{
  if(!p || l>r) return;
  dfs(ch[p][0], l, p-1);
  dfs(ch[p][1], p+1, r);
  sz[p] = sz[ch[p][0]] + sz[ch[p][1]] + 1;
  if(sz[ch[p][0]]<sz[ch[p][1]]) for(int i=l; i<=p-1; i++) ans += ask(rt[ch[p][1]], 1, inf, a[p]/a[i]);
  else for(int i=p+1; i<=r; i++) ans += ask(rt[ch[p][0]], 1, inf, a[p]/a[i]);
  rt[p] = merge(rt[ch[p][0]], rt[ch[p][1]], 1, inf);
  upd(rt[p], 1, inf, a[p]);
  ans += ask(rt[p], 1, inf, 1);
}
int main()
{
  scanf("%d", &n);
  for(int i=1; i<=n; i++) scanf("%d", a+i);
  build();
  dfs(st[1], 1, n);
  printf("%lld\n", ans);
  return 0;
}

牛客多校3 Sort the Strings Revision

有一个序列，第i个元素的值为$i % 10$，n次操作，每次将$p_i$​位置的值换成$d_i$​，其中$p_i$​为一个排列，问你操作前后共$n+1$个序列的字典序排名显然越小的$p_i$​越占据主导地位，根据序列p建出笛卡尔树，然后如果$p_i>d_i$​，说明修改后字典序更小，优先遍历右子树，反之优先遍历左子树。有一个问题是如果$p_i=d_i$​，此时就不知道左右子树哪个小了，可以人为的先让这样的$p_i$​取一个极大值，这样这些$p_i$​只可能在叶子节点了。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5, mod = 1e9 + 7, base = 10000019;
int n, p[N], d[N];
int st[N], ch[N][2], rk[N], top, rnk;
void build(int *a)
{
  top = 0;
  for(int i=0; i<n; i++) ch[i][0] = ch[i][1] = 0;
  for(int i=0, j; i<n; i++)
  {
    j = top;
    while(j && a[st[j]]>a[i]) j--;
    if(j) ch[st[j]][1] = i;
    if(j<top) ch[i][0] = st[j+1];
    top = j;
    st[++top] = i;
  }
}
void dfs(int rt, int l, int r)
{
  if(l>r) return;
  if(l==r || p[rt]==mod)
  {
    for(int i=l; i<=r; i++) rk[i] = rnk++;
    return;
  }
  if(p[rt]%10>d[rt]) dfs(ch[rt][1], rt+1, r), dfs(ch[rt][0], l, rt);
  else dfs(ch[rt][0], l, rt), dfs(ch[rt][1], rt+1, r);
}
void solve()
{
  int pseed, pa, pb, pmod;
  int dseed, da, db, dmod;
  rnk = 0;
  scanf("%d", &n);
  scanf("%d%d%d%d", &pseed, &pa, &pb, &pmod);
  scanf("%d%d%d%d", &dseed, &da, &db, &dmod);
  for(int i=0; i<n; i++) p[i] = i;
  for(int i=1; i<n; i++)
  {
    swap(p[pseed%(i+1)], p[i]);
    pseed = (1ll*pseed*pa + pb)%pmod;
  }
  for(int i=0; i<n; i++)
  {
    d[i] = dseed%10;
    dseed = (1ll*dseed*da + db)%dmod;
  }
  for(int i=0; i<n; i++) if(d[i]==p[i]%10) p[i] = mod;
  build(p);
  int rt = st[1];
  dfs(rt, 0, n);
  int ans = 0, pw = 1;
  for(int i=0; i<=n; i++)
  {
    ans = (ans + 1ll*rk[i]*pw%mod)%mod;
    pw = 1ll*pw*base%mod;
  }
  printf("%d\n", ans);
}
int main()
{
  int _; scanf("%d", &_);
  while(_--) solve();
  return 0;
}