CustomCC0-1.0#ct-p4-042080
Range Majority Candidate
Summary
- •Phase 4 / segment-tree
- •Reasoning-first competitive programming drill
Problem Description
Support range query returning majority candidate and verify count offline. Your submission must justify algorithm choice, prove correctness, and test adversarial edge cases.
How to read this problem in plain language:
- This is a Phase 4 reasoning drill focused on segment-tree.
- Typical lenses to test first: segment-tree, boyer-moore, offline.
- Constraints reminder: n,q <= 2e5
Mini examples for mental simulation:
1) Boundary example: Candidate exists but fails final count check.
2) Adversarial example: Always majority. Explain expected behavior and why naive logic may fail.
Lite-mode writing target:
- Write 1~2 observations that shrink the search space.
- Name one final algorithm and state target complexity explicitly.
- Validate with at least 2 edge cases and one hand simulation.
Constraints
- •n,q <= 2e5
Analysis
Key Insight
Candidate query + count verification both logarithmic.
segment-treeboyer-mooreoffline