---
title: 線段樹經典例題 翻譯、講解
---
# 線段樹經典例題 翻譯、講解
---
## [CSES 區間相異元素個數](https://cses.fi/problemset/task/1734)
----
### 題敘：
現在有 $N$ 個數字和 $Q$ 次詢問，問你區間 $[L, R]$ 內的相異數字的個數
----
### 解答：
簡單的想法是：直接硬算，複雜度 $O(N^2)$，$N, Q=2\times10^5$，直接下去。
這裡要引入一個技巧叫做「離線」，這是什麼意思呢 ? 也就是不必在每次詢問的時候直接回答出答案，而是先將詢問一次讀取完，經過許多操作後，再一次處理所有詢問：
首先針對這題，我們可以先將詢問全部儲存下來 ( 常會用到 std::tuple, std::array 之類的東西 )
我們嘗試維護一個含有左端點為 $1$，右端點為 $1$ ~ $N$ 的數字的線段樹，
每次，我們先依次加入第 $i$ 個數字 $a_i$，並且進行以下操作：
1. 如果 $a_i$ 未被加入過，則將線段樹的第 $i$ 個位置改成 $1$
2. 反之，將同個數字前一個改成 $1$ 的位置改成 $0$，將第 $i$ 個位置改成 $1$
接著，對於每個右端點是 $i$ 的詢問，我們只需求線段樹區間 $L, R$ 的總和即可。
由上述可見：
1. 若一個右端點是 $i$ 的區間包含了 $1$ 個 $x$，那他一定是目前被加入的 $x$ 數字的最右邊那個，而他的數值就會加上 $1$
2. 若他包含了 $2$ 個以上的數字，那他一定也會加到最右邊的數字 $x$，而因為前面的 $x$ 的位置都已經被修改成 $0$，最後的總和也是 $1$
複雜度 $O((Q + N)logN)$
----
### 程式碼：
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
int arr[maxn], ans[maxn], seg[4 * maxn];
vector<pair<int, int> > query[maxn];
map<int, int> prepos;
void add(int l, int r, int p, int v, int i) {
if(l == r) {
seg[i] += v;
return ;
}
int mid = (l + r) >> 1;
if(p <= mid) add(l, mid, p, v, i << 1);
else add(mid + 1, r, p, v, i << 1 | 1);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
int cal(int l, int r, int L, int R, int i) {
if(L <= l and R >= r) return seg[i];
int mid = (l + r) >> 1, res = 0;
if(L <= mid) res += cal(l, mid, L, R, i << 1);
if(R > mid) res += cal(mid + 1, r, L, R, i << 1 | 1);
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> arr[i];
for(int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
query[r].push_back({l, i});
}
for(int i = 1; i <= n; i++) {
int x = arr[i];
if(prepos.find(x) == prepos.end()) add(1, n, i, 1, 1);
else add(1, n, prepos[x], -1, 1), add(1, n, i, 1, 1);
prepos[x] = i;
for(auto [p, id]: query[i]) {
ans[id] = cal(1, n, p, i, 1);
}
}
for(int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
}
```
:::
---
## [CSES Hotel Queries](https://cses.fi/problemset/task/1143/)
----
### 題敘：
在一條街上有 $N$ 間旅館，分別擁有 $h_i$ 間單人房，
並有 $M$ 組客人，每組客人有 $r_i$ 位
已知每組客人須住在同一間旅館，他們會依序由道路的左端往右尋找第一間剩餘房間大於等於客人數量的旅館，並且剩餘房間將會減 $r_i$ 位。
請輸出每組客人的旅館位置，若沒有適當的旅館，請輸出 $0$
----
### 解答：
還是一樣：簡單的想法是：直接硬算，複雜度 $O(MN)$，$M, N=2\times10^5$，直接下去。
這裡也有個技巧叫做「線段樹二分搜」，也就是沿著線段樹的根節點往下搜尋，
本題需要找出最左邊大於等於 $r_i$ 的格子，那我們可以在線段樹的每個節點存儲「這個節點包含的區間，最大的旅館的房間數」，那我們就可以進行以下操作，從根節點開始：
1. 若左邊的節點的值大於等於 $r_i$，那代表左邊的區間有一個旅館能容納這組客人，故往左節點遞迴
2. 若左邊的值不夠，而右邊的值夠，那我們就可以往右節點遞迴
3. 若兩邊都不夠，則無解
複雜度 $O(MlogN)$
----
### 程式碼：
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define i1 (i << 1)
#define i2 (i << 1 | 1)
using namespace std;
const int maxn = 2e5;
int seg[4 * maxn], arr[maxn], ans;
void build(int l, int r, int i) {
if(l == r) {
seg[i] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, i1);
build(mid + 1, r, i2);
seg[i] = max(seg[i1], seg[i2]);
}
void bs(int x, int l, int r, int i) {
if (l == r) {
if (seg[i] >= x) ans = l;
seg[i] -= x;
return;
}
int mid = (l + r) >> 1;
if(seg[i1] >= x) bs(x, l, mid, i1);
else if(seg[i2] >= x) bs(x, mid + 1, r, i2);
seg[i] = max(seg[i1], seg[i2]);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> arr[i];
build(1, n, 1);
while(q--) {
int x;
cin >> x;
ans = 0;
bs(x, 1, n, 1);
cout << ans << ' ';
}
}
```
:::
---
## [CF E. Boring Segments](https://codeforces.com/contest/1555/problem/E)
----
### 題敘：
現在有 $N$ 個線段，範圍從 $L_i$ 到 $R_i$，並有一個數值 $w_i$
現在你可以選任意幾個線段，使得線段的聯集能夠覆蓋整個 $1$ 到 $N$ 區間
而如此的花費是 最大的 $w_i$ - 最小的 $w_i$，
請問最小的花費是多少 ?
----
### 解答：
暴力解：$N!$，電腦直接下去
同時，我們可以先將線段以價值排序，利用滑動視窗的方法，對於每個左端點 $L$，找到一個滿足完全覆蓋的右端點 $R_L$，每次計算價值後取 $min$。
要如何證明這是對的呢 ? 上述也就是代表說「包含第 $L$ 個線段」的最小花費可能。
而要怎麼利用線段樹呢 ? 若每次加入一個線段就直接在線段樹裡面的區間都加上 $1$，那我們知道區間 $1$ 到 $N$ 被完全覆蓋若且唯若**區間最小值大於 0**
如此一來，複雜度變成 $O(NlogM)$
----
### 程式碼：
:::spoiler 很醜的 Code，加減看
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define g0 get<0>(i)
#define g1 get<1>(i)
#define g2 get<2>(i)
#define f first
#define s second
#define lowbit(x) (x&-x)
#define endl '\n'
#define mid ((l+r)>>1)
#define i1 (i<<1)
#define i2 (i1+1)
#define iofaster ios::sync_with_stdio(0);cin.tie(0)
using namespace std;
const int maxn = 1e6 + 5 ;
const int mod = 1e9 + 7 ;
const int INF = 1e9 + 9 ;
int minn[maxn*4],lazy[maxn*4];
inline void pushdown(int l,int r,int i) {
if(lazy[i]) {
lazy[i1]+=lazy[i];
lazy[i2]+=lazy[i];
minn[i1]+=lazy[i];
minn[i2]+=lazy[i];
lazy[i]=0;
}
}
void add(int l,int r,int L,int R,int i,int w) {
if(L<=l and R>=r) {
lazy[i]+=w;
minn[i]+=w;
return ;
}
pushdown(l,r,i);
if(L<=mid) add(l,mid,L,R,i1,w);
if(R>mid) add(mid+1,r,L,R,i2,w);
minn[i]=min(minn[i1],minn[i2]);
}
signed main()
{
iofaster;
vector<tup>q;
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) {
int a,b,w;
cin>>a>>b>>w;
q.pb({w,a,b-1});
}
sort(q.begin(),q.end());
multiset<int>st;
int ps=0,pf=0,ans=INF;
while(ps<n) {
while(minn[1]==0 and ps<n) {
auto i=q[ps];
st.insert(g0);
add(1,m-1,g1,g2,1,1);
ps++;
}
while(minn[1]) {
ans=min(ans,*st.rbegin()-*st.begin());
auto i=q[pf];
st.erase(st.find(g0));
add(1,m-1,g1,g2,1,-1);
pf++;
}
}
cout<<ans;
}
```
:::
---
## [洛谷 區間 Mex](https://www.luogu.com.cn/problem/P4137)
----
### 題敘：
現在有一個長度為 $N$ 的序列，和 $M$ 次詢問，每次問你區間 $[L, R]$ 的 $mex$ 是多少
[$mex$](https://en.wikipedia.org/wiki/Mex_(mathematics)) 不是 $typo$，的確有這個東西，代表著是序列內第一個沒有出現的非負整數。
如：
$[1, 3, 4]$ 的 $mex$ 就是 $0$
$[0, 1, 3, 4]$ 的 $mex$ 是 $2$
$[0, 1, 2, 3]$ 的 $mex$ 是 $4$
----
### 解答：
暴力解：
每次詢問都講數字放到一個陣列，$sort$ 一遍後找出 $mex$。
複雜度 $O(QNlogN)$，爆炸。
我們要引入一個線段樹技巧「值域線段樹」，也就是你們上次在矩形覆蓋面積的線段樹是同個類型，並且，本題需要搭配「離線」算法，也就是剛才區間相異元素個數的想法，最後再加入一個「線段樹二分搜」，也就是剛剛的 hotel queries 那題。
聽起來太多技巧合併在一起了吧 ? 但其實主要熟悉離線算法，其他兩項技巧是不太難的。
首先同樣將詢問先儲存下來，開始建立一個包函左端點為 $1$，右端點為 $1$ 到 $N$ 的數字的值域線段樹。
每次到了一個新的右端點 $i$，我們將數字放進線段樹，而這裡我們在線段樹裡面要放的數值是「在這個節點包含的區間中，每個數字出現在最右邊的一次的位置的最小值」，
如此一來，我們就可以處理詢問的問題。在線段樹二分搜的時候，進行下列操作：
1. 若詢問的左節點大於「每個數字出現在最右邊的一次的位置的最小值」，那我們就向左節點遞迴，代表因為其中某個數字沒有出現在我要查詢的區間內，就往左走，才能找到 $mex$
2. 反之，則向右走
3. 若到了葉節點，則我們找到了 $mex$
複雜度 $O(Qloga_i)$
----
### 程式碼：
:::spoiler 很久之前寫的 Code，所以很醜
```cpp=
#include <bits/stdc++.h>
#define m ((l+r)>>1)
#define i1 i<<1
#define i2 (i<<1)+1
#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define int long long
#define lowbit(x) (x&-x)
using namespace std;
const int maxn = 1000000 ;
int c[maxn],num[maxn],full[maxn];
int n,q,x=1,pos=1;
bool cmp1(tup t1,tup t2){return g2(t1)<g2(t2);}
bool cmp2(tup t1,tup t2){return g0(t1)<g0(t2);}
void build(int l,int r,int i)
{
if(l==r) return ;
build(l,m,i1);
build(m+1,r,i2);
}
void update(int p,int l,int r,int v,int i)
{
if(l==r)
{
c[i]=v;
return ;
}
if(p<=m) update(p,l,m,v,i1);
if(p>m) update(p,m+1,r,v,i2);
c[i]=min(c[i1],c[i2]);
}
int query(int p,int l,int r,int i)
{
if(l==r) return r;
if(p>c[i1]) return query(p,l,m,i1);
else eturn query(p,m+1,r,i2);
}
signed main()
{
cin>>n>>q;
for(int b=1;b<=n;b++) cin>>num[b];
build(0,200005,1);
vector< tup >v;
while(q--)
{
int l,r;
cin>>l>>r;
v.push_back(make_tuple(x++,l,r));
}
sort(v.begin(),v.end(),cmp1);
for(auto &i:v)
{
while(pos<=g2(i)) update(num[pos],0,200005,pos,1),pos++;
g2(i)=query(g1(i),0,200005,1);
}
sort(v.begin(),v.end(),cmp2);
for(auto i:v) cout<<g2(i)<<endl;
}
```
:::
---
## [TOI 1!模考P4](http://mdcpp.mingdao.edu.tw/problem/TOI_2021_1_pD)
----
### 題敘：
----
### 解答：
----
### 程式碼：
---
## [CF 609F](https://codeforces.com/contest/609/problem/F)
----
### 題敘：
----
### 解答：
----
### 程式碼：
---
Sign in with Wallet
Connect another wallet