P3071

fly_fire · 2025-03-14 19:01:45 · 个人记录

虽然有奇怪的标签，但是还是一眼辨认出了珂朵莉树十分适用。

仔细看一眼题，发现第一个操作使用珂朵莉树是可以减小复杂度的，第二个操作虽然不能减小复杂度，但是这个操作并不会很慢。并且这题不可能通过很少的 A 操作卡掉 odt，因为答案就是 A 操作的失败次数。

于是写一个很版的 odt 就过力。

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 5e5 + 5;

int n, m;

struct Node {
    int l, r;
    mutable int v;

    Node(int L, int R, int V) {l = L, r = R, v = V;}

    bool operator < (const Node & x) const {
        return l < x.l;
    }
};

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound(Node(x, 0, 0));
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, val = it -> v;
    if (r < x) return odt.end();
    odt.erase(it);
    odt.insert(Node(l, x - 1, val));
    return odt.insert(Node(x, r, val)).first; 
}

void Assign(int l, int r, int val) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(Node(l, r, val));
}

int len(auto x) {
    return x.r - x.l + 1;
}

int update(int x) {
    int tot = 0, cnt = 0, frm = -1;
    for (auto i : odt) {
        if (i.v == 0) {
            cnt += len(i);
            if (frm == -1) frm = i.l;
        }
        else cnt = 0, frm = -1;
        tot = max(tot, cnt);
        if (tot >= x) {
            Assign(frm, frm + x - 1, 1);
            return 0;
        }
    }
    return 1;
}

int main() {
    n = read(), m = read();

    odt.insert(Node(1, n, 0));

    int ans = 0;
    while (m--) {
        char ch;cin >> ch;
        int x = read(), y;
        if (ch == 'A') ans += update(x);
        else y = read(), Assign(x, y, 0); 
//      for (auto i : odt) {
//          cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
//      }
    }

    write(ans), putchar(10);
    return 0;
}