求助ODT
查看原帖
求助ODT
332914
happybob楼主2022/6/5 13:31
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

int n, q;

struct Node
{
    int l, r;
    mutable int v;
    bool operator<(const Node& g) const
    {
        return l < g.l;
    }
    Node(int _l, int _r, int _v) : l(_l), r(_r), v(_v) {}
};

set<Node> odt;

auto split(int x)
{
    if (x > n) return odt.end();
    auto it = --odt.upper_bound(Node(x, 0, 0));
    if (it->l == x) return it;
    int l = it->l, r = it->r;
    int v = it->v;
    odt.erase(it);
    odt.insert(Node(l, x - 1, v));
    return odt.insert(Node(x, r, v)).first;
}
void assign(int l, int r, int v)
{
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(Node(l, r, v));
}
int query(int l, int r)
{
    int res = 0;
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; ++itl) res += itl->v * (itl->r - itl->l + 1);
    return res;
}

int main()
{
    scanf("%d%d", &n, &q);
    assign(1, n, 1);
    while (q--)
    {
        int op, l, r;
        scanf("%d%d%d", &l, &r, &op);
        if (op == 1) assign(l, r, 0);
        else assign(l, r, 1);
        printf("%d\n", query(1, n));
    }
    return 0;
}

rt,洛谷IDE,RE了

2022/6/5 13:31
加载中...