2D Range Tree Query Example

range2D.cpp

/*
LANG: C++
*/
#include <iostream>
#include <cstdio>

using namespace std;

#define MAXN 512

int RA, RB, RM;

int next_rand() {
  static int RS = 0;
  return RS = (1ll * RA * RS + RB) % RM;
}

int A[MAXN*2][MAXN*2];

int get_c(int x, int y, int CA, int CB, int QCA, int QCB) {
  if(QCB <= CA || CB <= QCA) return 0;
  if(QCA <= CA && CB <= QCB) {
    return A[x][y];
  }
  int CM = CA + (CB - CA) / 2;
  return max(get_c(x, 2 * y, CA, CM, QCA, QCB),
             get_c(x, 2 * y + 1, CM, CB, QCA, QCB));
}

int get_r(int x, int RA, int RB, int QRA, int QRB, int QCA, int QCB) {
  if(QRB <= RA || RB <= QRA) return 0;
  if(QRA <= RA && RB <= QRB) {
    return get_c(x, 1, 0, MAXN, QCA, QCB);
  }
  int RM = RA + (RB - RA) / 2;
  return max(get_r(x * 2, RA, RM, QRA, QRB, QCA, QCB),
             get_r(x * 2 + 1, RM, RB, QRA, QRB, QCA, QCB));
}

int main() {
  int N, Q, M; scanf("%d%d%d", &N, &Q, &M);
  for(int k = 0; k < M; k++) {
    int r1, c1, r2, c2; 
    scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
    r1--; c1--; r2--; c2--;

    for(int i = r1; i <= r2; i++) {
      for(int j = c1; j <= c2; j++) {
        int x;
        scanf("%d", &x);
        A[MAXN + i][MAXN + j] += x;
      }
    }
  }
  for(int i = 2 * MAXN - 1; i; i--) {
    for(int j = 2 * MAXN - 1; j; j--) {
      if(i < MAXN) {
        A[i][j] = max(A[2 * i][j], A[2 * i + 1][j]);
      } else if(j < MAXN) {
        A[i][j] = max(A[i][2 * j], A[i][2 * j + 1]);
      }
    }
  }
  
  scanf("%d%d%d", &RA, &RB, &RM);
  long long sum = 0;
  for(int i = 0; i < Q; i++) {
    int s = 1 + next_rand() % N;
    int r = 1 + next_rand() % (N - s + 1);
    int c = 1 + next_rand() % (N - s + 1);
    r--; c--;

    sum += get_r(1, 0, MAXN, r, r + s, c, c + s);
  }
  printf("%lld\n", sum);

  return 0;
}