求救 RE#4
查看原帖
求救 RE#4
532450
xiyuanli楼主2024/3/31 22:16
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson root<<1
#define rson (root<<1)|1
#define mid (l+r)/2
#define maxn 200005
using namespace std;

int s[maxn];

struct node1 {
	int num; // 几条不相交的线段覆盖
	int sum; // 被完整覆盖了几次
	int len; // 覆盖长度
    int l, r;
    bool lc, rc;// 标记左右端点是否被覆盖
} tree[maxn];

struct node2 {
    int y, x1, x2;
    int flag;
} p[maxn];

bool cmp(node2 a, node2 b) {
    return a.y < b.y || (a.y == b.y && a.flag > b.flag);
}

void pushup(int root) {
    if (tree[root].sum) { // 当前区间被完全覆盖
        tree[root].len = tree[root].r - tree[root].l;
        tree[root].lc = tree[root].rc = 1;
        tree[root].num = 1;
    } else { // 没有完全覆盖
    	tree[root].len = tree[lson].len + tree[rson].len;
    	tree[root].num = tree[lson].num + tree[rson].num;
    	if (tree[lson].rc && tree[rson].lc) tree[root].num--; // 左右区间线段相交
    	tree[root].lc = tree[lson].lc;
    	tree[root].rc = tree[rson].rc;
    }
}

void build(int root, int l, int r) {
    if (r - l > 1) {
        tree[root].l = s[l];
        tree[root].r = s[r];
        build(lson, l, mid);
        build(rson, mid, r);
        pushup(root);
    } else {
        tree[root].l = s[l];
        tree[root].r = s[r];
        tree[root].len = 0;
        tree[root].sum = 0;
        tree[root].num = 0;
        tree[root].lc = 0;
        tree[root].rc = 0;
    }
}

void update(int root, int x1, int x2, int flag) {
    if (tree[root].l == x1 && tree[root].r == x2) {
        tree[root].sum += flag;
        pushup(root);
    } else {
        if (tree[lson].r > x1) update(lson, x1, min(tree[lson].r, x2), flag);
        if (tree[rson].l < x2) update(rson, max(tree[rson].l, x1), x2, flag);
        pushup(root);
    }
}

int main() {
  int n;
  int x1, y1, x2, y2, ans;
  cin >> n;
  ans = 0;
  for (int i = 0; i < n; i++) {
    cin >> x1 >> y1 >> x2 >> y2;
    p[i].y = y1;
    p[i].x1 = x1;
    p[i].x2 = x2;
    p[i].flag = 1;
    p[i + n].y = y2; 
    p[i + n].x1 = x1;
    p[i + n].x2 = x2;
    p[i + n].flag = -1;
    s[i + 1] = x1;
    s[i + n + 1] = x2;
  }
  sort(s + 1, s + (2 * n + 1)); 
  sort(p, p + 2 * n, cmp);  // 把矩形的边的横坐标从小到大排序
  build(1, 1, 2 * n);       // 建树
  int tlen = tree[1].len;
  update(1, p[0].x1, p[0].x2, p[0].flag);
  
  for (int i = 1; i < 2 * n; i++) {
  	// cout << i << ":" << ans + tlen<< "." << p[i].y - p[i-1].y << "," << tree[1].num <<endl;
  	cout << i << ":" << tree[1].num << ":" << tree[1].len << " all:" << (p[i].y - p[i-1].y) << " ans:" << ans <<endl;

    ans += (p[i].y - p[i - 1].y) * 2 * tree[1].num + abs(tree[1].len - tlen);

    tlen = tree[1].len;
    update(1, p[i].x1, p[i].x2, p[i].flag);
  }
  cout << ans + abs(tree[1].len - tlen)<< endl;
  return 0;
}
2024/3/31 22:16
加载中...