AtCoder Beginner Contest 106 D - AtCoder Express 2

セグメント木でやろうとして90分くらい使ったらもう眠いしわからんしで解説読んだらシンプルな累積和でよかった。就寝。

歯を磨いてたら解説の図が頭の中でどうも引っかかって、正方形ではなくてその左上半分ではないかという気がする。L_i <= R_i の制約外せば正方形ではあるが…（制約はずさなくても正方形で描くほうが適切であることに記事の後半で気づいた）

眠くて理解しきれていないので解法を丁寧に書く。

int N,M,Q;
cin>>N>>M>>Q;
vector<int> L(M_MAX,0),R(M_MAX,0);
  
int X[N_MAX][N_MAX],C[N_MAX][N_MAX];
fill(X[0],X[N_MAX-1],0);
fill(C[0],C[N_MAX-1],0);

FOR(i,1,M+1) {
  cin>>L[i]>>R[i];
  ++X[L[i]][R[i]];
}
FOR(i,1,N+1)
  FOR(j,1,N+1) C[i][j] = C[i][j-1] + X[i][j];

REP(i,Q) {
  int p,q;
  cin>>p>>q;
  int sum = 0;
  FOR(j,p,q+1) sum += C[j][q] - C[j][p-1];
  cout << sum << endl;
}

まず

++X[L[i]][R[i]];

で x_{l,r} を数えていますよね。次に

C[i][j] = C[i][j-1] + X[i][j];

で x_{l,r} の累積和を計算しておいている。最後に

FOR(j,p,q+1) sum += C[j][q] - C[j][p-1];

で区間 [p,q] に収まる x_{l,r}、すなわち x_{p,p} から x_{q,q} までの和を数えるために c_{j,q} - c_{j,p-1} = x_{j,p} + ... + x_{j,q} を j = p から q まで走らせている。求める和は x_{i,j} の i,j 両方を p から q まで走らせたものなのでこういうコードになっている。

x_{p,p} + ... + x_{p,q} でひとかたまり、次に x_{p+1,p} + ... + x_{p+1,q}、…、 x_{q,p} + ... + x_{q,q} というように続いていく。

こうしてみると解説冒頭の図が正方形になっているのはむしろ自然だ。問題の制約上 i > j であるような x_{i,j} が 0 であるだけ。

累積和はそのままなら 1 からある要素までの総和が取り出せて、適切な区間で切って引き算すればある部分列の総和が取り出せる。そんな累積和の部分的な和のさらに総和が今回の答え。なんか高校数学みたいな問題だなあ。

累積和含め、今回のように区間がからむものはセグメント木や Binary indexed tree を工夫して用いることで効率的な計算ができるらしい。N が大きかったらセグ木や BIT のほうがいいのかも。