自动搬运

查看原文

来自洛谷，原作者为

	c_y_y 星辰诞于瞬间

搬运于2025-08-24 23:08:09，当前版本为作者最后更新于2025-01-25 21:36:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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] << " ";
}