THUPC2023 D 种苹果

题意

给一颗树，支持加点、边中加点、树链加、树链查询 的排名。

。

思路

首先做教主的魔法，然后做无处储存。

然后把两道题融合即可通过本题，随机撒点树链分块然后块内排序，查询时对整块块内二分，时间复杂度 。

可见本题只有蓝题难度。

对于加点，分成若干情况讨论然后把链重新连一下即可。

实现

但是第一次写树链分块，所以写挂了。

细节包括但不限于：

  • 深度是比较难维护的，所以求 LCA 直接令一个点跳到根并标记路径，然后令另一个点去找标记，注意同在一条链上时要暴力判一下哪个比较浅（记得清空标记）。
  • 连链的时候按照 为一节拆开，最后保留一节小于 的（令重链长度不小于 ），自动保证复杂度正确，然后记得下放中间的链的信息。
  • 为了保证复杂度，对于散点需要维护一个下方最长链的长度，在向上找链的时候维护即可。
  • 对于边中间加点有四种情况：
    1. 在链中间，这种情况先把链的信息下放下去，然后重连。
    2. 在两条链的中间，因为链是下闭上开的，所以下放下方链的信息，然后重连下方链到上方链的顶部。
    3. 在上方链的底部，直接连到上方链（这种情况当散点也行）。
    4. 在散点，这个时候要判断下方最长链的长度加上方到链上的距离，够大就从底部连上来。
  • 注意边中间加点的时候，对于链信息需要提前手动下放，不然新点连好之后再下放信息会有问题。
  • 在点下加点要判断上方到链上的距离，维护一下结构。
  • 结点 是不在任何链中的，这个一定要注意。
  • 根据实现复杂度还会有若干细节（以上是我精简代码之后仅剩的）。

关于常数

我去除了大部分的运行用时，但保留了一小部分，好让评测机知道它评测的是 N 根号 Log。

这个做法应该不卡常，我第一遍调出来就 3.7s，个人感觉询问分块然后重构的方法是比较卡常的，因为我赛后写了一份现在没过。

写挂的时候发现一个卡常小寄巧，对于所有非根的点总是保留第一条链不连成链（无论任何情况都不连接），让上面的点连。

然后就是对于暴力修改小于一定阈值使用插入排序。

块长调小，跑的很快，2.5s 左右。

CODE

含少量注释。

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<cstdio>
#include<vector>
#include<random>
#include<chrono>
#include<algorithm>
using namespace std;
const int N=400010,FSIZE=1<<24,B=280;
int n,m,p[N],fa[N],up[N],in[N],dp[N],hs[N],path[N],tag[N],tmp[N];
bool v[N];
vector<int> t[N];
vector<pair<int,int>> c[N];
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF;
template<typename T>void read(T &x){
    bool f=0;
    for(x=0;48>*InF||*InF>57;*InF++=='-'&&(f=1));
    for(;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    f&&(x=-x);
}
void write(int x){
    char st[12]={},*c=st;
    for(!x&&(*OnF++=48);x;x/=10) *++c=x%10^48;
    for(;c!=st;*OnF++=*c--);
    *OnF++='\n';
}
void reset(int u){    // 下放链的信息，并删除这条链
    c[u].clear();
    if(int &i=tag[u]){
        for(int x=up[u];u!=x;u=fa[u]) p[u]+=i;
        i=0;
    }
}
void set(int x,int y){    // 将 x->y 连接成若干条链
    for(tmp[tmp[0]=1]=x;x!=y;tmp[++tmp[0]]=x=fa[x])
        if(x==in[x]) reset(x);
    for(int *i=tmp+1,*j=i,*r=tmp+tmp[0];i<r;i=j){
        int *nxt=i+B;
        if(nxt+B>r) nxt=r;
        for(;j<nxt;++j){
            up[*j]=*nxt;
            c[in[*j]=*i].emplace_back(p[*j],*j);
        }
        sort(c[*i].begin(),c[*i].end());
    }
}
int dfs(int x){    // 预处理初始撒点情况
    int re=0;
    for(int i:t[x]) if(i!=fa[x]){
        fa[i]=x;
        if(int tmp=dfs(i)){
            if(re){
                set(tmp,x);
                v[x]=1;
            }else re=tmp;
        }
        if(dp[i]>dp[hs[x]]) hs[x]=i;
    }
    dp[x]=dp[hs[x]]+1;
    return(!re&&v[x]?x:re);
}
pair<int,int> getup(int i){    // 获取到上方链的距离及编号，并维护向下最长链的长度
    for(int x,dis=0;;++dis,i=x){
        if(dp[i]>dp[hs[x=fa[i]]]) dp[x]=dp[hs[x]=i]+1;
        if(in[x]||x==1) return(make_pair(x,dis));
    }
}
void add(int u,int w){    // 点下加点
    fa[++n]=u;
    p[n]=w;
    auto m=getup(n);
    if(m.second>=B) set(n,m.first);
}
void add(int u,int v,int w){    // 边中加点
    if(fa[u]==v) swap(u,v);
    if(in[v]) reset(in[v]);    // 提前手动下放
    fa[fa[v]=++n]=u;
    p[n]=w;
    if(in[v]&&in[v]!=in[u]) return(set(in[v],u));    // 在两条链中间
    if(in[u]) return(set(u==in[u]?n:in[u],up[u]));    // 在链中间或底部
    dp[n]=dp[hs[n]=v]+1;
    auto m=getup(n);
    if(m.second+dp[n]>=B+B){
        int x=n;
        for(;hs[x];x=hs[x]);
        set(x,m.first);
    }
}
int check(int u,int v){    // 返回两结点中较浅的一个
    int x=in[u];
    for(;x!=v&&x!=u;x=fa[x]);
    return(x==v?u:v);
}
int lca(int u,int v){    // 如名
    int x=u,re=0;
    for(;!up[x]&&x>1;x=fa[x]) path[x]=1;
    for(;!up[v]&&v;v=fa[v])
        if(path[v]){
            re=v;
            break;
        }
    for(;!up[u]&&u>1;u=fa[u]) path[u]=0;
    if(re) return(re);
    for(;x>1;x=up[x]) path[in[x]]=x;
    for(;v>1;v=up[v])
        if(path[in[v]]){
            re=check(path[in[v]],v);
            break;
        }
    for(;u>1;u=up[u]) path[in[u]]=0;
    return(re?re:1);
}
void modify2(int u,int v,int w){    // 对链内（或散点）暴力修改
    int b=in[u],sz=0;
    for(;u!=v;u=fa[u],++sz) p[u]+=w;
    if(b){
        for(auto &x:c[b]) x.first=p[x.second];
        if(sz<8)
            for(auto i=c[b].begin()+1;i<c[b].end();++i)
                for(auto j=i;j>c[b].begin()&&j[-1]>*j;--j) swap(j[-1],*j);
        else sort(c[b].begin(),c[b].end());
    }
}
void modify1(int u,int x,int w){    // 修改祖先后代链
    for(;!up[u]&&u!=x;u=fa[u]) modify2(u,fa[u],w);
    for(;in[u]!=in[x];u=up[u])
        if(in[u]==u) tag[u]+=w;
        else modify2(u,up[u],w);
    modify2(u,x,w);
}
void modify(int u,int v,int w){    // 如名
    int l=lca(u,v);
    modify1(u,l,w);
    modify1(v,l,w);
    modify2(l,fa[l],w);
}
int query2(int u,int x,int w){    // 对链内（或散点）暴力询问
    int re=0;
    for(w-=tag[in[u]];u!=x;u=fa[u]) re+=p[u]>=w;
    return(re);
}
int query1(int u,int x,int w){    // 询问祖先后代链
    int re=0;
    for(;!up[u]&&u!=x;u=fa[u]) re+=p[u]>=w;
    for(;in[u]!=in[x];u=up[u])
        if(u==in[u])
            re+=c[u].end()-lower_bound(c[u].begin(),c[u].end(),make_pair(w-tag[u],0));
        else re+=query2(u,up[u],w);
    return(query2(u,x,w)+re);
}
int query(int u,int v,int w){    // 如名
    int l=lca(u,v),re=p[l]>=w-tag[in[l]];
    re+=query1(u,l,w);
    re+=query1(v,l,w);
    return(re);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);read(m);
    for(int i=1;i<=n;++i) read(p[i]);
    for(int i=1,x,y;i<n;++i){
        read(x);read(y);
        t[x].push_back(y);
        t[y].push_back(x);
    }
    mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());
    for(int i=v[1]=1;i<=n;i+=B) v[rnd()%n+1]=1;
    set(dfs(1),1);    // 注意手动连接最后一条传上来的链
    for(int i=0,o,x,y,w,lastans=0;i<m;++i){
        read(o);read(x);read(y);
        x^=lastans;
        y^=lastans;
        if(o!=2){
            read(w);
            w^=lastans;
            switch(o){
            case 1:add(x,y,w);break;
            case 3:modify(x,y,w);break;
            case 4:write(lastans=query(x,y,w));
            }
        }else add(x,y);
    }
    fwrite(WuF,1,OnF-WuF,stdout);
    return(0);
}
≡