虽然我知道可能没人错这种错误但是发下吧还是
查看原帖
虽然我知道可能没人错这种错误但是发下吧还是
758820
Porridge_Dust楼主2024/3/11 11:53

改之前:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 100;

typedef long long ll;

int n, len;
struct node {int x1, x2, y, vis;} seg[N << 1];
int sum[N << 4], lazy[N << 4], b[N << 1];
ll ans;

int id (int x) {return lower_bound (b + 1, b + len + 1, x) - b;}

bool cmp (const node &x, const node &y) {return x.y < y.y;}

inline int ls (int p) {return p >> 1;}
inline int rs (int p) {return p >> 1 | 1;}

void push_up (int p, int l, int r) {
	if (lazy[p] > 0) sum[p] = b[r + 1] - b[l];
	else sum[p] = sum[ls(p)] + sum[rs(p)];
}

void update (int p, int l, int r, int nl, int nr, int f) {
	if (nl <= l && r <= nr) {
		lazy[p] += f;
		push_up(p, l, r);
		return ;
	}
	int mid = l + r >> 1;
	if (nl <= mid) update (ls(p), l, mid, nl, nr, f);
	if (mid < nr) update (rs(p), mid + 1, r, nl, nr, f);
	push_up(p, l, r);
}

void dfs (int p) {
	if (p > 6) return ;
	cout << p << " " <<sum[p] << " " << lazy[p] << '\n';
	dfs(ls(p)), dfs(rs(p));
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1, X1, Y1, X2, Y2; i <= n; i ++ ) {
		cin >> X1 >> Y1 >> X2 >> Y2;
		seg[i * 2 - 1] = {X1, X2, Y1, 1};
		seg[i * 2] = {X1, X2, Y2, -1};
		b[i * 2 - 1] = X1, b[i * 2] = X2;
	}
	
	sort (b + 1, b + n * 2 + 1);
	sort (seg + 1, seg + n * 2 + 1, cmp);
	len = unique(b + 1, b + n * 2 + 1) - b - 1;
		
	for (int i = 1; i < 2 * n; i ++ ) {
		update (1, 1, len - 1, id(seg[i].x1), id(seg[i].x2) - 1, seg[i].vis);
		ans += sum[1] * 1ll * (seg[i + 1].y - seg[i].y);	
	}
	
	cout << ans << '\n';
	
	return 0;
}

改之后:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 100;

typedef long long ll;

int n, len;
struct node {int x1, x2, y, vis;} seg[N << 1];
int sum[N << 4], lazy[N << 4], b[N << 1];
ll ans;

int id (int x) {return lower_bound (b + 1, b + len + 1, x) - b;}

bool cmp (const node &x, const node &y) {return x.y < y.y;}

inline int ls (int p) {return p << 1;}
inline int rs (int p) {return p << 1 | 1;}

void push_up (int p, int l, int r) {
	if (lazy[p] > 0) sum[p] = b[r + 1] - b[l];
	else sum[p] = sum[ls(p)] + sum[rs(p)];
}

void update (int p, int l, int r, int nl, int nr, int f) {
	if (nl <= l && r <= nr) {
		lazy[p] += f;
		push_up(p, l, r);
		return ;
	}
	int mid = l + r >> 1;
	if (nl <= mid) update (ls(p), l, mid, nl, nr, f);
	if (mid < nr) update (rs(p), mid + 1, r, nl, nr, f);
	push_up(p, l, r);
}

void dfs (int p) {
	if (p > 6) return ;
	cout << p << " " <<sum[p] << " " << lazy[p] << '\n';
	dfs(ls(p)), dfs(rs(p));
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1, X1, Y1, X2, Y2; i <= n; i ++ ) {
		cin >> X1 >> Y1 >> X2 >> Y2;
		seg[i * 2 - 1] = {X1, X2, Y1, 1};
		seg[i * 2] = {X1, X2, Y2, -1};
		b[i * 2 - 1] = X1, b[i * 2] = X2;
	}
	
	sort (b + 1, b + n * 2 + 1);
	sort (seg + 1, seg + n * 2 + 1, cmp);
	len = unique(b + 1, b + n * 2 + 1) - b - 1;
		
	for (int i = 1; i < 2 * n; i ++ ) {
		update (1, 1, len - 1, id(seg[i].x1), id(seg[i].x2) - 1, seg[i].vis);
		ans += sum[1] * 1ll * (seg[i + 1].y - seg[i].y);	
	}
	
	cout << ans << '\n';
	
	return 0;
}

没错,ls() 和 rs() 左移右移方向写错了(错过不止一次了已经)

大家一定要引以为戒(qwq)

2024/3/11 11:53
加载中...