练习扫描线,莫名错误
查看原帖
练习扫描线,莫名错误
113932
lxg_honoka楼主2020/9/15 00:47
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

#define mid ((l+r) >> 1)
#define lson (o >> 1)
#define rson (o >> 1 | 1)

const int maxn = 5000 + 10;
int y[maxn];
int n;

struct scanline
{
    int l, r, x;
    int val;
    bool operator < (const scanline &k) const
    {
        return x < k.x;
    }
}line[maxn << 1];

struct segtree
{
    int l, r;
    int sum, len;
}tree[maxn << 3];

struct node
{
    int x, y;
}ans[maxn];

void build (int l, int r, int o)
{
    tree[o].l = l;
    tree[o].r = r;
    tree[o].sum = tree[o].len = 0;

    if (l == r) return;
    build(l, mid, lson);
    build(mid+1, r, rson);
}

void pushdown (int o)
{
    int l = tree[o].l, r = tree[o].r;

    if (tree[o].sum)
        tree[o].len = y[r+1] - y[l];
    else
        tree[o].len = tree[lson].len + tree[rson].len;
}

void updata (int ql, int qr, int o, int val)
{
    int l = tree[o].l, r = tree[o].r;

    if (y[r+1] <= ql || y[l] >= qr)
        return;

    if (ql <= y[l] && qr >= y[r+1])
    {
        tree[o].sum += val;
        pushdown(o);
        return;
    }

    updata(ql, qr, lson, val);
    updata(ql, qr, rson, val);
    pushdown(o);
}

int main ()
{
    int xx, yy, zz;
    int cnt;
    n = 0;
    while (cin >> xx >> yy >> zz)
    {
        n++;
        cin >> xx >> yy >> zz;
        y[(n<<1)-1] = 0, y[n<<1] = yy;
        line[(n<<1)-1] = (scanline){0, yy, xx, 1};
        line[n<<1] = (scanline){0, yy, zz, -1};
    }

    n <= 1;
    sort(line+1, line+n+1);
    sort(y+1, y+n+1);
    cnt = unique(y+1, y+n+1) - (y+1);
    build(1, cnt-1, 1);

    int num = 0, pre = 0;
    for (int i = 1; i <= n; i++)
    {
        updata(line[i].l, line[i].r, 1, line[i].val);
        cout << tree[1].len << endl;
        if (tree[1].len != pre)
        {
            ans[++num] = (node){line[i].x, pre};
            pre = tree[1].len;
            ans[++num] = (node){line[i].x, pre};
        }
    }

    for (int i = 1; i <= num; i++)
    {
        if (i & 1)
            printf("%d ", ans[i].x);
        else
            printf("%d ", ans[i].y);
    }

    return 0;
}

求助QAQ

2020/9/15 00:47
加载中...