hiho第152周,离散化记笔记记笔记

Posted by Cww97 on 2017-05-28

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/72794941
感觉自己用node+map的存数据方案有点烦,
不过还没想到什么骚操作简化,用二进制的话也是换汤不换药,
一开始node里面全是bool导致A集合里重叠左端点的区间只算了一次,
60分无限WA,改成int,我真傻,真的

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
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 1e7 + 7;

struct node{
int al, ar, bl, br;
node(){}
node(int x, int y, int z, int w):al(x),ar(y),bl(z),br(w){}
node add(node b){return node(al+b.al, ar+b.ar, bl+b.bl, br+b.br);}
}nodes[N];

LL n, m, a[N];
map <LL,LL> mp;

int main()
{
//freopen("in.txt", "r", stdin);
scanf("%lld%lld", &n, &m);
LL l, r, top = 0;
memset(nodes, 0, sizeof(nodes));

for (LL i = 1; i <= n; i++){
scanf("%lld%lld", &l, &r);
if (!mp[l]) mp[l] = ++top;
nodes[mp[l]] = nodes[mp[l]].add(node(1,0,0,0));
if (!mp[r]) mp[r] = ++top;
nodes[mp[r]] = nodes[mp[r]].add(node(0,1,0,0));
a[i*2 - 1] = l;
a[i*2] = r;
}
for (LL i = 1; i <= m; i++){
scanf("%lld%lld", &l, &r);
if (!mp[l]) mp[l] = ++top;
nodes[mp[l]] = nodes[mp[l]].add(node(0,0,1,0));
if (!mp[r]) mp[r] = ++top;
nodes[mp[r]] = nodes[mp[r]].add(node(0,0,0,1));
a[n*2 + i*2 - 1] = l;
a[n*2 + i*2] = r;
}

sort(a + 1, a + 2*n+2*m+1 );
// top == cnt
LL cnt = unique(a+1, a+n*2+m*2+1) - (a+1);
LL cntA = 0, cntB = 0, ans = 0;

for (LL i = 1; i < cnt; i++){
node t = nodes[mp[a[i]]];
cntA += t.al - t.ar;
cntB += t.bl - t.br;
//printf("%lld %lld\n", cntA, cntB);
if (cntA > 0 && cntB == 0){
ans += a[i+1] - a[i];
}
}
printf("%lld\n", ans);
return 0;
}

几秒后的更新:
丢到map,不去重直接排序
不仅丢掉了wa点,还扔掉了很多冗余过程

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 1e7 + 7;
struct node{
int index, al, ar, bl, br;
node(){}
node(int in, int x, int y, int z, int w):index(in),al(x),ar(y),bl(z),br(w){}
bool operator <(const node& b)const{return index < b.index;}
}nodes[N];
LL n, m;

int main()
{
//freopen("in.txt", "r", stdin);
scanf("%lld%lld", &n, &m);
LL l, r, top = 0;
memset(nodes, 0, sizeof(nodes));

for (LL i = 1; i <= n; i++){
scanf("%lld%lld", &l, &r);
nodes[++top] = node(l,1,0,0,0);
nodes[++top] = node(r,0,1,0,0);
}
for (LL i = 1; i <= m; i++){
scanf("%lld%lld", &l, &r);
nodes[++top] = node(l,0,0,1,0);
nodes[++top] = node(r,0,0,0,1);
}

sort(nodes + 1, nodes + top +1 );
LL cntA = 0, cntB = 0, ans = 0;

for (LL i = 1; i < top; i++){
node t = nodes[i];
cntA += t.al - t.ar;
cntB += t.bl - t.br;
//printf("%lld %lld\n", cntA, cntB);
if (cntA > 0 && cntB == 0){
ans += nodes[i+1].index - t.index;
}
}
printf("%lld\n", ans);
return 0;
}