MYF

POJ 2528 Mayor's posters

Posted on | In | | Visitors

题目链接

POJ 2528

方法：离散化+线段树（区间替换值）

题目分析

题目大意

有一个特别长的线段，往上贴海报，贴n张，告诉每一张海报的起点x、终点y，问最终能看见几张海报。

解析

因为数据大小可能出现特别大的数字，但是特别大的数字在本题里没有什么意义，开那么大的数组既可能开不了又浪费空间，而我们只需要知道数字的大小关系即可，所以需要按数字大小将折线数字离散化成1,2,3,…,cnt。这样我们就可以造一棵cnt个点的线段树了。我们知道集合是自动去重的，所以我们每次把海报的编号插入集合，最后输出集合的size()，就是我们的结果。总结一下，我们的思路大概是这样：先将点离散化，然后把每一张海报进行编号，每次update树的时候将对应的点替换。最终将树上cnt个点全部query一遍，将每个点上的海报插入集合之中。输出内容即集合size()。

代码

此处有两种版本的代码，均可以ac，但是后者是比较好的。

当数据为

1

3
1 10
1 3
6 10

该组数据正确结果为3，错误为2。

具体原因把这组数据手写一下就明白了。

不完美版：

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, n) for (int i = 1; i <= n; i++)
#define ForK(i, k, n) for (int i = k; i <= n; i++)
#define ForD(i, n) for (int i = n; i >= 0; i--)
#define Rep(i, n) for (int i = 0; i < n; i++)
#define RepD(i, n) for (int i = n; i >= 0; i--)
#define MemI(a) memset(a, 0, sizeof(a))
#define MemC(a) memset(a, '\0', sizeof(a))
#define vset(a,val) memset(a,val,sizeof(a))
#define pf          printf
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define PI acos(-1)
#define bug         pf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int NV = 100005;
int add[NV<<2],sum[NV<<2];
void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt,int m)
{
    if (add[rt])
    {
        add[rt<<1] = add[rt];
        add[rt<<1|1] = add[rt];
        sum[rt<<1] = add[rt] * (m - (m >> 1));
        sum[rt<<1|1] = add[rt] * (m >> 1);
        add[rt] = 0;
    }
}
void build(int l,int r,int rt=1)
{
    add[rt] = 0;
    if (l == r)
    {
        sum[rt]=0;
        return ;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt=1)
{
    if (L <= l && r <= R)
    {
        add[rt] = c;
        sum[rt] = c * (r - l + 1);
        return ;
    }
    PushDown(rt , r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m) update(L , R , c , lson);
    if (m < R) update(L , R , c , rson);
    PushUp(rt);
}
int query(int L,int R,int l,int r,int rt=1)
{
    if (L <= l && r <= R)
    {
        return sum[rt];
    }
    PushDown(rt , r - l + 1);
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret += query(L , R , lson);
    if (m < R) ret += query(L , R , rson);
    return ret;
}

int main(){
    int t;
    int n;
    sf(t);
    while (t--) {
        set<int>st;
        sf(n);
        int v[2*(n+1)],tmp[2*(n+1)],a[2*(n+1)];
        for (int i=1; i<=2*n; i++) {
            scanf("%d",v+i);
        }
        /****离散化****/
        memcpy(tmp, v, sizeof(tmp));
        stable_sort(tmp+1, tmp+1+2*n);
        int cnt=unique(tmp+1, tmp+1+2*n)-tmp-1;
        for (int i=1; i<=2*n; i++)
            a[i]=lower_bound(tmp+1, tmp+cnt+1, v[i])-tmp;


        build(1, cnt);
        
        for (int i=1; i<=n; i++) {
            update(a[2*i-1], a[2*i], i, 1, cnt);
        }
        for (int i=1; i<=cnt; i++) {
            int x=query(i, i, 1, cnt);
            st.insert(x);
        }
        cout<<st.size()<<endl;
    }
}

完美版：

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <time.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MAXN=40000+5;
int sum[MAXN<<2],add[MAXN<<2];
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int m/*区间长度*/)
{
    if (add[rt]!=0)//倍数变化add[rt]!=1
    {
        add[rt<<1]=add[rt];
        add[rt<<1|1]=add[rt];
        sum[rt<<1]=add[rt]*(m-(m>>1));
        sum[rt<<1|1]=add[rt]*(m>>1);
        add[rt]=0;
    }
}
void build(int l,int r,int rt/*=1*/)
{
    add[rt]=0;//倍数变化add[rt]=1
    if (l==r)
    {
        sum[rt]=0;
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int L/*左端点*/,int R/*右端点*/,int c,int l,int r,int rt/*=1*/)
{
    if (L<=l&&r<=R)
    {
        add[rt]=c;
        sum[rt]=c*(r-l+1);
        return ;
    }
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if (L<=m)
        update(L,R,c,lson);
    if (m<R)
        update(L,R,c,rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt/*=1*/)
{
    if (L<=l&&r<=R)
    {
        return sum[rt];
    }
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    int ret=0;
    if (L<=m)
        ret+=query(L,R,lson);
    if (m<R)
        ret+=query(L,R,rson);
    return ret;
}
struct node
{
    long long num;
    long long pos;
} a[200000+5],b[200000+5];
int cmp1(node x,node y)
{
    return x.num<y.num;
}
int cmp2(node x,node y)
{
    return x.pos<y.pos;
}
long long vis[MAXN];
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        int l,r;
        for (int i=1; i<=2*n-1; i+=2)
        {
            scanf("%d %d",&l,&r);
            //a[i]=l,a[i+1]=r;
            a[i].num=l,a[i+1].num=r;
            a[i].pos=i,a[i+1].pos=i+1;
        }
        
        sort(a+1,a+2*n+1,cmp1);
        b[1].num=1,b[1].pos=a[1].pos;
        for (int i=2; i<=2*n; i++)
        {
            if (a[i].num==a[i-1].num)
                b[i].num=b[i-1].num;
            else if (a[i].num-a[i-1].num>1)
                b[i].num=b[i-1].num+2;
            else
                b[i].num=b[i-1].num+1;
            b[i].pos=a[i].pos;
        }
        int tot=b[2*n].num;
        sort(b+1,b+1+2*n,cmp2);
        build(1,tot,1);
        int v=1;
        for (int i=1; i<=2*n-1; i+=2)
        {
            update(b[i].num,b[i+1].num,v++,1,tot,1);
        }
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for (int i=1; i<=tot; i++)
        {
            int ans=query(i,i,1,tot,1);
            if (vis[ans]==0&&ans!=0)
            {
                vis[ans]=1;
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }
}