monede2 70p - recursiv

#include <bits/stdc++.h>

using namespace std;

ifstream fin("monede2.in");
ofstream fout("monede2.out");

class Raport {
  public:
    int a, b;
    Raport(int, int);
    Raport();

    Raport &operator+=(const Raport &);
    Raport &operator-=(const Raport &);
    Raport &operator*=(const Raport &);
    Raport &operator/=(const Raport &);

    bool operator==(const Raport &rhs) const;
    bool operator!=(const Raport &rhs) const;
};

Raport operator+(Raport, const Raport &);
Raport operator-(Raport, const Raport &);
Raport operator*(Raport, const Raport &);
Raport operator/(Raport, const Raport &);

Raport::Raport(int A, int B) : a(A), b(B) {}

Raport::Raport() : Raport(0, 1) {}

Raport &Raport::operator+=(const Raport &rhs) {
    a = ((long long)a * rhs.b + (long long)b * rhs.a) % 1000000007;
    b = ((long long)b * rhs.b) % 1000000007;
    return *this;
}

Raport &Raport::operator-=(const Raport &rhs) {
    a = ((long long)a * rhs.b - (long long)b * rhs.a) % 1000000007;
    if (a < 0)
        a += 1000000007;
    b = ((long long)b * rhs.b) % 1000000007;
    return *this;
}

Raport &Raport::operator*=(const Raport &rhs) {
    a = ((long long)a * rhs.a) % 1000000007;
    b = ((long long)b * rhs.b) % 1000000007;
    return *this;
}

Raport &Raport::operator/=(const Raport &rhs) {
    a = ((long long)a * rhs.b) % 1000000007;
    b = ((long long)b * rhs.a) % 1000000007;
    return *this;
}

bool Raport::operator==(const Raport &rhs) const {
    return ((long long)a * rhs.b - (long long)b * rhs.a) % 1000000007 == 0;
}

bool Raport::operator!=(const Raport &rhs) const { return !(*this == rhs); }

Raport operator+(Raport a, const Raport &b) { return a += b; }

Raport operator-(Raport a, const Raport &b) { return a -= b; }

Raport operator*(Raport a, const Raport &b) { return a *= b; }

Raport operator/(Raport a, const Raport &b) { return a /= b; }

class SegTree {
    public:
        int sz = 1;
        vector<Raport> Tree;

        void init(int N) {
            sz = 1;
            while(sz < N)
                sz <<= 1;
            Tree.resize((sz << 1) | 1);
        }

        Raport Merge(Raport a, Raport b) {
            return a * (Raport(1, 1) - b) + (Raport(1, 1) - a) * b;
        }

        void build(int x, int lx, int rx) {
            if(lx == rx) {
                int a, b;
                fin >> a >> b;
                Tree[x] = Raport(a, b);
                return;
            }
            int mid = (lx + rx) >> 1;
            build(x << 1, lx, mid);
            build((x << 1) | 1, mid + 1, rx);
            Tree[x] = Merge(Tree[x << 1], Tree[(x << 1) | 1]);
        }

        Raport query(int x, int lx, int rx, int st, int dr) {
            if(st <= lx && rx <= dr)
                return Tree[x];
            int mid = (lx + rx) >> 1;
            Raport ans1(0, 1), ans2(0, 1);
            if(st <= mid)
                ans1 = query(x << 1, lx, mid, st, dr);
            if(mid < dr)
                ans2 = query((x << 1) | 1, mid + 1, rx, st, dr);
            return Merge(ans1, ans2);
        }
};

int main() {
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    int N, Q;
    fin >> N >> Q;
    SegTree Tree;
    Tree.init(N);
    Tree.build(1, 1, N);
    while(Q--) {
        int st, dr;
        fin >> st >> dr;
        Raport R = Tree.query(1, 1, N, st, dr);
        fout << R.a << ' ' << R.b << '\n';
    }
}