SRM 424 div1 hard:ProductOfPrices

これは解きたかったかな〜

問題:TopCoder Statistics - Problem Statement

解法:0〜L-1の座標系に木を植えていくことになる。そこで,以下のような変数を用意する。
cnt[i]:座標iに植えられている木の数
dst[i]:dst[i] = cnt[i] * i
座標xに木を植えることを考える。これにかかるpriceは,
(座標x未満に植えられている木の数)*x - (座標x未満に植えられている木の座標の合計)
+ (座標がxより大きい木の座標の合計) - (座標がxより大きい木の植えられている数)*x
= sum(cnt, 0, x-1)*x - sum(dst, 0, x-1) + sum(dst, x+1, L) - sum(cnt, x+1, L)*x
となる。これをBITで処理すれば良い。

// 0-based Binary Indexed Tree
constexpr int mod = 1e9+7;
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s += bit[i]) %= mod;
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] += x) %= mod;
            i += i&-i;
        }
    }
    // [a, b)
    T sum(int a, int b) {
        return sum(b)-sum(a);
    }
    // sum(0, i) >= wとなる最小のiを求める 存在しなければmaxを返す
    int lb(T w) {
        if (w <= 0) return 0;
        int k = 1;
        while (k <= max) k <<= 1;
        int i = 0;
        for (; k > 0; k >>= 1) if (i+k <= max && bit[i+k] < w) {
            w -= bit[i+k];
            i += k;
        }
        return i+1;
    }
};

class ProductOfPrices {
public:
    int product(int N, int L, int X0, int A, int B) {
        BIT<ll>* cnt = new BIT<ll>(L);
        BIT<ll>* dst = new BIT<ll>(L);
        vector<int> X(N);
        X[0] = X0 % L;
        for (int i = 1; i < N; i++) {
            X[i] = ((ll)X[i-1] * A % L + B) % L;
        }
        ll ret = 1;
        cnt->add(X[0], 1);
        dst->add(X[0], X[0]);
        for (int i = 1; i < N; i++) {
            ll tmp = 0;
            tmp += (cnt->sum(0, X[i])) * X[i];
            tmp += mod - (dst->sum(0, X[i]));
            tmp %= mod;
            tmp += (dst->sum(X[i]+1, L));
            tmp += mod-(cnt->sum(X[i]+1, L)) * X[i];
            tmp %= mod;
            if (tmp < 0) tmp += mod;
            (ret *= tmp) %= mod;
            cnt->add(X[i], 1);
            dst->add(X[i], X[i]);
        }
        return (int)(ret%mod);
    }
};