30分 求助求hack qwq

limuloo @ 2019-04-30 19:35:51

// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
using namespace  std;
#define N 400005
struct {
    int l,r,p,col;
}tree[4*N];
int n,m,l,r,cnt,ans,num;
int a[N*4],f[N];
bool vis[N];
struct {int l,r;}q[N];
void build(int ll,int rr,int k){
    if(ll==rr){tree[k].l=a[ll]; tree[k].r=a[ll+1]; f[ll]=k;  return;}
    build(ll,(ll+rr)/2,2*k); build((ll+rr)/2+1,rr,2*k+1);
    tree[k].l=tree[2*k].l;  tree[k].r=tree[2*k+1].r;
}
void tp(int k){
    tree[2*k].p=tree[k].p; tree[2*k+1].p=tree[k].p;
    tree[2*k].col=tree[k].p; tree[2*k+1].col=tree[k].p;  tree[k].p=0;
}
void change(int ll,int rr,int k,int col){
    if(tree[k].l>=ll&&tree[k].r<=rr){ tree[k].p=col; tree[k].col=col; return; }
    if(tree[k].p) tp(k);
    if(ll<tree[2*k].r) change(ll,rr,2*k,col); if(rr>tree[2*k+1].l) change(ll,rr,2*k+1,col);
}
void trans(int ll,int rr,int k){
    if(ll==rr){return;}
    if(tree[k].p) tp(k);
    trans(ll,(ll+rr)/2,2*k); trans((ll+rr)/2+1,rr,2*k+1);
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        ++num;
        scanf("%d %d",&q[num].l,&q[num].r);
        if(q[i].l>n){--num;continue;}
        if(q[i].r>n) q[i].r=n;
        ++q[i].r; a[++cnt]=q[num].l; a[++cnt]=q[num].r;
    }
    sort(a+1,a+1+cnt);
    cnt=(int)(unique(a+1,a+1+cnt)-a-1); --cnt;
    build(1,cnt,1);
    for(int i=1;i<=num;++i) change(q[i].l,q[i].r,1,i);
    trans(1,cnt,1);
    for(int i=1;i<=cnt;++i){
        if(!vis[tree[f[i]].col]){
            vis[tree[f[i]].col]=true;
            ++ans;
        }
    }
    printf("%d\n",ans);
    return 0;
}

by limuloo @ 2019-04-30 19:37:52

上面代码发错了 再发一遍qwq

// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
using namespace  std;
#define N 4005
struct {
    int l,r,p,col;
}tree[4*N];
int n,m,l,r,cnt,ans;
int a[N*4],f[N];
bool vis[N];
struct {int l,r;}q[N];
void build(int ll,int rr,int k){  // ll rr表示 表示的是ll-rr的区间
    if(ll==rr){tree[k].l=a[ll]; tree[k].r=a[ll+1]; f[ll]=k;  return;}
    build(ll,(ll+rr)/2,2*k); build((ll+rr)/2+1,rr,2*k+1);
    tree[k].l=tree[2*k].l;  tree[k].r=tree[2*k+1].r;
}
void tp(int k){
    tree[2*k].p=tree[k].p; tree[2*k+1].p=tree[k].p;
    tree[2*k].col=tree[k].p; tree[2*k+1].col=tree[k].p;  tree[k].p=0;
}
void change(int ll,int rr,int k,int col){
    if(tree[k].l>=ll&&tree[k].r<=rr){ tree[k].p=col; tree[k].col=col; return; }
    if(tree[k].p) tp(k);
    if(ll<tree[2*k].r) change(ll,rr,2*k,col); if(rr>tree[2*k+1].l) change(ll,rr,2*k+1,col);
}
void trans(int ll,int rr,int k){  // ll rr表示 表示的是ll-rr的区间
    if(ll==rr){return;}
    if(tree[k].p) tp(k);
    trans(ll,(ll+rr)/2,2*k); trans((ll+rr)/2+1,rr,2*k+1);
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d %d",&q[i].l,&q[i].r);
        ++q[i].r; a[++cnt]=q[i].l; a[++cnt]=q[i].r;
    }
    sort(a+1,a+1+cnt);
    cnt=(int)(unique(a+1,a+1+cnt)-a-1); --cnt;
    build(1,cnt,1);
    for(int i=1;i<=m;++i) change(q[i].l,q[i].r,1,i);
    trans(1,cnt,1);
    for(int i=1;i<=cnt;++i){
        if(!vis[tree[f[i]].col]){
            vis[tree[f[i]].col]=true;
            ++ans;
        }
    }
    printf("%d\n",ans);
    return 0;
}

by wxwoo @ 2019-04-30 19:45:27

这题不是暴力就能艹过的吗

by limuloo @ 2019-04-30 20:19:22

已AC 加一个vis[0]=true就过了qwq