$\text{前言}$ ：
本篇题解是我对其他题解的理解和梳理。$\text{题意}$ ：
给你一棵树，和一个 $n$ 的排列 $a$。定义一个满足要对的点对 $(L,R)$ 为：对于 $\forall x,y$ 如果满足 $a_x,a_y \in [L,R]$，则 $a_{Lca(x,y)} \in [L,R]$。
$q$ 次询问形如 $l,r$，求：$[l,r]$ 中满足要求的点对数量。
数据规模：$n ,q \le 2\times 10 ^5$
$\text{分析}$ ：
我们知道，$Lca$ 满足相关性质我们常用点分治或者 `dsu on tree`，与距离相关常用点分治，这题我们尝试使用 `dsu on tree` 做。
令 $Lca(x,y) = z$，我们考虑一个合法的区间满足 $a_x < a_z < a_y$。我们考虑什么样的区间不满足要求。
不妨设 $a_x < a_y$，有：
1. 如果 $a_z < a_x$，则 $l \in (a_z,a_x], \ r \ge a_y$ 的区间不满足要求。
2. 如果 $a_z > a_y$，则 $l \in [1,a_x], \ r \in [a_y,a_z)$ 的区间不满足要求。
但是枚举这样的点对是 $O(n^2)$ 的。观察发现，对于同一个 $z$，不合法点对 $(x,y)$，$(d,e)$ 如果都不满足限制 $1$，如果 $[x,y] \subset [d,e]$，显然 $[x,y]$ 可以约束到更多的点，那么另一个点对就可以删去。$2$ 同理。
这样我们就可以在 `dsu on tree` 中对于每个点 $x$ 找 $a_x$ 的前驱后继，这样我们可以找出大概 $2 \times n \log n$ 个点对。
发现我们大概要求一个矩形内符合要求的点，
我们把询问离线下来，用扫描线做。枚举每个右端点，累计左端点可能的个数。大概来说就是求历史最小值 $0$ 的个数和，这是满足区间可减性的，即可以差分。如果不满足的话，我们通常可以分治求解，不过要多带一只 $\log$。复杂度 $O (n \log^2 n) $。
------------
$\text{Add} \ \ 1.20.2024$
我当时写这篇题解的时候还没有敲代码，后来我自己写的时候发现维护历史 $0$ 的个数之和并不是很好做，就顺便提一嘴。
首先我们要求历史 $0$ 的个数和，也就是各个版本 $0$ 的个数之和。因此我们考虑维护**当前最小值**，**当前最小值个数**，**历史 $0$ 个数之和**。
首先有一个想法是在 $\operatorname{push\ up}$ 的时候记录时间差来维护一段时间的贡献，但是这样不好处理 $\operatorname{push\ down}$。
之后我 $\text{Search Online}$，但是没找到。然后参考其他了题解，发现了一个很聪明（可能是套路）的做法：记一个 $\operatorname{tag_2}$ 把时间差累积起来算贡献。即在扫描线每次移动 $r$ 的时候都在整棵树为 $0$ 的区间打上一个 $\operatorname{tag_2}$。但是我不太会分析这个的复杂度，等我再研究一下。
还有个小细节，我们打 $\operatorname{tag_2}$ 的时候可以只在从 $1$ 到当前枚举的右端点 $r$ 的区间打标记，这样我们不用查询两次做差分，少一半的查询。
因为我写完了，给出参考代码。
1 #include<bits/stdc++.h>
2
3 #define pb emplace_back
4 #define pi pair<int,int>
5 #define mp make_pair
6 #define fi first
7 #define se second
8 const int N=2e5+50;
9 typedef long long ll;
10 using namespace std;
11
12 int n,m;
13 int a[N],sei[N], so[N];
14 vector<int>e[N];
15 set<int>sg[N];
16 vector<pi> Re[N];
17 bool cmp(int a,int b){return sg[sei[a]].size() > sg[sei[b]].size();}
18 void dsu(int u){
19 int sot=0;
20 for(auto v : e[u]) dsu(v);
21 for(auto v : e[u]) so[++sot] = v;
22 if(!sot) {sg[sei[u]].insert(a[u]);return;}
23 sort(so+1,so+sot+1,cmp);
24 int fu = so[1];
25 for(int i=2;i<=sot;++i){
26 int nv = so[i];
27 for(auto v : sg[sei[nv]]){
28 auto ql = sg[sei[fu]].lower_bound(v);
29 if(ql!=sg[sei[fu]].end()){
30 int x = v, y = *ql, z = a[u];
31 if(x > y) swap(x, y);
32 if(z < x) {Re[y].pb(mp(z + 1, x));}
33 if(z > y) {Re[y].pb(mp(1, x));Re[z].pb(mp(-1, x));}
34 }
35 if(ql!=sg[sei[fu]].begin()) {
36 ql--;
37 int x = v, y = *ql, z = a[u];
38 if(x > y) swap(x, y);
39 if(z < x) {Re[y].pb(mp(z + 1, x));}
40 if(z > y) {Re[y].pb(mp(1, x));Re[z].pb(mp(-1, x));}
41 }
42 }
43 for(auto v : sg[sei[nv]]) sg[sei[fu]].insert(v);
44 }
45 sei[u]=sei[fu];
46 sg[sei[fu]].insert(a[u]);
47 }
48
49 struct node{
50 ll tsm, nsm;
51 int tmin;
52 node operator+(const node b) const {
53 if(!nsm && !tsm) return b;
54 if(!b.nsm && !b.tsm) return *this;
55 node ans;
56 ans.tsm = tsm + b.tsm;
57 ans.tmin = min(tmin, b.tmin);
58 ans.nsm = nsm * (tmin == ans.tmin) + b.nsm * (ans.tmin == b.tmin);
59 return ans;
60 }
61 };
62
63 struct segment{
64 #define lc k << 1
65 #define rc k << 1 | 1
66 #define lcon lc,l,mid
67 #define rcon rc,mid+1,r
68 #define Mid int mid=l+r>>1
69 node tm[N << 2];
70 int tag1[N << 2], tag2[N << 2];
71 void pu(int k){
72 tm[k] = tm[lc] + tm[rc];
73 }
74 void ad1(int k,int v){
75 tag1[k] += v;
76 tm[k].tmin += v;
77 }
78 void ad2(int k,int v){
79 tag2[k] += v;
80 tm[k].tsm += (ll)tm[k].nsm * v;
81 }
82 void build(int k,int l,int r){
83 tm[k].nsm = r - l + 1;
84 if(l==r)return; Mid;
85 build(lcon), build(rcon); pu(k);
86 }
87 void pd(int k){
88 if(tag1[k]){
89 ad1(lc,tag1[k]);
90 ad1(rc,tag1[k]);
91 }
92 if(tag2[k]){
93 if(tm[lc].tmin == tm[k].tmin) ad2(lc,tag2[k]);
94 if(tm[rc].tmin == tm[k].tmin) ad2(rc,tag2[k]);
95 }
96 tag1[k]=tag2[k]=0;
97 }
98 void mo(int k,int l,int r,int x,int y,int v){
99 if(x>y)return;if(x<=l&&r<=y) return ad1(k,v);
100 Mid; pd(k); if(x<=mid) mo(lcon,x,y,v);
101 if(y>mid) mo(rcon,x,y,v); pu(k);
102 }
103 void update(int k,int l,int r,int x,int y,int v){
104 if(x>y||tm[k].tmin>0)return;
105 if(x<=l&&r<=y) return ad2(k,v);
106 Mid; pd(k); if(x<=mid) update(lcon,x,y,v);
107 if(y>mid) update(rcon,x,y,v); pu(k);
108 }
109 ll qr(int k,int l,int r,int x,int y){
110 if(x<=l&&r<=y)return tm[k].tsm;
111 Mid; pd(k); ll ans = 0;
112 if(x<=mid) ans+=qr(lcon,x,y);
113 if(y>mid) ans+=qr(rcon,x,y);
114 return ans;
115 }
116 }ti;
117
118 vector<pi>rq[N];
119 ll ans[N];
120
121 int main(){
122 ios::sync_with_stdio(false);
123 cin>>n>>m;
124 for(int i=1;i<=n;++i)cin>>a[i];
125 for(int i=2,x;i<=n;++i)cin>>x,e[x].pb(i);
126 for(int i=1;i<=n;++i)sei[i]=i;
127 dsu(1); ti.build(1,1,n);
128 for(int i=1;i<=m;++i){
129 int l,r; cin >> l >> r;
130 rq[r].pb(mp(l,i));
131 }
132 for(int i=1;i<=n;++i){
133 for(auto [l, r] : Re[i]) {
134 if(l > 0) ti.mo(1,1,n,l,r,1);
135 else ti.mo(1,1,n,-l,r,-1);
136 }
137 ti.update(1,1,n,1,i,1);
138 for(auto [l, id] : rq[i]) {
139 ans[id] = ti.qr(1, 1, n, l, i);
140 }
141 }
142 for(int i=1;i<=m;++i) cout << ans[i] << "\n";
143 return 0;
144 }
标签：tmin,露露,Ynoi2003,pb,int,铃原,mp,ans,sei From： https://www.cnblogs.com/Saka-Noa/p/18025997