欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Picture 【HDU - 1828】【对于扫描线更新的一些特殊情况】

程序员文章站 2022-07-12 11:36:50
...

题目链接


这个问题,在以前写过博客,但是今朝再来看,属实还存有一些问题未曾解决

举个例子,我们来画一张图,并且给每个边标个序号。

Picture 【HDU - 1828】【对于扫描线更新的一些特殊情况】

  如图,我们有4条边,按照之前想的办法,我们进行处理,我们先放进去1这号边,再放入2这号边,实际上,这时候我们已经把下面的那个矩形块的周长完全计算了一遍,这时候其实我们已经算了2号的这条边,但是呢,我们再放进去3这号边的时候,其实又要去把3这号边的值给计算一遍,而且完完全全的是加3这号的边,那么实际上就把2这条边连续加了两次,而实际上呢,它并未产生贡献。

  虽然,不经过这样的考虑也是可以AC的,弱数据(可能是随机数造的吧开森),但是今天突然被问到这个,于是想到了,扫描线确实还有一些小细节尤为重要,现在写下来,自省。

  处理的方式呢?我们不妨在同等的高度上,我们先放进去要增入的边,在减去其余的边,我们就可以让那些由于先减后删多出来的贡献给消除掉了。所以,在对于y的排序上,我们先考虑y是否相同,若是相同了,我们先放入“val == 1”的加的部分,然后再是“val == -1”的减的部分。

放上数据(比较的强)

47
-1155 -1105 -285 -930
-1115 -765 -375 -615
-480 -705 -285 -165
-1200 -705 -1025 -175
-1105 -275 -385 -105
-1165 -10 -285 185
-1160 315 -710 400
-1195 340 -1070 655
-1140 580 -265 655
-480 325 -335 395
-390 365 -265 620
-770 365 -665 610
-1195 815 -1070 1110
-760 825 -660 1100
-405 810 -275 1115
-700 780 -360 860
-695 1065 -360 1130
-1110 775 -735 860
-1110 1070 -730 1145
-95 -1065 260 140
80 -725 460 750
-135 135 840 490
-135 135 750 490
40 -520 945 -210
620 -595 695 215
-5 670 610 855
-75 550 -25 830
240 815 370 1085
-90 980 145 1125
150 280 315 490
-155 -1035 -90 -845
815 855 1030 950
980 785 1165 860
985 945 1160 1015
835 730 895 1075
695 875 790 935
420 -1165 650 -520
815 -1090 945 -210
800 -130 1160 65
980 120 1150 690
995 -1140 1180 -125
1050 -825 1135 -195
865 -90 1090 10
1045 280 1090 625
1065 -655 1115 -245
70 -1155 315 -790
110 -1005 225 -825

 

ans = 37000

 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e4 + 5;
int N, num, cnt_x, X[maxN], lazy[maxN<<2];
struct node
{
    int lx, rx, y, val;
    node(int a=0, int b=0, int c=0, int d=0):lx(a), rx(b), y(c), val(d) {}
}line[maxN];
bool cmp(node e1, node e2) { return e1.y == e2.y ? e1.val > e2.val : e1.y < e2.y; }
struct TREE
{
    int val, range; //val是此时该段被覆盖次数
    bool lc, rc;
    TREE(int a=0, bool b=false, bool c=false, int d=0, int f=0):val(a), lc(b), rc(c), range(d) {}
}tree[maxN<<2];
inline void buildTree(int rt, int l, int r)
{
    lazy[rt] = 0;
    tree[rt] = TREE();
    if(l == r) return;
    int mid = HalF;
    buildTree(Lson); buildTree(Rson);
}
void pushup(int rt, int l, int r)
{
    if(lazy[rt])
    {
        tree[rt].val = X[r + 1] - X[l];
        tree[rt].range = 1;
        tree[rt].lc = tree[rt].rc = true;
    }
    else if(l == r) tree[rt] = TREE();
    else
    {
        tree[rt].val = tree[lsn].val + tree[rsn].val;
        tree[rt].range = tree[lsn].range + tree[rsn].range;
        tree[rt].lc = tree[lsn].lc;
        tree[rt].rc = tree[rsn].rc;
        if(tree[lsn].rc && tree[rsn].lc) tree[rt].range--;
    }
}
void update(int rt, int l, int r, int ql, int qr, int val)
{
    if(ql <= l && qr >= r)
    {
        lazy[rt] += val;
        pushup(myself);
        return;
    }
    int mid = HalF;
    if(qr <= mid) update(QL, val);
    else if(ql > mid) update(QR, val);
    else { update(QL, val); update(QR, val); }
    pushup(myself);
}
inline void init()
{
    num = 0;
    cnt_x = 1;
}
int main()
{
    while(scanf("%d", &N)!=EOF)
    {
        init();
        for(int i=1; i<=N; i++)
        {
            int lx, ly, rx, ry;
            scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
            line[++num] = node(lx, rx, ly, 1);
            X[num] = lx;
            line[++num] = node(lx, rx, ry, -1);
            X[num] = rx;
        }
        sort(X + 1, X + num + 1);
        sort(line + 1, line + num + 1, cmp);
        cnt_x = (int)(unique(X + 1, X + num + 1) - X - 1);
        buildTree(1, 1, cnt_x);
        ll ans = 0, las = 0;
        for(int i=1; i<num; i++)
        {
            int l = (int)(lower_bound(X + 1, X + cnt_x + 1, line[i].lx) - X);
            int r = (int)(lower_bound(X + 1, X + cnt_x + 1, line[i].rx) - X - 1);
            update(1, 1, cnt_x, l, r, line[i].val);
            ans += abs(tree[1].val - las) + tree[1].range * 2 * (line[i+1].y - line[i].y);
            las = tree[1].val;
        }
        ans += line[num].rx - line[num].lx;
        printf("%lld\n", ans);
    }
    return 0;
}

  细思极恐!

相关标签: 扫描线