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

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

You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x1 y1 z1 x2 y2 z2 W updates the value of each block whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive). where n<=100,m<=1000 what will be the solution of this problem? I have a solution which has a complexity of n*m*log4(n*n) but I really doubt about log4(n*m) part. I am really confused.

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

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

For 3D segtree solution Update and query is log^3(N).

Oh wait, N and M are small?

Make one segment tree. Then brute force other two dimensions with for loops.