G - Perm Query Japan Alumni Group Summer Camp 2013 Day 2

G - Perm Query

問題文より、全ては周期40以下の巡回群である。
あるli~riが揃うまでにはそれらの周期の最小公倍数回だけ操作が必要である。
区間の最小公倍数はセグ木で持てる。
また、操作の和も調べられるので持てる。

Submission #3879423 - Japan Alumni Group Summer Camp 2013 Day 2

struct Monoid {
    int i;
    mint v;
    Monoid(int i, mint v) : i(i), v(v) {}
};
struct SegmentTree {
    int n;
    vector<Monoid> seg;
    const Monoid e;
    //shu wa
    Monoid f(Monoid a, Monoid b) {
        int shu = lcm(a.i, b.i);
        mint sum = shu / a.i * a.v;
        sum += shu / b.i * b.v;
        return Monoid(shu, sum);
    }
    void update(int k, int shu, int v) {
        seg[k + n - 1] = Monoid(shu, v);
        k += n - 1;
        while (k) {
            k = (k - 1) / 2;
            seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]);
        }
    }
    SegmentTree(int len, const Monoid e) : e(e) {
        n = 1;
        while (n < len)n *= 2;
        seg.assign(2 * n - 1, e);
    }
    SegmentTree(vi dat, const Monoid e) : e(e) {
        n = 1;
        int asz = dat.size();
        while (n < asz)n *= 2;
        seg.assign(2 * n - 1, e);
        rep(i, asz) seg[i + n - 1] = Monoid(i, dat[i]);
        rer(i, n - 2)seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2]);
    }
    Monoid query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r == -1)r = n;
        if (r <= a || b <= l)return e;
        else if (a <= l && r <= b)return seg[k];
        else {
            Monoid sl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            Monoid sr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return f(sl, sr);
        }
    }

    int geti(int a, int b) {
        return query(a, b).i;
    }
    ll getv(int a, int b) {
        return query(a, b).v;
    }
    Monoid operator[](int k) const {
        return seg[k + n];
    }
};
int N, K, M, H, W, X, Y, q, Q, r;
vi A, B, C, p;
signed main() {
    cin >> N >> Q;
    addAll(p, N);
    A = B = p;
    setMod();
    //                        周期 和
    SegmentTree st(N + 1, Monoid(1, 0));
    vi shu(N, INF);
    vm sum(N);
    rep(i, 42) {
        rep(j, N) {
            if (shu[j] == INF)sum[j] += A[j];
            if (A[j] == j + 1)chmin(shu[j], i + 1);
            B[j] = p[A[j] - 1];
        }
        A = B;
    }
    rep(i, N) {
        st.update(i, shu[i], sum[i]);
    }
    while (Q--) {
        int a, b;
        cin >> a >> b;
        cout << st.getv(a - 1, b) << endl;
    }
    return 0;
}