Code+2020 F 六元环 与二叉树旋转

First Post:

Last Update:

Word Count:
2.2k

Read Time:
9 min

Page View: loading...

upd 2023/5/31：对本文所述结构有了更为本质的认识，故重构。

upd 2023/6/1：换上了新的代码，勘误。

本题解旨在提供一种维护二叉树旋转信息的非 LCT 做法。对于本人而言，做法来源是退役学长 yyt 的出题莱斯特城，祝其人生之路璀璨。

题意

给定序列 其中 。

定义图 中结点 满足 间有双向边当且仅当 是 前第一个大于等于 的数，或 是 后第一个大于 的数。

每次修改将某个 中的某个数 ，修改后询问 中的六元环数量。

题意转化

首先，容易想到使用笛卡尔树维护序列 ，显然笛卡尔树上的边全部在 中，然后存在额外连边，它们满足在笛卡尔树上是一个转折的关系（左儿子的右链连向自己，与右儿子的左链连向自己），容易发现 为一个平面图。

对于六元环，其在 上由四个三角形组成，通过对这四个三角形的联通情况进行分类讨论可以发现，一组联通的四个三角形与六元环间恰好存在对应关系。

我们用一个三角形在笛卡尔树中最深的结点表示这个三角形，即可将一组联通的四个三角形进一步转化为在笛卡尔树上的联通的四个点。

注意不存在边 ，需要将根节点删除。

如果不存在修改，该计数可以在每个点向下记录下一层结点数与下下层结点数解决，我们接下来考虑如何修改。

由于修改只会变大，且中序遍历不变，于是这可以描述为修改点在笛卡尔树上进行上旋。

现在有一个结点 父亲为 旋转到原先 的位置， 满足过程中旋转方向不变，对于笛卡尔树上的边仅有 ， 的一个儿子、、 与其的父亲它们的 的父子关系被改变，同样的贡献的改变量也是 的。

我们假设这之后 的旋转方向改变，那么称 是一个转折点。

对于转折点的数量，lxl 通过势能分析证明了其复杂度为 ，不过笔者并未看到具体的证明过程，加上太菜了以及不是本文重点 故先咕这，不补了好像直接套 LCT 的分析就行，但是我不会分析 LCT 而且找不到资料。

数据结构

这显然是可以使用 LCT 维护的，但是毕竟本题的结构较为静态（中序遍历不变），考虑是否存在更为简单的方式。

现在考虑一个大根笛卡尔树，其结点上有权值，为了避免文字太多导致疲劳记为 吧。

对于结点 ，不妨设是父亲的左儿子，那么它向上第一个转折点的父亲在它的左边，且一定是左边第一个 大于它的 的点，这中间的其他结点均为 的后代。

对于旋转不到转折点的情况，由于旋转方向上那一条链所有大于 的结点的 按顺次为一个递减序列（因为它们按顺序是 的祖先），而其他点的 均小于其临近的两个链上的结点的 。

这是什么？单调性，二分一下。不单调的都不是我们要找的，并且会被我们要找的给挡住，所以可以直接查找最终要旋转到的值。

所有的找某个结点的操作均可在数据结构上二分解决，由于本题没有其它操作了，使用线段树维护即可。

拓展

对于一般的二叉树，我们仍然可以使用该方法。

对于一棵二叉树，其满足是自己深度的中序遍历构建的笛卡尔树，对于连续的不变向旋转，可以等价于两个区间操作（以左旋为例）：

  1. 从链顶的子树最左到这个点父亲的所有点深度加一。
  2. 这个点的子树中不包括左子树的所有点的深度减去旋转次数。

实际上可以随便构造序列，只要满足笛卡尔树的性质即可，使用深度便于处理向上旋转某个特定次数的情况。

一般而言这类维护转折的题目不太可能出现区间修改一类的操作，所以区间加是不太可能跟什么别的标记冲突的。

后记

可以看到通过这种方式，我们将旋转操作的维护静态化了。虽然并不能够得到一个更加强大的做法，因为该做法仍然依赖于操作中信息的改变量是有限的这一事实，而对于树本身形态的维护是不能超过动态树的能力范畴的。

虽然只使用了线段树，但由于 LCT 本身结构的特点适于维护树链，相比之下这种做法细节相当多，并不容易调试。

速度由于线段树二分的递归结构在本题上没有太多优势，可以写 zkw 线段树，实际总用时跑到 LCT 的一半（于是完全看不懂洛谷怎么算的总用时了）。

本文撰文仓促，难免有错误，若发现请务必吊打笔者。

由于笔者没有进行进一步的研究，如果有其它有趣的想法欢迎讨论。

CODE

就这道题的话，代码或许以后补一份

代码有啦。

换成 zkw 线段树了。

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
113
114
115
116
117
118
119
120
121
122
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=(1<<19)+10,FSIZE=1<<24;
int n,m,ans,rt,sl[N],sr[N],fa[N],down[N][2],now[N];
vector<int> s;
ll p[N];
struct ST{
    ll a[N+N];
    int len;
    void build(){
        len=(2<<__lg(n-1))-1;
        for(int i=1;i<=n;++i) a[i+len]=p[i];
        for(int p=len;--p;a[p]=max(a[p<<1],a[p<<1|1]));
    }
    int pre(int x,ll y){
        for(x+=len;x>1;x>>=1)
            if(a[(x>>=__builtin_ctz(x))^1]>=y) break;
        if(x<2) return(0);
        for(x^=1;x<=len;)
            if(a[x=x<<1|1]<y) x^=1;
        return(x-len);
    }
    int nxt(int x,ll y){
        for(x+=len;x>1;x>>=1)
            if(a[(x>>=__builtin_ctz(~x))^1]>y) break;
        if(x<2) return(0);
        for(x^=1;x<=len;)
            if(a[x<<=1]<=y) x|=1;
        return(x-len);
    }
    void add(int x,int y){for(a[x+=len]+=y;x>>=1;a[x]=max(a[x<<1],a[x<<1|1]));}
}t;
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF,ST[10],*STC=ST;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;32<*InF;x=x*10+(*InF++^48));
}
void write(int x){
    for(!x&&(*OnF++=48);x;x/=10) *++STC=x%10^48;
    for(;STC!=ST;*OnF++=*STC--);
    *OnF++='\n';
}
int calc(int x){
    int *w=down[x],*ls=down[sl[x]],*rs=down[sr[x]],&re=now[x]=ls[1]+rs[1];
    w[1]=ls[0]+rs[0];
    if((w[0]=!!sl[x]+!!sr[x])>1) re+=w[1];
    return(re+=(ls[0]>1)+(rs[0]>1));
}
void bfs(){
    s={rt};
    for(int i=0;i<(int)s.size();++i){
        int x=s[i];
        fa[sl[x]]=fa[sr[x]]=x;
        if(sl[x]) s.push_back(sl[x]);
        if(sr[x]) s.push_back(sr[x]);
    }
    for(int i=s.size();i;--i) ans+=calc(s[i-1]);
}
#define zg(l,r){\
    fa[s##l[f]=s##r[x]]=f;\
    fa[fa[s##r[x]=y]=x]=fy;}
void change(int x,int y,bool is){
    int f=fa[x],fy=fa[y];
    if(is) zg(l,r)
    else zg(r,l)
    (sr[fy]==y?sr[fy]:sl[fy])=x;
    for(int i=f,p=4;i!=y&&i&&--p;i=fa[i]){
        ans-=now[i];
        ans+=calc(i);
    }
    ans-=now[y]+now[x];
    ans+=calc(y);ans+=calc(x);
    for(int i=fy,p=3;i&&--p;i=fa[i]){
        ans-=now[i];
        ans+=calc(i);
    }
}
void rotate(int x,ll &now,int add){
    for(;x!=rt;){
        int is=sl[fa[x]]==x,e=is?t.pre(x,now):t.nxt(x,now),s=e?is?sr[e]:sl[e]:rt;
        ll sp=p[s]+(s<x);
        if(sp<=now+add){
            change(x,s,is);
            add-=sp-now;
            now=sp;
            if(s==rt) rt=x;
        }else{
            int to=is?sl[t.nxt(x,now+add)]:sr[t.pre(x,now+add)];
            if(x!=to&&to) change(x,to,is);
            break;
        }
    }
    now+=add;
}
void buildC(){
    for(int i=1;i<=n;s.push_back(i++)){
        for(;s.size()&&p[i]>p[s.back()];s.pop_back()) sl[i]=s.back();
        if(s.size()) sr[s.back()]=i;
    }
    rt=s[0];
    for(int i=1;i<(int)s.size();++i) sr[s[i-1]]=s[i];
    bfs();
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=1;i<=n;++i) read(p[i]);
    buildC();
    t.build();
    read(m);
    for(int x,y;m--;){
        read(x);read(y);
        rotate(x,p[x],y);
        t.add(x,y);
        write(ans-now[rt]);
    }
    fwrite(WuF,1,OnF-WuF,stdout);
    return(0);
}
≡