题解：P11534 [NOISG 2023 Finals] Inspections

· · 题解

P11534 [NOISG 2023 Finals] Inspections

维护每个机器最后一次使用的时间，注意到每一次操作相当于将区间 [l_{i},r_{i}] 修改为一个公差为 +1 的等差数列。由于公差固定，因此只需维护首项便可知道该区间内所有数的值即可。

修改区间的值考虑 ODT。不断修改区间，维护首项。

最棘手的问题就是如何计算答案。

由于答案只要求修改次数，不难想到在修改操作中，每次不断暴力修改块时顺便计算答案，开个 vector 存放前后两次差值和区间长度。最后将询问离线，从大到小顺序求解，将原来的 vector 中的区间一个个丢到询问中判断是否合法（有点类似于单调栈），如果不合法就调到下一个询问。由于我们将询问变得有序，故所求答案是单调不降的。我们就很顺利地解决了这个问题。

#define LL long long
#define IT set<node>::iterator
inline long long read() {
    long long x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
const int N = 2e5 + 10; 
struct node {
    int l, r;
    mutable LL v;
    node(int L, int R = -1, LL V = 0):l(L), r(R), v(V) {}
    bool operator <(const node& b) const {
        return l < b.l;
    }
};
struct que {
    LL s;
    int id;
}a[N];
vector<pair<LL, LL> > d;
set<node>s;
IT split(int pos) {
    IT it = s.lower_bound(pos);
    if(it != s.end() && it->l == pos) return it;
    --it;
    int l = it->l, r = it->r;
    LL v = it->v;
    s.erase(it);
    s.insert(node(l, pos - 1, v));
    return s.insert(node(pos, r, v + pos - l)).first;
}
LL ans[N];
void assign(int l, int r, LL val) {
    IT itr = split(r + 1), itl = split(l);
    LL now = val;
    for (IT it = itl; it != itr; it++) {
        d.push_back(make_pair(now - it->v, it->r - it->l + 1));
        now += it->r - it->l + 1; 
    }
    s.erase(itl, itr);
    s.insert(node(l, r, val));
}
bool cmp(que x, que y) {
    return x.s > y.s;
}
void solve() {
    int n = read(), m = read(), q = read();
    s.insert(node(1ll, n, 1e18 + 10));
    LL now = 1;
    while(m--) {
        int l = read(), r = read();
        assign(l, r, now);
        now += (LL)r - l + 1;
    }
    for (int i = 1; i <= q; i++) {
        a[i].s = read(), a[i].id = i;
    }
    sort(a + 1, a + q + 1, cmp);
    sort(d.begin(), d.end());

    LL cnt = 0;
    for (int i = 1; i <= q; i++) {
        while(d.size() && d.back().first > a[i].s)
            cnt += d.back().second, d.pop_back();
        ans[a[i].id] = cnt;
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << " ";
}