Add #52 CDQ D&Q #63
Closed
Add #52 CDQ D&Q #63
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
chyyen
commented
May 13, 2023
•
chyyen
commented
- Read Contribute to NTHU-CPP.
- Rebase to the latest main branch.
- List all the references.
- Successfully build the website by mdBook with no error after the change.
- Exclude any irrelevant files.
- Link to the issue which is related to your change.
- Review the content by myself.
- Pass tests/CI.
harry900831
requested changes
Jun 12, 2023
src/Offline/CDQ.md
Outdated
| } | ||
| ``` | ||
| ### 三維偏序 | ||
| 定義偏序關係為 : |
src/Offline/ParallelBinarySearch.md
Outdated
| 剩下環狀的問題也很好解決，對於加值區間 \\( l,\ l + 1,\ ... \ m - 1,\ m,\ 1,\ 2,\ ... \ r \\) 的操作，把它拆成 \\( [l, m] \\) 以及 \\( [1, r] \\) 兩個操作就好了。 | ||
| </details> | ||
|
|
||
| > [CSES Houses and Schools](https://cses.fi/problemset/task/2087) |
There was a problem hiding this comment.
可以將此題往上移
使用f(i, j) 取代dp[i][j]
src/Offline/ParallelBinarySearch.md
Outdated
| BinarySearch(l, mid, ql); | ||
| BinarySearch(mid + 1, r, qr); | ||
| } | ||
| ``` |
There was a problem hiding this comment.
再講解一提感覺比較好
可以把底下的 meteor 往上拉到這裡
src/Offline/ParallelBinarySearch.md
Outdated
| } | ||
| ``` | ||
|
|
||
| ## 分治優化 |
src/Offline/ParallelBinarySearch.md
Outdated
| \end{align} | ||
| </details> | ||
|
|
||
| ## 練習 |
src/Offline/ParallelBinarySearch.md
Outdated
| * [Luogu P4602 混合果汁](https://www.luogu.com.cn/problem/P4602) | ||
| * [Tioj 1283 超大畫框設置](https://tioj.ck.tp.edu.tw/problems/1283) | ||
|
|
||
| ## Reference |
|
Ready for review @harry900831 |
harry900831
requested changes
Jul 21, 2023
There was a problem hiding this comment.
- Please resolve the comment by yourself after you fix it. If you want to discuss about it, just directly comment on it.
- Please make your explanation more clear. Imagine you are giving a lecture, I believe drawing dome figure would help the explanation.
- You may refer to others PR or the article that has been merged into NTHU-CPP to know that what kind of article you have to write.
- https://nthu-cp.github.io/NTHU-CPP/graph/lca.html
- https://nthu-cp.github.io/NTHU-CPP/math/introduction_to_generating_function.html
- https://nthu-cp.github.io/NTHU-CPP/graph/introduction_to_AP_bridge.html
- https://nthu-cp.github.io/NTHU-CPP/graph/introduction_to_BCC.html
- https://nthu-cp.github.io/NTHU-CPP/greedy/basic.html
- https://nthu-cp.github.io/NTHU-CPP/sqrt/sqrt_decomposition.html
- Please follow the format above too
- Please fix markdownlint and textlint.
- There should be two section
- Example problem: you should explain the problem in detail (including problem description, solution, code, time complexity/correctness analysis...). Also, please solve these problem with your own template code that mention above.
- Exercise problem: a problem list that reader may do if they want to practice treap, you don't have to explain these problem in detail, you may provide hint only.
- In my opinion, the article right now can't present that you have done a deep research on these topic. It looks like a zh-TW version of some post from CSDN blog.
- Please revise the sentence and the format. The layout could be better. Please try to use less but clear sentence to convey your idea. Please don't be limited by my comment, reorganize the whole article.
- You have to put more effort on this to get a great work. If the workload is too much, you may revise and merge the CDQ D&Q first.
- Please make your code short and clean, and use the formatter such as clang-format. Please prevent from useless comment on the code.
- Please read more online resources and do more problem about these topic.
- If you have no idea about how to enhance the quality of your article, just arrange a meeting with me on DC. We can discuss about it directly.
src/Miscellaneous/CDQ.md
Outdated
Comment on lines
3
to
7
| CDQ 分治是最早是由中國選手陳丹琦在中國國家集訓隊時整理並總結的一種想法。 | ||
| \ | ||
| 這個想法主要是透過分治的概念，去將跟偏序有關係的問題轉換得較簡單 ( 例如將原本需要的資料結構降一個維度 )。 | ||
| \ | ||
| 跟原來分治不太相同的點是，一般的分治將原問題分解成數個子問題後，每個子問題間的答案獨立。而 CDQ 分治中，則是分割出兩個子問題，且前面的子問題通常會影響到後面子問題的答案。 |
src/Miscellaneous/CDQ.md
Outdated
| 這樣一來就變成求二維的點集 \\( p_1, p_2 ... p_n \\) 中符合偏序關係的點對數量了。 | ||
|
|
||
| ### 二維偏序 | ||
| 就像前面說的，逆序數對就是其中一個二維偏序的例子，因為太過經典所以這邊就不做過多的解釋了，詳細的部分可以參考 [這份講義](https://drive.google.com/file/d/1SxuBzDDbgmpo2j2PyXEQ2Oe8BgVqM_DH/view) 。 |
src/Miscellaneous/CDQ.md
Outdated
Comment on lines
42
to
66
| ```cpp | ||
| void merge(int l, int m, int r){ | ||
| int lp = l, i = l, rp = m + 1; | ||
| while(lp <= m && rp <= r){ | ||
| if(a[lp] > a[rp]) | ||
| tmp[i++] = a[rp++], ans += m - lp + 1; | ||
| else | ||
| tmp[i++] = a[lp++]; | ||
| } | ||
| while(lp <= m) | ||
| tmp[i++] = a[lp++]; | ||
| while(rp <= r) | ||
| tmp[i++] = a[rp++]; | ||
| for(int j = l; j <= r; j++) | ||
| a[j] = tmp[j]; | ||
| } | ||
| void merge_sort(int l, int r){ | ||
| if(l == r) | ||
| return; | ||
| int m = (l + r) / 2; | ||
| merge_sort(l, m); | ||
| merge_sort(m + 1, r); | ||
| merge(l, m, r); | ||
| } | ||
| ``` |
src/Miscellaneous/CDQ.md
Outdated
| } | ||
| ``` | ||
| ### 三維偏序 | ||
| > [原題連結](https://zerojudge.tw/ShowProblem?problemid=c571) |
There was a problem hiding this comment.
有沒有除了 zerojudge 之外更好的 problem source 啊？
src/Miscellaneous/CDQ.md
Outdated
| (a_i, b_i, c_i) \prec (a_j, b_j, c_j) \equiv (a_i < a_j) \land (b_i < b_j) \land (c_i < c_j) | ||
| \end{align} | ||
| > 求符合偏序關係的點對數量。 | ||
| > * \\( N \leq 10^5 \\) |
There was a problem hiding this comment.
missing size of a_i, b_i, c_i
Comment on lines
27
to
41
| 先來想一下如果只有單筆詢問可以怎麼做：對答案二分搜，每次檢查目前的答案 \\( x \\) 時去跑過 \\( [l, r] \\) 一次來檢查有幾個數字小於等於 \\( x \\) 。 | ||
| \ | ||
| 這樣一來的時間複雜度為 \\( O(n\log n) \\) ，如果有 \\( q \\) 筆則為 \\( O(nq\log n) \\) ，這顯然是會 TLE 的，因此我們不能分開做每個詢問。 | ||
|
|
||
| 考慮將所有詢問存在一個數列 \\( Q \\) 中去分治求解，首先定義 \\( solve(l, r, Q) \\) 代表解決 \\( Q \\) 內的所有詢問，並且保證這些詢問的答案落在 \\( [l, r] \\) 。 | ||
| \ | ||
| 之後我們去分治他，將答案小於等於 \\( mid = \frac{l + r}{2} \\) 的詢問放到 \\( Q_l \\) ，答案大於 \\( mid \\) 的詢問放到 \\( Q_r \\) ，然後分治去解決 \\( solve(l, mid, Q_l) \\) 以及 \\( solve(mid + 1, r, Q_r) \\) 。 | ||
|
|
||
| 所以現在的問題是要如何知道每個詢問與 \\( mid \\) 的大小關係，這時候我們就可以用類似前面會 TLE 的做法了，也就是去算每個詢問區間小於 \\( mid \\) 的元素有多少個。 | ||
| \ | ||
| 具體來說，先跑過原數列，並將小於等於 \\( mid \\) 的數字在他的 index 上 \\( +1 \\) ，這樣一來每個詢問在檢查時就相當於區間查詢，而我們也可以用像是 BIT 來維護單點加值區間查詢。 | ||
|
|
||
| 接下來可以發現，其實不用每次都跑過整個數列 ，因為對於大於 \\( mid \\) 的元素，他在 \\( solve(l, mid, Q_l) \\) 中對詢問一定不會有貢獻，所以只需要計算他對 \\( Q_r \\) 的貢獻。 | ||
| \ | ||
| 而對於小於等於 \\( mid \\) 的元素，他對 \\( Q_r \\) 內詢問的貢獻都是不變的 ，那不如就在這一層中將這些詢問的 \\( k \\) 扣掉那些元素的數量，這樣一來就不用在 \\( solve(mid + 1, r, Q_r) \\) 中重複計算了，所以變成只需要計算對 \\( Q_r \\) 的貢獻。 |
Comment on lines
39
to
41
| 接下來可以發現，其實不用每次都跑過整個數列 ，因為對於大於 \\( mid \\) 的元素，他在 \\( solve(l, mid, Q_l) \\) 中對詢問一定不會有貢獻，所以只需要計算他對 \\( Q_r \\) 的貢獻。 | ||
| \ | ||
| 而對於小於等於 \\( mid \\) 的元素，他對 \\( Q_r \\) 內詢問的貢獻都是不變的 ，那不如就在這一層中將這些詢問的 \\( k \\) 扣掉那些元素的數量，這樣一來就不用在 \\( solve(mid + 1, r, Q_r) \\) 中重複計算了，所以變成只需要計算對 \\( Q_r \\) 的貢獻。 |
Comment on lines
94
to
106
| 首先考慮一下在上一題中，如果我們先將一些詢問跑過，再去將元素給更新上 BIT 的話會發生什麼事？ | ||
| \ | ||
| 會發現這些元素就不會對前面跑過的詢問產生貢獻，以時間序來說明的話其實就是先詢問完再新增一個元素上去。 | ||
|
|
||
| 再來，如果在把元素更新上 BIT 時不在他的 index 上 \\( + 1 \\) 而是 \\( -1 \\) 呢？ | ||
| \ | ||
| 這其實就相當於在這個時間點後將元素從原數列給刪除掉，因為對於後面的詢問，在 BIT 上加值 \\( -1 \\) 會使之前該元素的貢獻 ( 也就是之前在 BIT 上加 \\( +1 \\) ) 被抵銷掉，所以就不會計算到他的貢獻了。 | ||
|
|
||
| 那麼，把上述的兩種操作和在一起，其實就變成了修改的操作。 | ||
| \ | ||
| 因此可以將原數列、詢問以及修改都放在一起並按照時間序跑過，除了把修改視為先刪除 ( 在 BIT 上 \\( - 1\\) ) 再新增 ( 在 BIT 上 \\( + 1\\) ) 外，其他做法都會跟前面沒有帶修改的一樣。 | ||
|
|
||
| 複雜度的話，會跟不帶修改的版本一樣為 \\( O((n + q)\log n \log C ) \\) 。 |
| > \ | ||
| > 求每個人最少需要在第幾次操作後才能達到期望。 | ||
| > | ||
| > * \\( n, m, k \leq 3 * 10^5 \\) |
Comment on lines
326
to
327
| * [https://oi-wiki.org/misc/parallel-binsearch/](https://oi-wiki.org/misc/parallel-binsearch/) | ||
| * [https://link.springer.com/chapter/10.1007/978-3-319-72547-5_15#Sec20](https://link.springer.com/chapter/10.1007/978-3-319-72547-5_15#Sec20) |
There was a problem hiding this comment.
Please read more references
|
Please resolve the comment if you fix it. Is this PR ready for review? |
CDQ 的部分目前已經寫完了差 Markdownlint Error 的部分，但整體二分還需要寫一下，想問學長能不能先將這個 PR 改成只有 CDQ，整體二分我會再開一個 PR 出來 |
|
Sure~ |
harry900831
requested changes
Sep 17, 2023
src/SUMMARY.md
Outdated
| @@ -36,6 +36,7 @@ | |||
| - [杜教篩](math/du_sieve.md) | |||
| - [Arithmetic Function Revisit](math/revisit_arithmetic_function.md) | |||
| - [Miscellaneous]() | |||
| - [CDQ divide and conquer](miscellaneous/cdq.md) | |||
There was a problem hiding this comment.
CDQ Divide and Conquer
src/miscellaneous/cdq.md
Outdated
| ```cpp | ||
| #include <bits/stdc++.h> | ||
| #define pb push_back | ||
| #define int long long |
There was a problem hiding this comment.
don't use define int long long
src/miscellaneous/cdq.md
Outdated
| ```cpp | ||
| #include <bits/stdc++.h> | ||
| #define pb push_back | ||
| #define int long long |
src/miscellaneous/cdq.md
Outdated
|
|
||
| ```cpp | ||
| #include <bits/stdc++.h> | ||
| #define int long long |
src/miscellaneous/cdq.md
Outdated
|
|
||
| </details> | ||
|
|
||
| ## Reference |
src/miscellaneous/cdq.md
Outdated
Comment on lines
66
to
70
| ```cpp | ||
| #include <bits/stdc++.h> | ||
| #define ll long long | ||
| using namespace std; | ||
|
|
There was a problem hiding this comment.
IMO, your code can be more elegant. I've modified this as an example.
Please try to make your code clean and clear for all the following code.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
struct item {
int a, b, c, id;
item() {}
item(vector<int>&& x, int _id) : id(_id) {
sort(x.begin(), x.end());
a = x[0];
b = x[1];
c = x[2];
}
};
struct BIT {
int b[3 * N];
void upd(int p, int v) {
while (p < 3 * N) {
b[p] += v;
p += p & -p;
}
}
int query(int p) {
int sum = 0;
while (p) {
sum += b[p];
p -= p & -p;
}
return sum;
}
} bit;
ll ans;
void CDQ(vector<item>& a) {
if (a.size() <= 1) return;
int mid = a.size() >> 1;
vector<item> al(a.begin(), a.begin() + mid);
vector<item> ar(a.begin() + mid, a.end());
CDQ(al);
CDQ(ar);
int p = 0;
vector<int> his;
for (auto i : ar) {
while (p < mid && al[p].b < i.b) {
bit.upd(al[p].c, 1);
his.emplace_back(al[p].c);
p++;
}
ans += bit.query(i.c - 1);
}
sort(a.begin(), a.end(), [](item x, item y) { return x.b < y.b; });
for (auto x : his) bit.upd(x, -1);
}
void solve() {
int n;
cin >> n;
vector<item> a(n);
vector<int> v;
for (int i = 0; i < n; i++) {
int h, w, d;
cin >> h >> w >> d;
a[i] = item({h, w, d}, i);
v.insert(v.end(), {h, w, d});
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
auto lisan = [&](int& x) {
x = lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
};
for (auto& i : a) {
lisan(i.a);
lisan(i.b);
lisan(i.c);
}
sort(a.begin(), a.end(),
[](item x, item y) { return x.a == y.a ? x.b > y.b : x.a < y.a; });
CDQ(a);
cout << (ans > 0 ? "Yes\n" : "No\n");
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
solve();
}There was a problem hiding this comment.
The reason why I pull out history from bit structure is to keep bit clean as an template
src/miscellaneous/cdq.md
Outdated
|
|
||
| void upd(int p, int v, bool to_his = true) { | ||
| if (to_his) | ||
| history.push_back(make_pair(p, v)); |
src/miscellaneous/cdq.md
Outdated
| void upd(int p, int v, bool to_his = true) { | ||
| if (to_his) | ||
| history.push_back(make_pair(p, v)); | ||
| while (p < 3 * N) { |
There was a problem hiding this comment.
If you use vector instead of int array, you can avoid the mistake that chasing the size of the array but forget to change the variable over here.
src/miscellaneous/cdq.md
Outdated
Comment on lines
157
to
159
| i.a = lower_bound(v.begin(), v.end(), i.a) - v.begin() + 1; | ||
| i.b = lower_bound(v.begin(), v.end(), i.b) - v.begin() + 1; | ||
| i.c = lower_bound(v.begin(), v.end(), i.c) - v.begin() + 1; |
There was a problem hiding this comment.
use function to avoid duplicate code. It can prevent dumb typo
src/miscellaneous/cdq.md
Outdated
Comment on lines
371
to
380
| struct op { | ||
| int x, y, w; | ||
| int d, u; | ||
| int type, id; | ||
| op() {} | ||
| op(int _x, int _y, int _w, int _id) | ||
| : x(_x), y(_y), w(_w), id(_id), type(0) {} | ||
| op(int _x, int _y, int _d, int _u, int _id, int _t) | ||
| : x(_x), y(_y), d(_d), u(_u), id(_id), type(_t) {} | ||
| }; |
There was a problem hiding this comment.
This class looks pretty scary..
|
The overall structure LGTM! Please resolve the conversation if you fix it (including the ole ones) |
chyyen
force-pushed
the
CDQ_and_Parallel_Binary_Search
branch
from
06ca7c5
to
b257419
Compare
|
@chyyen why are you closing this? |
|
Sorry, I accidentally closed the PR, and I didn't know I can reopen the PR at that time, so I just created a new PR. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.