Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[問題案]Static RMQ(staticrmq) #34

Closed
yosupo06 opened this issue Sep 13, 2019 · 3 comments · Fixed by #551
Closed

[問題案]Static RMQ(staticrmq) #34

yosupo06 opened this issue Sep 13, 2019 · 3 comments · Fixed by #551

Comments

@yosupo06
Copy link
Owner

No description provided.

@kmyk kmyk mentioned this issue Jan 8, 2020
Closed
@yosupo06
Copy link
Owner Author

クエリが完全にランダムだとブロック分割で容易に<O(n), O(1)>が達成できてしまうので、幅の小さいクエリばっかのケースを用意する

@yosupo06 yosupo06 reopened this Mar 15, 2020
@madhur4127
Copy link

It is amusing to see that O(1) sparse table solution has the same time as O(log n) iterative segment tree.

Sparse table - 85 ms
Segment Tree - 86 ms

@yosupo06
Copy link
Owner Author

We need O(N log N) time for constructing the sparse table and N = Q in this problem...

@yosupo06 yosupo06 mentioned this issue Jul 17, 2020
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

use param and add case for staticrmq yosupo06/library-checker-problems
2 participants
@yosupo06 @madhur4127