首页 > 代码库 > poj2528---Mayor's posters

poj2528---Mayor's posters

2024-07-24 06:55:16   217人阅读

题意：有t组测试数据，有n张海报，海报按题目给出的顺序覆盖，问最后能看到几张海报。这道题刚开始没想出来，，最后看的题解，，从最后一张海报开始处理 一下子就明白了。线段树区间更新搞之。（当然离散化是必须的）

预处理区间所有值都置0，然后从最后面开始，每次求 l[i] ~r[i]区间的和，如果小于r[i]-l[i]+1,就说明这张海报可以看见，然后把l[i]~r[i]这个区间所有值置为1，继续下一张海报。

 1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cctype> 8 #include <cstdio> 9 #include <string>10 #include <vector>11 #include <cstdlib>12 #include <cstring>13 #include <iostream>14 #include <algorithm>15 using namespace std;16 typedef unsigned long long ull;17 typedef long long ll;18 const int inf = 0x3f3f3f3f;19 const double eps = 1e-8;20 const int maxn = 2e4+10;21 int n,a[maxn*2],setv[maxn<<2];22 void push_down(int pos)23 {24     if (~setv[pos])25     {26         setv[pos<<1] = setv[pos<<1|1] = setv[pos];27         setv[pos] = -1;28     }29 }30 void update(int l,int r,int pos,int ua,int ub,int v)31 {32     if (ua <= l && ub >= r)33         setv[pos] = v;34     else35     {36         push_down(pos);37         int mid = (l + r) >> 1;38         if (ua <= mid)39             update(l,mid,pos<<1,ua,ub,v);40         if (ub > mid)41             update(mid+1,r,pos<<1|1,ua,ub,v);42     }43 }44 int query(int l,int r,int pos,int ua,int ub)45 {46     if (~setv[pos])47     {48         return setv[pos] * (min(ub,r) - max(ua,l) + 1);49     }50     int mid = (l + r) >> 1;51     int ans = 0;52     if (ua <= mid)53         ans += query(l,mid,pos<<1,ua,ub);54     if (ub > mid)55         ans += query(mid+1,r,pos<<1|1,ua,ub);56     return ans;57 58 }59 int x[maxn],y[maxn];60 int main(void)61 {62     #ifndef ONLINE_JUDGE63         freopen("in.txt","r",stdin);64     #endif65     int t;66     scanf ("%d",&t);67     while(t--)68     {69         scanf ("%d",&n);70         int tot = 0;71         for (int i = 0; i < n; i++)72         {73             scanf ("%d%d",x+i,y+i);74             a[tot++] = x[i];75             a[tot++] = y[i];76         }77         sort(a,a+tot);78         tot = unique(a,a+tot) - a;79         for (int i = 0; i < n; i++)80         {81             x[i] = lower_bound(a,a+tot,x[i]) - a + 1;82             y[i] = lower_bound(a,a+tot,y[i]) - a + 1;83         }84         int ans = 0;85         update(1,tot,1,1,tot,0);86         for (int i = n - 1; i >= 0; i--)87         {88             if (query(1,tot,1,x[i],y[i]) < y[i] - x[i] + 1)89             {90                 ans++;91                 update(1,tot,1,x[i],y[i],1);92             }93         }94         printf("%d\n",ans);95     }96     return 0;97 }

 

poj2528---Mayor's posters


联系
我们