JOI Open Contest 2015 - Sterilizing Spray ふたたび

kagamiz.hatenablog.com

この問題、さすがに実装も定数倍も重い解法を書いてしまっていたので、別のアプローチで解き直してみました。

解法 :
のときは前の記事の解法と同様である。
のとき、全体で意味のある除算の操作の回数を考えてみると、 として 回であることが分かる。
なぜならば、任意の数は 回割ると になるからである。そこで、意味のある除算だけを行うことを考える。
これには、除算対象の区間の全ての数が であれば割る処理を終えるという再帰的な操作を行えば良い。
除算対象の区間の全ての数が かどうかは、RMQを用いて簡単に確かめられる。
計算量は 程度で前回のものと形だけだと差がないが、ポインタ操作などが無い分定数倍が軽くなっている。
手元の環境で最大ケースが 1 秒程度になった。

コード :

#include <bits/stdc++.h>

#define MAX_N (100010)
#define MAX_Q (100010)
#define MAX_S (131072)

using namespace std;

typedef long long Int;

class BIT {
	Int A[MAX_N + 1];
public:
	BIT(){
		memset(A, 0, sizeof(A));
	}
	void add(int p, Int x){
		for (p++; p <= MAX_N; p += p & -p) A[p] += x;
	}
	Int sum(int p){
		Int ret = 0;
		for (p++; p; p &= (p - 1)) ret += A[p];
		return (ret);
	}
};

BIT bit;
int N, Q, K;
int C[MAX_N];
int S[MAX_Q], T[MAX_Q], U[MAX_Q];
pair<int, int> seg[2 * MAX_S - 1];

void update(int k, int x)
{
	k += MAX_S - 1;
    seg[k] = make_pair(x, k - MAX_S + 1);
    while (k){
        k = (k - 1) / 2;
        seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
}

pair<int, int> getMax(int a, int b, int k = 0, int l = 0, int r = MAX_S)
{
    if (b <= l || r <= a) return (make_pair(-1, -1));
    if (a <= l && r <= b) return (seg[k]);
    pair<int, int> lch = getMax(a, b, k * 2 + 1, l, (l + r) / 2),
                   rch = getMax(a, b, k * 2 + 2, (l + r) / 2, r);
    return (max(lch, rch));
}

void divide(int L, int R)
{
    if (L > R) return;
    pair<int, int> p = getMax(L, R + 1);
    if (p.first == 0) return;
    bit.add(p.second, -p.first);
    bit.add(p.second, p.first / K);
    C[p.second] /= K;
    update(p.second, C[p.second]);
    divide(L, p.second - 1);
    divide(p.second + 1, R);
}

int main()
{
	scanf("%d %d %d", &N, &Q, &K);

	for (int i = 0; i < N; i++){
		scanf("%d", C + i);
	}

	for (int i = 0; i < Q; i++){
		scanf("%d %d %d", S + i, T + i, U + i);
	}

	for (int i = 0; i < N; i++) bit.add(i, C[i]);
    for (int i = 0; i < MAX_S; i++) update(i, i < N ? C[i] : -1);

	for (int i = 0; i < Q; i++){
		if (S[i] == 1){
            update(T[i] - 1, U[i]);
			bit.add(T[i] - 1, (Int)U[i] - C[T[i] - 1]);
			C[T[i] - 1] = U[i];
		}
        else if (S[i] == 2){
            if (K == 1) continue;
            else divide(T[i] - 1, U[i] - 1);
        }
		else {
			printf("%lld\n", bit.sum(U[i] - 1) - bit.sum(T[i] - 2));
		}
	}

	return (0);
}

実装も遥かに軽い...