Ile inwersji II (nietestowane)

#include <cstdio>
#include <algorithm>

const int MAXN = 5e5; // REMEMBER!!! change S below too!
char buff[MAXN+1];

typedef long long LL;
struct Node {
    int a, b;
    LL inv, rev_inv;
    bool is_reversed;

    Node() : a(0), b(0), inv(0), rev_inv(0), is_reversed(false) {}

    Node operator+(const Node& o) const {
        Node res;
        res.a = a + o.a;
        res.b = b + o.b;
        res.inv = inv + b * o.a + o.inv;
        res.rev_inv = rev_inv + a * o.b + o.rev_inv;
        return res;
    }

    Node& reverse_me() {
        std::swap(inv, rev_inv);
        std::swap(a, b);
        is_reversed = !is_reversed;
        return *this;
    }
};

const int S = 1<<19; // FOR MAXN=5e5 !!!!
struct Tree {
    Node v[2*S];

    Node query(int a, int b, bool reverse = false, int left = 0, int right = S-1, int me_ind = 1) {
        if(a<=left && b>=right) {
            if(reverse)
                v[me_ind].reverse_me();
            return v[me_ind];
        }

        // zepchnij aktualizacje na synow
        if(v[me_ind].is_reversed && me_ind < S) { // hm, drugi warunek zawsze prawdziwy...
            v[me_ind*2].reverse_me();
            v[me_ind*2+1].reverse_me();
        }


        Node left_son, right_son;
        // lewy syn
        if(a <= (left+right)/2)
            left_son = query(a, b, reverse, left, (left+right)/2, me_ind*2);
        // prawy syn
        if(b >= (left+right)/2+1)
            right_son = query(a, b, reverse, (left+right)/2+1, right, me_ind*2+1);

        v[me_ind] = v[me_ind*2] + v[me_ind*2+1];

        return left_son + right_son;
    }


    // helper init function !
    void build_tree(const char* buff) {
        for(int i=0; buff[i]; i++)
            if(buff[i]=='a')
                v[S+i+1].a++;
            else
                v[S+i+1].b++;

        int ind = S;
        while(--ind)
            v[ind] = v[ind*2] + v[ind*2+1];
    }
};


Tree t;
int main()
{
    int q,n;
    scanf("%i %i %s", &q, &n, buff);
    t.build_tree(buff);

    while(q--) {
        char c; int a,b;
        scanf("%c%c %i %i", &c, &c, &a, &b);

        if(c=='I')
            t.query(a,b,true);
        else
            printf("%lld\n", t.query(a,b).inv);
    }

    return 0;
}