seating - jan 2013 gold

#include <bits/stdc++.h>
using namespace std;

const int N = 500500;
const int N2 = 1<<20;

const int NOLAZY = 0;
const int EMPTY = 1;
const int FULL = 2;
const int MIXED = 3;

const int DYNAMIC = 0;
const int PREFIX = 1;
const int SUFFIX = 2;

struct Node {
    int mx, pre, suf, status, lazy;
    Node() {}
    inline void push(Node &l, Node &r, int tl, int tr) {
        int tm = (tl + tr) / 2;
        if (lazy == EMPTY) {
            l.mx = l.pre = l.suf = tm-tl+1;
            r.mx = r.pre = r.suf = tr-tm;
        } else if (lazy == FULL) {
            l.mx = l.pre = l.suf = 0;
            r.mx = r.pre = r.suf = 0;
        }
        l.status = l.lazy = lazy;
        r.status = r.lazy = lazy;
        lazy = NOLAZY;
    }
    inline void pull(Node &l, Node &r) {
        if (l.status == EMPTY && r.status == EMPTY) {
            status = EMPTY;
            mx = pre = suf = l.mx + r.mx;
        } else if (l.status == FULL && r.status == FULL) {
            status = FULL;
            mx = pre = suf = 0;
        } else {
            status = MIXED;
            pre = l.pre;
            suf = r.suf;
            mx = 0;
            if (l.mx > mx) {
                mx = l.mx;
            }
            if (r.mx > mx) {
                mx = r.mx;
            }
            if (l.suf + r.pre > mx) {
                mx = l.suf + r.pre;
            }
        }
    }
};

Node tree[N2];

void build(int v, int tl, int tr) {
    tree[v].lazy = NOLAZY;
    if (tl == tr) {
        tree[v].mx = tree[v].pre = tree[v].suf = 1;
        tree[v].status = EMPTY;
    } else {
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        tree[v].pull(tree[2*v], tree[2*v+1]);
    }
}

pair<int, int> findrange(int v, int tl, int tr, int p, int status) {
    if (tree[v].mx < p) {
        return make_pair(-1, -1);
    }
    if (tl == tr) {
        // leaf
        return make_pair(tl, tl);
    }
    if (tr-tl+1 == p) {
        // perfect fit
        return make_pair(tl, tr);
    }
    // must either go down or split
    int tm = (tl + tr) / 2;
    tree[v].push(tree[2*v], tree[2*v+1], tl, tr);
    if (status == DYNAMIC) {
        if (tree[2*v].mx >= p) {
            // completely in left child
            return findrange(2*v, tl, tm, p, DYNAMIC);
        } else if (tree[2*v+1].mx >= p) {
            // completely in right child
            return findrange(2*v+1, tm+1, tr, p, DYNAMIC);
        } else {
            // mx = l.suf + r.pre >= p
            // using suffix of left, prefix of right
            int l = findrange(2*v, tl, tm, tree[2*v].suf, SUFFIX).first;
            int r = findrange(2*v+1, tm+1, tr, p-tree[2*v].suf, PREFIX).second;
            return make_pair(l, r);
        }
    } else if (status == PREFIX) {
        if (tree[2*v].pre >= p) {
            // completely in left
            return findrange(2*v, tl, tm, p, PREFIX);
        } else {
            // using whole left, prefix of right
            // l.mx == l.pre
            return findrange(2*v+1, tm+1, tr, p-tree[2*v].mx, PREFIX);
        }
    } else if (status == SUFFIX) {
        if (tree[2*v+1].suf >= p) {
            // completely in right
            return findrange(2*v+1, tm+1, tr, p, SUFFIX);
        } else {
            // using prefix of left, whole right
            // r.mx == r.suf
            return findrange(2*v, tl, tm, p-tree[2*v+1].mx, SUFFIX);
        }
    } else {
        //cout << "Error.\n";
        return make_pair(-1, -1);
    }
}

void update(int v, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (l == tl && tr == r) {
        if (val == 0) {
            // leaving
            tree[v].mx = tree[v].pre = tree[v].suf = tr-tl+1;
            tree[v].status = tree[v].lazy = EMPTY;
        } else {
            // arriving
            tree[v].mx = tree[v].pre = tree[v].suf = 0;
            tree[v].status = tree[v].lazy = FULL;
        }
        return;
    }
    tree[v].push(tree[2*v], tree[2*v+1], tl, tr);
    int tm = (tl + tr) / 2;
    update(2*v, tl, tm, l, min(r, tm), val);
    update(2*v+1, tm+1, tr, max(l, tm+1), r, val);
    tree[v].pull(tree[2*v], tree[2*v+1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef _DEBUG
    freopen("seating.in", "r", stdin);
    freopen("seating.out", "w", stdout);
    #endif
    int n, m;
    cin >> n >> m;
    int ans = 0;
    build(1, 1, n);
    while (m--) {
        char ch;
        cin >> ch;
        if (ch == 'A') {
            int p, l, r;
            cin >> p;
            tie(l, r) = findrange(1, 1, n, p, DYNAMIC);
            if (l == -1 || r == -1) {
                ans += 1;
            } else {
                update(1, 1, n, l, r, 1);
            }
        } else {
            int l, r;
            cin >> l >> r;
            update(1, 1, n, l, r, 0);
        }
    }
    cout << ans << '\n';
}