Блог пользователя AnotherRound

Автор AnotherRound, история, 8 лет назад, По-английски

After reading the solution to problem D from last CF round, I decided to implement it(the idea with 2D segment tree). I know that there are other(faster) ways to implement segment tree as needed for RMQ, but I wanted to implement it with standard(check my code for what I call standard) implementation of 2D seg tree. Unfortunately, I got TL on test 16. So I wanted to ask whether there is some way to optimise my solution(without using the other faster way to implement segment tree). Link to my code: http://mirror.codeforces.com/contest/677/submission/18295468

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

This is actually not a 2D segment tree. This is a quad tree which has worst case complexity O(N) per query (in your case it can become O(N*M) per operation). Try implementing it using a 2D Fenwick tree or like you said 2D segment tree (not Quad tree).