欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2825

程序员文章站 2022-03-23 11:36:55
...
//区间染色+特殊离散化处理
//用lazy线段树存染色区域
//一直WA 不知道哪里错了 改到凌晨1点半 懒得改了 等将来填坑吧
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=2e4+100;
int tree_value[maxn<<2];
bool visit[maxn<<2];
int lisan[maxn<<2],le[maxn<<2],ri[maxn<<2];
void pushdown(int rt) {
    tree_value[rt<<1]=tree_value[rt<<1|1]=tree_value[rt];
    tree_value[rt]=-1;
}
void update(int L,int R,int l,int r,int value,int rt) {
    if(L<=l&&R>=r) {
        tree_value[rt]=value;
        return;
    }
    if(tree_value[rt]!=-1)
        pushdown(rt);
    int m=l+r>>1;
    if(R<=m)
        update(L,R,l,m,value,rt<<1);
    else if(L>m)
        update(L,R,m+1,r,value,rt<<1|1);
    else {
        update(L,m,l,m,value,rt<<1);
        update(m+1,R,m+1,r,value,rt<<1|1);
    }
}
void query(int l,int r,int rt,int& ans) {
    if(tree_value[rt]!=-1){
        if(visit[tree_value[rt]]==false){//第一次染色
            ans++;//答案+1
            visit[tree_value[rt]]=true;
        }
        return;
    }
    if(l==r)
        return ;
    int m=l+r>>1;
    query(l,m,rt<<1,ans);
    query(m+1,r,rt<<1|1,ans);
}
int main(void) {
    //freopen("E:\\input.txt","r",stdin);
    ios::sync_with_stdio(false);
    int T,n,total,m,temp,ans;
    cin>>T;
    while(T--) {
        cin>>n;
        memset(tree_value,-1,sizeof(tree_value));
        memset(visit,0,sizeof(visit));
        total=0;
        for(int i=0; i<n; i++) {
            cin>>le[i]>>ri[i];
            lisan[total++]=le[i];
            lisan[total++]=ri[i];
        }
        sort(lisan,lisan+total);
        m=unique(lisan,lisan+total)-lisan;
        temp=m;
        for(int i=1; i<temp; i++) {
            if(lisan[i]-lisan[i-1]>1)
                lisan[m++]=lisan[i-1]+1;
        }
        sort(lisan,lisan+m);
        for(int i=0; i<n; i++) {
            int x=lower_bound(lisan,lisan+m,le[i])-lisan;
            int y=lower_bound(lisan,lisan+m,ri[i])-lisan;
            update(x,y,0,m-1,i,1);
        }
        ans=0;
        query(0,m-1,1,ans);
        cout<<ans<<endl;
    }
    return 0;
}
//AC 别人家的代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=20000+100;//点的数目
int tree[maxn<<4];
int li[maxn],ri[maxn];
int lisan[3*maxn];
bool visit[3*maxn];
void pushdown(int p) {
    tree[p<<1]=tree[(p<<1)|1]=tree[p];
    tree[p]=-1;
}
void update(int p,int l,int r,int x,int y,int v) {//update(1,0,m-1,x,y,i);
    if(x<=l&&y>=r) {
        tree[p]=v;
        return;
    }
    if(tree[p]!=-1)
        pushdown(p);
    int mid=(l+r)>>1;
    if(y<=mid)
        update(p<<1,l,mid,x,y,v);
    else if(x>mid)
        update((p<<1)|1,mid+1,r,x,y,v);
    else
        update(p<<1,l,mid,x,mid,v),update((p<<1)|1,mid+1,r,mid+1,y,v);
}
int ans;
void query(int p,int l,int r) {
    if(tree[p]!=-1) {
        if(!visit[tree[p]]) {
            ans++;
            visit[tree[p]]=true;
        }
        return;
    }
    if(l==r)
        return;
    int mid=(l+r)>>1;
    query(p<<1,l,mid);
    query((p<<1)|1,mid+1,r);
}
int main() {
    //freopen("E:\\input.txt","r",stdin);
    int T;
    scanf("%d",&T);
    int n;
    while(T--) {
        scanf("%d",&n);
        memset(tree,-1,sizeof(tree));
        memset(visit,false,sizeof(visit));
        int tot=0;
        for(int i=0; i<n; i++) {
            scanf("%d%d",&li[i],&ri[i]);
            lisan[tot++]=li[i];
            lisan[tot++]=ri[i];
        }
        sort(lisan,lisan+tot);//tot是数组长度
        int m=unique(lisan,lisan+tot)-lisan;//m为不重复的个数
        int t=m;
        for(int i=1; i<t; i++) {
            if(lisan[i]-lisan[i-1]>1)
                lisan[m++]=lisan[i-1]+1;
        }
        sort(lisan,lisan+m);
        for(int i=0; i<n; i++) {
            int x=lower_bound(lisan,lisan+m,li[i])-lisan;
            int y=lower_bound(lisan,lisan+m,ri[i])-lisan;
            update(1,0,m-1,x,y,i);
        }
        ans=0;
        query(1,0,m-1);
        printf("%d\n",ans);
    }
}

 

相关标签: POJ 2528