萌新刚学线段树,求助 30pts 代码
查看原帖
萌新刚学线段树,求助 30pts 代码
486187
vvautedSN第一魔怔人楼主2021/11/1 21:06

RT。

#include <stdio.h>
#include <set>
#define Rep(i, l, r) for(i = l; i <= r; ++ i)
#define Nep(i, l, r) for(i = l; i != r; ++ i)
#define Maxn 1000005

struct sugment_tree {
	int sum[Maxn << 2];
	int lc(int x) { return x << 1; }
	int rc(int x) { return x << 1 | 1; }
	
	int ins(int x, int l, int r) {
		if(l == r) {
			sum[x] = 1;
			return l;
		}
		
		int mid = l + r >> 1; sum[x] ++;
		if(sum[lc(x)] < mid) return ins(lc(x), l, mid);
		return ins(rc(x), mid + 1, r);
	}
	
	void del(int x, int l, int r, int k) {
		if(l == r) {
			sum[x] = 0;
			return;
		}
		
		int mid = l + r >> 1; sum[x] --;
		if(k <= mid) del(lc(x), l, mid, k);
		else del(rc(x), mid + 1, r, k);
	}
}ta, tb; 

struct node {
	bool type; int id, time;
	
	friend bool operator < (node a, node b) {
		return a.time < b.time;
	}
};

std :: set <node> sa;
std :: set <node> sb;
int prea[Maxn], preb[Maxn], lta[Maxn], ltb[Maxn], ans; 
int max(int a, int b) { return a > b ? a : b; }

int main() {
	int n, m1, m2, i, l, r, t; std :: set <node> :: iterator it;
	scanf("%d%d%d", &n, &m1, &m2); int tot = m1 + m2 + 1000;
	Rep(i, 1, m1) scanf("%d%d", &l, &r), sa.insert({0, i, l}), sa.insert({1, i, r});
	Rep(i, 1, m2) scanf("%d%d", &l, &r), sb.insert({0, i, l}), sb.insert({1, i, r});
	Nep(it, sa.begin(), sa.end()) if(it->type) ta.del(1, 1, m1, lta[it->id]); else lta[it->id] = ta.ins(1, 1, m1), ++ prea[lta[it->id]];
	Nep(it, sb.begin(), sb.end()) if(it->type) tb.del(1, 1, m2, ltb[it->id]); else ltb[it->id] = tb.ins(1, 1, m2), ++ preb[ltb[it->id]];
	Rep(i, 2, n) prea[i] += prea[i - 1], preb[i] += preb[i - 1];
	Rep(i, 0, n) ans = max(ans, prea[i] + preb[n - i]);
	return printf("%d", ans), 0; 
}
2021/11/1 21:06
加载中...