POJ 2528 Mayor's posters 线段树（成段更新+离散化）

题意：

给出N个海报，每个海报有一个长度区间（a,b）.按顺序贴在墙上。

问最后可以看到几张海报。

思路：

一想到的就是线段树，对每个区间进行染色，最后查找一共有多少种颜色。

第一次写玩没看数据大小。MLE了。。仔细一看，海报长度1QW。

然后写了个离散化的，300MS+。

又去看了别人的离散化。。神多了。。60MS。。

优化后的离散

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 20005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x)(x<<1|1)
using namespace std;

struct kdq
{
    int l,r,flag;
} tree[Max*4];

struct kdq1
{
    int num,id;
} poster[Max];

int aa[Max][2];
void build_tree(int l,int r,int u)
{
    tree[u].l=l;
    tree[u].r=r;
    tree[u].flag=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    build_tree(l,mid,LL(u));
    build_tree(mid+1,r,RR(u));
}

void update(int l,int r,int u,int i)
{
    if(l>tree[u].r||r<tree[u].l)return ;
    if(l==tree[u].l&&r==tree[u].r)
    {
        tree[u].flag=i;
        return ;
    }
    if(tree[u].flag > 0 && tree[u].flag != i)
    {
        tree[LL(u)].flag = tree[u].flag;
        tree[RR(u)].flag= tree[u].flag;
        tree[u].flag = 0;
    }
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid)
        update(l,r,LL(u),i);
    else if(l>mid)
        update(l,r,RR(u),i);
    else
    {
        update(l,mid,LL(u),i);
        update(mid+1,r,RR(u),i);
    }
    if(tree[LL(u)].flag==tree[RR(u)].flag)
        tree[u].flag=tree[LL(u)].flag;
    else
        tree[u].flag=0;
}

int ans;
bool visit1[20005];

void query(int l,int r,int u)
{
    if(tree[u].flag&&!visit1[tree[u].flag])
        return ;
    if(tree[u].flag)
    {
        ans+=visit1[tree[u].flag];
        visit1[tree[u].flag]=0;
        return ;
    }
    int mid=(l+r)>>1;
    query(l,mid,LL(u));
    query(mid+1,r,RR(u));
}
bool cmp(kdq1 &a,kdq1 &b)
{
    return a.num<b.num;
}
int main()
{
    int i,j,k,l,n,m,T;
    scanf("%d",&T);
    int a,b;
    while(T--)
    {
        memset(visit1,1,sizeof(visit1));
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            scanf("%d%d",&aa[i][0],&aa[i][1]);
            poster[2*i].num=aa[i][0];
            poster[2*i].id=-(i+1);
            poster[2*i+1].num=aa[i][1];
            poster[2*i+1].id=i+1;
        }
        sort(poster,poster+2*n,cmp);
        int temp=poster[0].num;
        int tp=1;
        for(i=0; i<2*n; i++)
        {
            if(temp!=poster[i].num)
            {
                tp++;
                temp=poster[i].num;
            }
            if(poster[i].id<0)
            {
                aa[-poster[i].id-1][0]=tp;
            }
            else
            {
                aa[poster[i].id-1][1]=tp;
            }
        }
        build_tree(1,tp,1);
        for(i=0; i<n; i++)
            update(aa[i][0],aa[i][1],1,i+1);
        ans=0;
        query(1,tp,1);
        printf("%d\n",ans);
    }
    return 0;
}

第一次写的离散

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 20005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x)(x<<1|1)
using namespace std;

struct kdq
{
    int l,r,flag;
} tree[Max*4];

int aa[Max],bb[Max];

void build_tree(int l,int r,int u)
{
    tree[u].l=l;
    tree[u].r=r;
    tree[u].flag=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    build_tree(l,mid,LL(u));
    build_tree(mid+1,r,RR(u));
}

void update(int l,int r,int u,int i)
{
    if(l>tree[u].r||r<tree[u].l)return ;
    if(l==tree[u].l&&r==tree[u].r)
    {
        tree[u].flag=i;
        return ;
    }
    if(tree[u].flag > 0 && tree[u].flag != i)
    {
        tree[LL(u)].flag = tree[u].flag;
        tree[RR(u)].flag= tree[u].flag;
        tree[u].flag = 0;
    }
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid)
        update(l,r,LL(u),i);
    else if(l>mid)
        update(l,r,RR(u),i);
    else
    {
        update(l,mid,LL(u),i);
        update(mid+1,r,RR(u),i);
    }
    if(tree[LL(u)].flag==tree[RR(u)].flag)
        tree[u].flag=tree[LL(u)].flag;
    else
        tree[u].flag=0;
}

int ans;
int yinshe[20005];
int visit[10000005];
bool visit1[20005];

void query(int l,int r,int u)
{
    if(tree[u].flag&&!visit1[tree[u].flag])
        return ;
    if(tree[u].flag)
    {
        ans+=visit1[tree[u].flag];
        visit1[tree[u].flag]=0;
        return ;
    }
    int mid=(l+r)>>1;
    query(l,mid,LL(u));
    query(mid+1,r,RR(u));
}

int main()
{
    int i,j,k,l,n,m,T;
    scanf("%d",&T);
    int a,b;
    while(T--)
    {
        memset(visit1,1,sizeof(visit1));
        memset(visit,0,sizeof(visit));
        memset(yinshe,0,sizeof(yinshe));
        scanf("%d",&n);
        int num=1;
         for(i=1; i<=n; i++)
         {
             scanf("%d%d",&aa[i],&bb[i]);
             if(!visit[aa[i]])
             {
                 yinshe[num]=aa[i];
                 visit[aa[i]]=1;
                 num++;
             }
             if(!visit[bb[i]])
             {
                 yinshe[num]=bb[i];
                 visit[bb[i]]=1;
                 num++;
             }
         }
         sort(yinshe+1,yinshe+num);
         for(i=1; i<num; i++)
             visit[yinshe[i]]=i;
         build_tree(1,num-1,1);
        for(i=1;i<=n;i++)
        update(visit[aa[i]],visit[bb[i]],1,i);
        ans=0;
        query(1,num-1,1);
        printf("%d\n",ans);
    }
    return 0;
}

显然优化后的神多了。。。继续。