Codeforces Beta Round #88 D. Not Quick Transformation

Codeforces

久々に本番で解けなかったシリーズを書いてみる。

Not Quick Transformation

問題の概要

  • 数列a = {1, 2, ..., N} が与えられる
  • 数列aの奇数番目のみを並べた数列をodd, 偶数番目のみを並べた数列をevenとする
  • F(a) = F(odd) + F(even) として新たに数列bを得る
    • a = {1, 2, 3, 4} なら b = {1, 3} + {2, 4} = {1, 3, 2, 4} という感じ
  • 数列b上で、l≦i≦r かつ u≦bi≦vを満たす項の総和をmodで割った余りを求める


解法

  • 本番はなぜかFを再帰的に適用してなくてpretestすら通らなかった。
  • l=0、u=0とした問題を考える
    • つまり、b上の第r項までで値がv以下のものの総和を求める
  • odd部分とeven部分に分け、各数列に1, ..., nを割り当て直せば再帰的に計算できる
    • odd部分は得られた解を2倍して項数を引けば求める答え
    • even部分は得られた解を2倍すれば求める答え
    • n = rとなった時点で1からmin(n, v)までの総和を返す
  • odd部分の項数は (n+1)/2 になる
    • r > (n+1)/2 ならodd部分は自明に解が求まる
    • r <= (n+1)/2 ならeven部分を考慮しなくて良い(総和0)
    • 考慮する区間の長さは半分になっていくので、計算量はO(log n)
  • この問題を解く関数をcalc(r, u)とでもしておく
  • (calc(r, v)-calc(l-1, v))-(calc(r, u-1)-calc(l-1, u-1)) が求める値
#include <iostream>
#include <stdio.h>

using namespace std;

pair<long long, long long> calcB(long long n, long long r, long long upper, long long mod){
    if(r <= 0) return make_pair(0,0);
    if(r == n){
        long long res = min(upper, n)%mod;
        return make_pair((res*(res+1)/2)%mod, res);
    }
    pair<long long, long long> left  = calcB((n+1)/2, min(r, (n+1)/2), (upper+1)/2, mod);
    pair<long long, long long> right = calcB(n/2, r-(n+1)/2, upper/2, mod);
    return make_pair((2*left.first-left.second+2*right.first+mod)%mod, (left.second+right.second)%mod);
}

long long calcA(long long n, long long l, long long r, long long upper, long long mod){
    return (calcB(n, r, upper, mod).first-calcB(n, l-1, upper, mod).first+mod)%mod; 
}

int main(){
    long long n, m, mod;
    while(cin >> n >> m >> mod){
        for(int i=0;i<m;i++){
            long long l, r, u, v; scanf("%lld %lld %lld %lld", &l, &r, &u, &v);
            printf("%lld\n", (calcA(n, l, r, v, mod)-calcA(n, l, r, u-1, mod)+mod)%mod);
        }
    }
}