记录编号	195726	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.324 s
提交时间	2015-10-19 17:01:05	内存使用	229.21 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=1010;
const int maxm=10000010;
const int mod=1000000007;

struct node
{
    int s,e;
} a[maxn];

int tree[maxm*6];
int vis[maxn];//t[maxn*2];
//int num[maxm];
int ans=0;

void modify(int ql,int qr,int val,int l,int r,int dir)
{
    if(ql>r||qr<l) return;
    if(ql<=l&&qr>=r)
    {
        tree[dir]=val;
        return;
    }
    if(tree[dir]!=0)
    {
        tree[dir*2]=tree[dir*2+1]=tree[dir];
        tree[dir]=0;
    }
    int m=(l+r)>>1;
    modify(ql,qr,val,l,m,dir*2);
    modify(ql,qr,val,m+1,r,dir*2+1);
}

void query(int l,int r,int dir)
{
    if(!vis[tree[dir]])
    {
        vis[tree[dir]]=1;
        ans++;
    }
    if(l==r||tree[dir]!=0) return;
    int m=(l+r)>>1;
    query(l,m,dir*2);
    query(m+1,r,dir*2+1);
}

int main()
{
    freopen("ha14d.in","r",stdin);
    freopen("ha14d.out","w",stdout);
    //clock_t st=clock();
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i].s,&a[i].e);
        //t[i]=a[i].s;t[i+m]=a[i].e;
    }
    /*sort(t+1,t+1+m*2);
    int cnt=1;
    for(int i=1;i<=2*m;i++)
    {
        if (t[i]==t[i+1]) continue;
        num[t[i]]=cnt++;
        if(t[i+1]!=t[i]+1&&i!=m*2) num[t[i]+1]=cnt++;
    }
    cnt--;*/
    for(int i=1;i<=m;i++)
    {
        modify(a[i].s,a[i].e,i,1,n,1);
    }
    //for(int i=1;i<=31;i++) printf("%d ",tree[i]);
    vis[0]=1;query(1,n,1);
    printf("%d\n",ans);
    //clock_t ed=clock();
    //printf("\nTime used : %.5lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}