1. 题目

传送门= ̄ω ̄=
题意:
依次张贴n张海报,新张贴的会覆盖之前的海报。给你每个海报覆盖的区间,问你最后还能看见几个海报。

n<=10^4,1<=坐标<=10^7

boshi&kb已然用线段树ac了%%%%%

2. 题解

用map离散化一下。等于把每个端点(包括左端点、右端的)从小到大排序,再把它们的位置改为它们在排序后的序列中的位置(比如排第一的位置改为1)。
然后从最后张贴的一张海报开始,一张一张张贴上去。数列初始为0,每次对当前海报所在区间求和,如果得到的和小于区间内元素个数(l-r+1),那么说明还有没被覆盖的,也就是在数列中为0的数字。那么ans++。再把这个海报所在区间的元素全部设为1。
最后输出ans。
记得清空数组、map。

说白了就是区间覆盖&区间求和
而且覆盖只可能覆盖成1

EASY,RIGHT?

我用的是分块,复杂度:n√n,然而比线段树块——常数小啊!

代码:

#include <cstdio>
#include <map>
#include <cmath>
#include <cstring>
#define bi(a) ((a-1)/sqn+1)
using namespace std;
typedef pair<int,int> pii;typedef map<int,int> mii;
int n,sqn,arr[20100],sum[300],atag[300];
pii p[10100];
mii mp;
inline int getsum(int l,int r)
{
    int ans=0;
    for(int i=l;i<=min(r,bi(l)*sqn);i++)if(atag[bi(i)]||arr[i])ans++;
    if(bi(l)!=bi(r))for(int i=(bi(r)-1)*sqn+1;i<=r;i++)ans+=atag[bi(i)]|arr[i];
    for(int i=bi(l)+1;i<bi(r);i++)ans+=sum[i];
    return ans;
}
inline void update(int l,int r)
{
    for(int i=l;!atag[bi(l)]&&i<=min(r,bi(l)*sqn);i++)
        sum[bi(i)]+=(arr[i]^1),arr[i]=1;
    for(int i=(bi(r)-1)*sqn+1;bi(l)!=bi(r)&&!atag[bi(r)]&&i<=r;i++)
        sum[bi(i)]+=(arr[i]^1),arr[i]=1;
    for(int i=bi(l)+1;i<bi(r);i++)sum[i]=sqn,atag[i]=1;
}
int main()
{
    int c,i,ans;
    scanf("%d",&c);
    while(c--)
    {
        memset(arr,0,sizeof(arr)),memset(sum,0,sizeof(sum));
        memset(atag,0,sizeof(atag)),mp.clear(),ans=0;
        scanf("%d",&n),sqn=sqrt(n);
        for(i=1;i<=n;i++)
            scanf("%d%d",&p[i].first,&p[i].second),
            mp[p[i].first]=mp[p[i].second]=0;
        i=1;
        for(mii::iterator it=mp.begin();it!=mp.end();it++,i++)it->second=i;
        for(i=1;i<=n;i++)p[i].first=mp[p[i].first],p[i].second=mp[p[i].second];
        for(i=n;i>=1;i--)
            ans+=getsum(p[i].first,p[i].second)<p[i].second-p[i].first+1,
            update(p[i].first,p[i].second);
        printf("%d\n",ans);
    }
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *