Skip to content

Commit e7f05d9

Browse files
liuyuboboboliuyubobobo
committed
LCP52 added.
1 parent bd504e4 commit e7f05d9

File tree

3 files changed

+152
-0
lines changed

3 files changed

+152
-0
lines changed

‎LC/LCP52/cpp-LCP52/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.21)
2+
project(C)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(C main.cpp)

‎LC/LCP52/cpp-LCP52/main.cpp

Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,145 @@
1+
/// Source : https://leetcode-cn.com/problems/QO5KpG/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-04-17
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <map>
8+
9+
using namespace std;
10+
11+
12+
/// Using Segment Tree
13+
/// Time Complexity: O(nlogn)
14+
/// Space Complexity: O(n)
15+
16+
/// Definition for a binary tree node.
17+
struct TreeNode {
18+
int val;
19+
TreeNode *left;
20+
TreeNode *right;
21+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
22+
};
23+
24+
template<typename T>
25+
class SegmentTree{
26+
27+
private:
28+
int n;
29+
vector<T> tree, lazy;
30+
T (*combine)(T a, T b);
31+
32+
public:
33+
SegmentTree(int n, T (*combine)(T a, T b)): n(n), tree(4 * n, 0), lazy(4 * n, -1){
34+
this->combine = combine;
35+
}
36+
37+
void set(int uL, int uR, T v){
38+
if(uL > uR) return;
39+
set(0, 0, n - 1, uL, uR, v);
40+
}
41+
42+
T query(int qL, int qR){
43+
if(qL > qR) return 0;
44+
return query(0, 0, n - 1, qL, qR);
45+
}
46+
47+
private:
48+
void set(int treeID, int treeL, int treeR, int uL, int uR, T v){
49+
50+
if(uL > treeR || uR < treeL) return;
51+
52+
if(uL <= treeL && treeR <= uR){
53+
tree[treeID] = (treeR - treeL + 1) * v;
54+
lazy[treeID] = v;
55+
return;
56+
}
57+
58+
if(lazy[treeID] != -1)
59+
push(treeID, treeL, treeR);
60+
61+
int mid = (treeL + treeR) / 2;
62+
set(2 * treeID + 1, treeL, mid, uL, uR, v);
63+
set(2 * treeID + 2, mid + 1, treeR, uL, uR, v);
64+
tree[treeID] = combine(tree[treeID * 2 + 1], tree[treeID * 2 + 2]);
65+
return;
66+
}
67+
68+
T query(int treeID, int treeL, int treeR, int qL, int qR){
69+
70+
if(qL <= treeL && treeR <= qR)
71+
return tree[treeID];
72+
73+
if(lazy[treeID] != -1)
74+
push(treeID, treeL, treeR);
75+
76+
int mid = (treeL + treeR) / 2;
77+
if(qR <= mid) return query(2 * treeID + 1, treeL, mid, qL, qR);
78+
if(qL >= mid + 1) return query(2 * treeID + 2, mid + 1, treeR, qL, qR);
79+
80+
T resl = query(2 * treeID + 1, treeL, mid, qL, qR);
81+
T resr = query(2 * treeID + 2, mid + 1, treeR, qL, qR);
82+
T res = combine(resl, resr);
83+
return res;
84+
}
85+
86+
private:
87+
void push(int treeID, int treeL, int treeR){
88+
89+
if(treeL == treeR) return;
90+
91+
T v = lazy[treeID];
92+
93+
int mid = (treeL + treeR) / 2;
94+
int tn = treeR - treeL + 1, tnl = mid - treeL + 1, tnr = tn - tnl;
95+
96+
tree[treeID * 2 + 1] = v * tnl;
97+
tree[treeID * 2 + 2] = v * tnr;
98+
99+
lazy[treeID * 2 + 1] = v;
100+
lazy[treeID * 2 + 2] = v;
101+
102+
lazy[treeID] = -1;
103+
}
104+
};
105+
106+
class Solution {
107+
108+
public:
109+
int getNumber(TreeNode* root, vector<vector<int>>& ops) {
110+
111+
vector<int> index2value;
112+
init(root, index2value);
113+
114+
int n = index2value.size();
115+
// for(int e: index2value) cout << e << ' '; cout << '\n';
116+
117+
SegmentTree<int> seg_tree(n, [](int a, int b){return a + b;});
118+
119+
for(const vector<int>& op: ops){
120+
int color = op[0], l_value = op[0], r_value = op[1];
121+
int l = lower_bound(index2value.begin(), index2value.end(), l_value) - index2value.begin();
122+
int r = (upper_bound(index2value.begin(), index2value.end(), r_value) - index2value.begin()) - 1;
123+
124+
// cout << l << ' ' << r << ' ' << color << '\n';
125+
seg_tree.set(l, r, color);
126+
}
127+
return seg_tree.query(0, n - 1);
128+
}
129+
130+
private:
131+
void init(TreeNode* node, vector<int>& index2value){
132+
133+
if(!node) return;
134+
135+
init(node->left, index2value);
136+
index2value.push_back(node->val);
137+
init(node->right, index2value);
138+
}
139+
};
140+
141+
142+
int main() {
143+
144+
return 0;
145+
}

‎readme.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2106,6 +2106,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
21062106
| | | | | | |
21072107
| LCP50 | [宝石补给](https://leetcode-cn.com/problems/WHnhjV/) | [无] | [C++](LC/LCP50/cpp-LCP50/) | | |
21082108
| LCP51 | [烹饪料理](https://leetcode-cn.com/problems/UEcfPD/) | [无] | [C++](LC/LCP51/cpp-LCP51/) | | |
2109+
| LCP52 | [二叉搜索树染色](https://leetcode-cn.com/problems/QO5KpG/) | [无] [缺：非线段树做法] | [C++](LC/LCP52/cpp-LCP52/) | | |
21092110
| | | | | | |
21102111

21112112
## 其他

0 commit comments

Comments
 (0)