推性质 + 很多个DS：ICPC2025西安A

Azalea Garden - Problem - QOJ.ac

我们考虑 $a$ 最大的那个人 $i$ ，显然除了它自己本身，所有 $b_j\le a_i$ 一定可以被杀死，所有 $b_j>a_i$ 一定杀不死

因此问题就剩下一个，它自己能不能被杀死？

$b_i>a_i$ 显然不能

接下来，我们考虑所有 $b_j>a_i$ 的生物，它们显然最后会一直存活。考虑它们当中 $a$ 的最大值 $A$

如果 $A\ge b_i$ ，那生物 $i$ 确实可以被杀死

有没有其他可能呢？

在上面的情况中，我们也是可以杀死的。

上面这种情况的本质是什么？

所有 $(b_j,a_j]$ 区间（除 $i$ 本身外）的交集覆盖 $(A,bi]$

我们需要维护4个数据结构：

set：用于求最大的 $a_i$
一个树状数组：用于求有多少个 $b_j\le a_i$
一棵线段树：用于求 $A$ ，支持单点修改和区间查询。但每个叶子节点要拿一个set来维护
一棵线段树：用于求区间覆盖，支持区间加减和区间最小值查询

#include<bits/stdc++.h>
#include<cassert>
using namespace std;bool Mbe;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 400010
int n, m, i, j, k, T;
int a[N], b[N], Qa[N], Qb[N], Qx[N], q; 
vector<int>E; 
struct node {
	int x, i; 
	bool operator < (const node A) const {
		if(x == A.x) {
			if(b[i] == b[A.i]) return i < A.i; 
			return b[i] < b[A.i]; 
		}
		return x < A.x; 
	}
};
multiset<node>S; 

struct Binary_tree {
	int cnt[N << 2]; 
	void add(int x, int y) {
		while(x < m) {
			cnt[x] += y; 
			x += x & -x; 
		}
	}
	int qry(int x) {
		int ans = 0; 
		while(x) {
			ans += cnt[x]; 
			x -= x & -x; 
		}
		return ans; 
	}
}Bin;

struct Segment_tree2 {
	int ls[N << 4], rs[N << 4], mn[N << 4], tot; 
	multiset<int>s[N << 2]; 
	void push_up(int k) {
		mn[k] = max(mn[ls[k]], mn[rs[k]]); 
	}
	void build(int &k, int l, int r) {
		if(!k) k = ++tot; 
		if(l == r) {
			mn[k] = 0; return ; 
		}
		int mid = (l + r) >> 1; 
		build(ls[k], l, mid); 
		build(rs[k], mid + 1, r); 
		push_up(k); 
	}
	void modify(int k, int l, int r, int x, int y) {
		if(l == r) {
			if(y < 0) {
				y = -y; 
				auto it = s[l].find(y); assert(it != s[l].end()); 
				s[l].erase(it); 
			}
			else s[l].insert(y); 
			if(s[l].empty()) mn[k] = 0; 
			else {
				auto it = s[l].end(); --it; mn[k] = *it; 
			}
			return ; 
		}
		int mid = (l + r) >> 1; 
		if(x <= mid) modify(ls[k], l, mid, x, y); 
		else modify(rs[k], mid + 1, r, x, y); 
		push_up(k); 
	}
	int qry(int k, int l, int r, int x, int y) {
		if(l >= x && r <= y) return mn[k]; 
		int mid = (l + r) >> 1, m1 = 0, m2 = 0; 
		if(x <= mid) m1 = qry(ls[k], l, mid, x, y); 
		if(y >= mid + 1) m2 = qry(rs[k], mid + 1, r, x, y); 
		return max(m1, m2); 
	}
}Seg2;

struct Segment_tree3 {
	int ls[N << 4], rs[N << 4], mn[N << 4], tag[N << 4], tot; 
	void push_down(int k) {
		tag[ls[k]] += tag[k]; mn[ls[k]] += tag[k]; 
		tag[rs[k]] += tag[k]; mn[rs[k]] += tag[k]; 
		tag[k] = 0; 
	}
	void push_up(int k) {
		mn[k] = min(mn[ls[k]], mn[rs[k]]); 
	}
	void build(int &k, int l, int r) {
		if(!k) k = ++tot; 
		if(l == r) {
			mn[k] = 0; return ; 
		}
		int mid = (l + r) >> 1; 
		build(ls[k], l, mid); 
		build(rs[k], mid + 1, r); 
		push_up(k); 
	}
	void modify(int k, int l, int r, int x, int y, int z) {
		if(l >= x && r <= y) {
//			debug("Add[%d %d] + %d\n", l, r, z); 
			tag[k] += z; mn[k] += z; 
			return ; 
		}
		push_down(k); 
		int mid = (l + r) >> 1; 
		if(x <= mid) modify(ls[k], l, mid, x, y, z); 
		if(y >= mid + 1) modify(rs[k], mid + 1, r, x, y, z); 
		push_up(k); 
//		debug("Min of [%d %d] is %d (%d %d)\n", l, r, mn[k], mn[ls[k]], mn[rs[k]]); 
	}
	int qry(int k, int l, int r, int x, int y) {
		if(l >= x && r <= y) return mn[k]; 
		int mid = (l + r) >> 1, m1 = m + 1, m2 = m + 2; 
		push_down(k); 
		if(x <= mid) m1 = qry(ls[k], l, mid, x, y); 
		if(y >= mid + 1) m2 = qry(rs[k], mid + 1, r, x, y); 
		push_up(k); 
//		debug("mn of [%d %d (%d)][%d %d] is %d\n", l, r, mn[k], x, y, min(m1, m2)); 
		return min(m1, m2); 
	}
}Seg3;

void Calc() {
	int x, A, c, i; 
	assert(S.begin() != S.end()); 
	auto it = S.end(); --it; i = (it -> i); 
	x = Bin.qry(a[i]); 
	if(a[i] < b[i]) { printf("%d\n", n - x); return ; }
	A = Seg2.qry(1, 1, m, a[i] + 1, m); 
	debug("[%d %d] %d (%d)\n", a[i], b[i], x, A); 
	if(A > a[i]) { printf("%d\n", n - (x - 1)); return ; }
	if(A >= b[i]) { printf("%d\n", n - x); return ; }
	if(a[i] >= b[i] + 1) Seg3.modify(1, 1, m, b[i] + 1, a[i], -1); 
	c = Seg3.qry(1, 1, m, A + 1, b[i]); 
//	debug("mn of [%d %d] is %d\n", A + 1, b[i], c); 
	if(a[i] >= b[i] + 1) Seg3.modify(1, 1, m, b[i] + 1, a[i], 1); 
	if(c >= 1) { printf("%d\n", n - x); return ; }
	printf("%d\n", n - (x - 1)); 
}

bool Med;
signed main() {
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
//	  freopen("out.txt", "w", stdout); 
	  atexit([]{fprintf(stderr,"%.lfms\n%lfMB\n",clock()*1000./CLOCKS_PER_SEC,(&Mbe-&Med)/1024./1024);});
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); q = read(); 
	E.pb(1e9 + 1); E.pb(0); 
	for(i = 1; i <= n; ++i) {
		a[i] = read(); b[i] = read(); 
		E.pb(a[i]); E.pb(b[i]); 
	}
	for(i = 1; i <= q; ++i) {
		Qx[i] = read(); Qa[i] = read(); Qb[i] = read(); 
		E.pb(Qa[i]); E.pb(Qb[i]); 
	}
	sort(E.begin(), E.end()); 
	E.erase(unique(E.begin(), E.end()), E.end()); m = E.size(); 
	int rt = 0; Seg2.build(rt, 1, m); rt = 0; Seg3.build(rt, 1, m); 
	auto get = [&] (int x) -> int {
		return lower_bound(E.begin(), E.end(), x) - E.begin() + 1; 
	}; 
	auto add = [&] (int i) -> void {
		S.insert({a[i], i}); 
		Bin.add(b[i], 1); 
		Seg2.modify(1, 1, m, b[i], a[i]); 
		if(a[i] >= b[i] + 1) Seg3.modify(1, 1, m, b[i] + 1, a[i], 1); //, debug("Add[%d %d]\n", b[i] + 1, a[i]); 
	}; 
	for(i = 1; i <= n; ++i) {
		a[i] = get(a[i]); b[i] = get(b[i]); add(i); 	
		debug("%d %d\n", a[i], b[i]); 
	}
	Calc(); 
	for(i = 1; i <= q; ++i) {
		j = Qx[i]; 
		debug("Try to find (%d %d)\n", a[j], j); 
		for(auto t : S) debug("(%d %d) ", t.x, t.i); debug("\n"); 
		auto it = S.find({a[j], j}); 
		//assert(it != S.end()); 
		S.erase(it); 
		Bin.add(b[j], -1); 
		Seg2.modify(1, 1, m, b[j], -a[j]); 
		if(a[j] >= b[j] + 1) Seg3.modify(1, 1, m, b[j] + 1, a[j], -1); 
		a[j] = get(Qa[i]); b[j] = get(Qb[i]); add(j); 
		debug("%d : [%d %d]\n", j, a[j], b[j]); 
		Calc(); 
	}
	return 0;
}