AC on #1 #3

#include <bits/stdc++.h>
#define lid (id << 1)
#define rid (id << 1 | 1)
using namespace std;
using ll = long long;
constexpr int MAXN = 5e6 + 1145;
constexpr int root = 1;

struct Node {
    int len, tag, lmax, rmax, sum;
} t[MAXN];

int a, b, p;

namespace sgt {
	void merge(int id) {
	    t[id].lmax = (t[lid].lmax == t[lid].len) ? (t[lid].len + t[rid].lmax) : t[lid].lmax;
	    t[id].rmax = (t[rid].rmax == t[rid].len) ? (t[rid].len + t[lid].rmax) : t[rid].rmax;
	    t[id].sum = max(t[lid].rmax + t[rid].lmax, max(t[lid].sum, t[rid].sum));
	}
	
	void build(int id, int l, int r) {
	    t[id].sum = t[id].len = t[id].lmax = t[id].rmax = r - l + 1;
	    if (l == r) return;
	    int mid = (l + r) >> 1;
	    build(lid, l, mid), build(rid, mid + 1, r);
	}
	
	void push_down(int id, int l, int r) {
	    if (t[id].tag == 0)
	        return;
	    int mid = l + r >> 1;
	    t[lid].tag = t[rid].tag = t[id].tag;
	    t[lid].sum = t[lid].lmax = t[lid].rmax = (t[id].tag == 1) ? t[lid].len : 0;
	    t[rid].sum = t[rid].rmax = t[rid].rmax = (t[id].tag == 1) ? t[rid].len : 0;
	}
	
	int qry(int x, int id, int cl, int cr) {
	    if (cl == cr)
	        return cl;
	    push_down(id, cl, cr);
	    int mid = cl + cr >> 1;
	    if (t[lid].sum >= x)
	        return qry(x, lid, cl, mid);
	    if (t[lid].rmax + t[rid].lmax >= x)
	        return mid - t[lid].rmax + 1;
	    return qry(x, rid, mid + 1, cr);
	}
	
	void modify(int l, int r, int x, int id, int cl, int cr) {
	    if (cl > r || cr < l)
	        return;
	    if (l <= cl && cr <= r) {
	        t[id].sum = t[id].lmax = t[id].rmax = (x == 1) ? t[id].len : 0;
	        t[id].tag = x;
	        return;
	    }
	    push_down(id, cl, cr);
	    int mid = cl + cr >> 1;
	    modify(l, r, x, lid, cl, mid);
	    modify(l, r, x, rid, mid + 1, cr);
	    merge(id);
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, ans = 0;
    char c;
    cin >> n >> m;
    sgt::build(root, 1, n);
    for (int i = 1; i <= m; i++) {
        cin >> c;
        if (c == 'L') {
            cin >> a >> b;
            sgt::modify(a, b, 1, root, 1, n);
        } else {
            cin >> p;
            if (t[root].sum >= p) {
                int ans_l = sgt::qry(p, root, 1, n);
                sgt::modify(ans_l, ans_l + p - 1, 2, root, 1, n);
            } else
                ans++;
        }
    }
    cout << ans;
    return 0;
}