Segment Tree

/*-----------------Segment Tree---------------------*/
struct Segment_tree {
    int n, sz;
    ll t[maxn * 4], u[maxn * 4];
    int right(int i) {
        return (i << 1) + 1;
    }
    int left(int i) {
        return (i << 1);
    }
    void recalc(int x) {
        t[x] = t[left(x)] + t[right(x)];
    }
    void udown(int x) {
        t[x] += u[x];
        if (x <= sz) {
            u[left(x)] += u[x];
            u[right(x)] += u[x];
        }
        u[x] = 0;
    }
    void init(int _n) {
        n = _n;
        for(sz = 1; sz < n; sz <<= 1);
        --sz;
    }
    void upd(int ql, int qr, int delta, int x = 1, int tl = 1, int tr = -1) {
        if (tr == -1) tr = sz + 2;
        udown(x);
        if (tl >= qr || tr <= ql) return;
        if (ql <= tl && tr <= qr) {
            u[x] += delta;
            udown(x);
            return;
        }
        int mid = (tl + tr) / 2;
        upd(ql, qr, delta, left(x), tl, mid);
        upd(ql, qr, delta, right(x), mid, tr);
        recalc(x);
    }
    ll get(int ql, int qr, int x = 1, int tl = 1, int tr = -1) {
        if (tr == -1) tr = sz + 2;
        udown(x);
        if (tl >= qr || tr <= ql) return 0;
        if (ql <= tl && tr <= qr)
            return t[x];
        int mid = (tl + tr) / 2;
        ll ans = 0;
        ans += get(ql, qr, left(x), tl, mid);
        ans += get(ql, qr, right(x), mid, tr);
        return ans;
    }
} jinv_tree, minv_tree;

/*------End of Segment Tree----------*/

/*------Intersection Tree------------*/

struct Intersection_tree {
    int n, sz;
    node t[maxn * 4];
    int right(int i) {
        return (i << 1) + 1;
    }
    int left(int i) {
        return (i << 1);
    }
    void recalc(int x) {
        t[x].sum_b = t[left(x)].sum_b + t[right(x)].sum_b;
        t[x].num_b = t[left(x)].num_b + t[right(x)].num_b;
        if (t[left(x)].r_b && t[right(x)].l_b) --t[x].num_b;
        t[x].l_b = t[left(x)].l_b, t[x].r_b = t[right(x)].r_b;
    }
    void push(int x, int tl, int tr) {
        if (!t[x].upd) return;
        if (t[x].new_c == 0) {
            t[x].sum_b = tr - tl;
            t[x].num_b = 1;
            t[x].l_b = 1, t[x].r_b = 1;
        }
        else {
            t[x].sum_b = t[x].num_b = 0;
            t[x].l_b = 0, t[x].r_b = 0;
        }
        t[x].upd = 0;
        if (tl == tr - 1) return;
        t[left(x)].upd = 1;
        t[left(x)].new_c = t[x].new_c;
        t[right(x)].upd = 1;
        t[right(x)].new_c = t[x].new_c;
    }
    void init(int _n) {
        n = _n;
        for(sz = 1; sz < n; sz <<= 1);
        --sz;
    }
    void upd(int ql, int qr, char delta, int x = 1, int tl = 1, int tr = -1) {
        if (tr == -1)
            tr = sz + 2;
        push(x, tl, tr);
        if (tl >= qr || tr <= ql) return;
        if (ql <= tl && tr <= qr) {
            t[x].upd = 1;
            t[x].new_c = (delta == 'W');
            push(x, tl, tr);
            return;
        }
        int mid = (tl + tr) / 2;
        upd(ql, qr, delta, left(x), tl, mid);
        upd(ql, qr, delta, right(x), mid, tr);
        recalc(x);
    }
    pair <int, int> get() {
        return mp(t[1].num_b, t[1].sum_b);
    }
} tree;

/*------End of Intersection Tree----------*/