这个问题，在以前写过博客，但是今朝再来看，属实还存有一些问题未曾解决
举个例子，我们来画一张图，并且给每个边标个序号。
如图，我们有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;
}细思极恐！