1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| namespace SweepLine{
#define lson (way<<1)
#define rson (way<<1|1)
#define mid (l+r)/2
long long x_pos[MAXN<<2],tot;
long long a,b,c,d,cnt,ans,n;
long long pos[MAXN];
namespace Segtree{
inline int read(){
register int a=0,f=1;register char c;
while((c=getchar())<'0')if(c=='-')f=-1;;
while(c>='0')a=a*10+(c^48),c=getchar();
return a*f;
}
struct SegTree{
long long l,r,val,len,lz;
}seg[MAXN<<2];
inline void build(int way,int l, int r){
seg[way].l = l;seg[way].r = r;
seg[way].val = seg[way].len = 0;
if (l==r) return;
build(lson,l,mid);
build(rson,mid+1,r);
}
inline void push(int way){
int l = seg[way].l, r = seg[way].r;
if(seg[way].val) {
seg[way].len = x_pos[r+1]-x_pos[l];
}else if (l!=r){
seg[way].len = seg[lson].len + seg[rson].len;
}else seg[way].len=0;
}
inline void update(int way, int l, int r, int qlow,int qhigh, int val){
if (qlow<=l && r<=qhigh){
seg[way].val += val;
push(way);
return;
}
if (l>qhigh || r<qlow || l==r) return;
update(lson,l,mid,qlow,qhigh,val);
update(rson,mid+1,r,qlow,qhigh,val);
push(way);
}
};
struct Edge{
int x1,x2,y,val;
bool operator <(const Edge& oth) const{
return y<oth.y || (y==oth.y && val>oth.val);
}
}edge[MAXN<<2];
inline void add(int x1,int x2, int y, int val){
edge[++tot].x1 = x1;
edge[tot].x2 = x2;
edge[tot].y = y;
edge[tot].val = val;
}
inline int Find(int num){
int l = 1, r = cnt;
while(l!=r){
if (x_pos[mid]==num) return mid;
if (x_pos[mid]>num) r = mid-1;
else l = mid+1;
}
return l;
}
inline void Find_area(){
sort(edge+1,edge+1+tot);
sort(x_pos+1,x_pos+1+tot);
cnt = unique(x_pos+1,x_pos+tot+1)-x_pos-1;
for (int i=1;i<tot;i++){
int x1 = Find(edge[i].x1),x2 = Find(edge[i].x2),val = edge[i].val;
Segtree::update(1,1,tot,x1,x2-1,val);
ans+=Segtree::seg[1].len*abs(edge[i+1].y-edge[i].y);
}
}
inline void init();
inline void solve();
}
|
