WA求调
查看原帖
WA求调
683212
Henly_Z楼主2024/7/23 16:10
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1000005;
using i64 = long long;

const int maxn = 1000010;
int cnt;
struct Node{
	int l , r , y , kur;
}query1[N];
struct Node1{
	int x , y1,y2;
	int kur;
}query2[N];
bool cmp(Node a , Node b){
	if(a.y == b.y){
		return a.kur > b.kur;
	}
	return a.y < b.y;
}
bool cmp1(Node1 a , Node1 b){
	if(a.x == b.x){
		return a.kur > b.kur;
	}
	return a.x < b.x;
}
struct S {
	// data
	int mx, len ;
	// lazy
	int lazyd;
	void reset() {
		lazyd = 0;
	}
} segt[maxn * 4];
S merge(const S& s1, const S& s2) {
	S s;
	s.reset();
	s.mx = min(s1.mx, s2.mx);
	s.len = 0;
	if(s.mx == s1.mx){
		s.len += s1.len;
	}
	if(s.mx == s2.mx){
		s.len += s2.len;
	}
	return s;
}
void apply(S& s, const S& tag) {
	s.lazyd += tag.lazyd;
	s.mx += tag.lazyd;
	
}

int n, a[maxn]; // in
void build(int idx, int L, int R) {
	segt[idx].lazyd = 0;
	if (L == R) {
		segt[idx].len = 1;
		segt[idx].mx = 0;
		return;
	}
	int M = (L+R) / 2;
	build(idx*2, L, M);
	build(idx*2+1, M+1, R);
	segt[idx] = merge(segt[idx*2], segt[idx*2+1]);
}
int ql, qr;
S query(int idx, int L, int R) {
	if (ql <= L && R <= qr) {
		return segt[idx];
	}
	int M = (L+R) / 2;
	apply(segt[idx*2], segt[idx]);
	apply(segt[idx*2+1], segt[idx]);
	segt[idx].reset();

	if (qr <= M) return query(idx*2, L, M);
	if (ql > M) return query(idx*2+1, M+1, R);
	return merge(query(idx*2, L, M), query(idx*2+1, M+1, R));
}
void update(int idx, int L, int R, const S& tag) {
	if (ql <= L && R <= qr) {
		apply(segt[idx], tag);
		return;
	}
	int M = (L+R) / 2;
	apply(segt[idx*2], segt[idx]);
	apply(segt[idx*2+1], segt[idx]);
	segt[idx].reset();

	if (ql <= M)
		update(idx*2, L, M,tag);
	if (qr > M)
		update(idx*2+1, M+1, R, tag);
	segt[idx] = merge(segt[idx*2], segt[idx*2+1]);
}
int main() {
	cin >> n;
	for(int i = 1 ; i <= n ; i++) {
		int x1 , x2 , y1 , y2;
		cin >> x1 >> y1 >> x2 >> y2;
		query1[2 * (i - 1) + 1].l = x1 + 10001, query1[2 * (i - 1) + 1].r = x2 + 10000, query1[2*(i - 1) + 1].y = y1,query1[2*(i - 1) + 1].kur = 1;
		query1[2 * i].l = x1 + 10001, query1[2 * i].r = x2 + 10000, query1[2*i].y = y2;
	}
	int ans = 0;
	build(1,1,20000);
	int lastx = 0 ; 
	int lasty = 0;
	sort(query1 + 1 , query1 + 2 * n + 1 , cmp);
	for(int i = 1 ; i <= 2 * n ; i++) {
		if(query1[i].kur == 1) {
			ql = query1[i].l , qr = query1[i].r;
//			cout << ql << " " << qr << endl;
			S nn = query(1,1,20000);
			int fir = 0;
			if(nn.mx == 0) fir = nn.len;
			S tag;
			tag.lazyd = 1;
			update(1,1,20000,tag);
			nn = query(1,1,20000);
			int sec = 0;
			if(nn.mx == 0) sec = nn.len;
			ans += min(lastx,abs(fir - sec)) * abs(query1[i].y - lasty);
			lastx = abs(fir - sec);
			lasty = query1[i].y;
//			cout << ans << endl;
		} 
		else{
			ql = query1[i].l , qr = query1[i].r;
			S nn = query(1,1,20000);
			int fir = 0;
			if(nn.mx == 0)fir = nn.len;
			S tag;
			tag.lazyd = -1;
			update(1,1,20000,tag);
			nn = query(1,1,20000);
			int sec = 0;
			if(nn.mx == 0)sec = nn.len;
//			cout << lastx << " " << abs(fir - sec) << " " << query1[i].y << " " << lasty << endl;
			ans += min(lastx,abs(fir - sec)) * abs(query1[i].y - lasty);
			lastx = abs(fir - sec);
			lasty = query1[i].y;
//			cout << ans << endl;
		}
	}
	
	cout << ans;
}
2024/7/23 16:10
加载中...