一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

题解 P1047 【校门外的树】

posted on 2018-10-12 18:22:39 | under 题解 |

为何要用树状数组?只是为了炫耀你们的学识吗?用模拟难道不是更好吗?

——为何要用模拟?只是为了炫耀你们的学识吗?用线段树难道不是更好吗?

——为何要用线段树?只是为了炫耀你们的学识吗?用分块难道不是更好吗?

——为何要用分块?只是为了炫耀你们的学识吗?用珂朵莉树难道不是更好吗?

(以上改编自本题一题解的评论qwq)


小蒟蒻终于有机会写一道这么难的题的题解了,So exciting!

看了上面的一段话,各位巨佬一定已经明白小蒟蒻这篇题解想讲的是什么了,但是

珂朵莉树是个什么东西?

肯定有人想问这个问题,小蒟蒻这里先不说,各位暂且看看小蒟蒻做这道题的心路历程QωQ

在刚学OI的时候,小蒟蒻最开始自然是用模拟做的,直接N方暴力覆盖,最后再去查询qwq

之后小蒟蒻接触了线段树,感觉线段树这东西好好用呀,手里拿着锤子看什么都是钉子,结果就重新发现了这道神题,一开始还调了不少时间,后来发现其实就是个线段树的板子qwq,初始值都赋为1,update赋值为0,最后query求和一下就完事了(这道题因为是统计全部区间可以直接输出ans[1])

之后小蒟蒻有去学了分块感觉分块这东西也好好用呀,把数列分成根号n块,对于散块直接暴力修改,整块打个tag,同时要维护一个ans数组,保存每个块内的答案。查询因为是从0~n,一定都是整块,小蒟蒻就偷了个懒,直接把所有的ans加起来了。

以上三种方法的代码在题解最后给出)

好了,终于要进入今天的正题了!

观察题目:区间赋值为0

选择珂朵莉树

简单介绍一下,珂朵莉树是一种基于set的暴力数据结构

珂朵莉树的关键在于推平一段区间,即把一段区间的数变的一样(似乎所有珂朵莉树的讲解里面都说了这一句话)

对每一个点建立一个集合

当需要修改的时候,就把要修改区间分成两部分,一部分是需要修改的,一部分是不需要修改的,返回需要修改的地址;

然后把这一段区间内所有的集合都删掉,用一个大集合代替之就可以了。

那么代码如下: 先上珂朵莉树:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;++i)
#define IT set<node>::iterator
using namespace std;

int n,m,x,y;

inline void in(re int &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9'){
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
}

inline void out(re int a){
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

struct node{
    int l,r;
    mutable int v;
    node(int L,int R=-1,int V=0):l(L),r(R),v(V) {}
    bool operator <(const node &o)const{
        return l<o.l;
    }
};

set<node> s;

inline IT split(re int pos){
    IT it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos)
      return it;
    --it;
    int L=it->l;
    int R=it->r;
    int V=it->v;
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}

inline void assign_val(re int l,re int r,re int val=0){
    IT itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,val));
}

inline int query(re int l,re int r){
    int res=0;
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
      res+=(itl->r-itl->l+1)*(itl->v);
    return res;
}

int main(){
    in(n),in(m);
    s.insert(node(0,n,1));
    FOR(i,1,m){
        in(x),in(y);
        assign_val(x,y,0);
    }
    out(query(0,n));
    puts("");
}

然后是之前提到的三种方法:

code1 模拟:

#include<iostream>
#include<cstring>
#include<cstdio> 
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;++i)
using namespace std;

int a[200001],i,h1,h2,s=0,m,l,j;

inline void in(re int &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9'){
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
}

inline void out(re int a){
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

int main(){
    in(l),in(m); 
    FOR(i,1,m){
        in(h1),in(h2);
        FOR(j,h1,h2)
          a[j]=1;
    }
    FOR(i,0,l)  
      if(a[i]==0)
        ++s;
    out(s);
    puts("");    
}

code2 线段树:

#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;++i)
using namespace std;

int a[100001],ans[100001],tag[100001],m,n,k,l,t,cnt,x,y;

inline int in(){  
    char ch;  
    int a=0;  
    while(!(((ch=getchar())>='0')&&(ch<='9')));  
    a*=10;a+=ch-'0';  
    while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';  
    return a;  
}

inline void out(int a){
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

inline int ls(int ss){
    return ss<<1;
}

inline int rs(int ss){
    return (ss<<1)|1;
}

inline void push_up(int k){
    ans[k]=ans[ls(k)]+ans[rs(k)];
}

inline void push_down(int i){
    if(tag[i]){
        tag[i]=0;
        tag[ls(i)]=1;
        tag[rs(i)]=1;
        ans[ls(i)]=0;
        ans[rs(i)]=0;
    }
}

inline void build(int p,int l,int r){
    if(l==r){
        ans[p]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}

inline void update(int nl,int nr,int l,int r,int p){
    if(nl<=l&&r<=nr){
        tag[p]=1;
        ans[p]=0;
        return;
    }
    push_down(p);
    int mid=(l+r)>>1;
    if(nl<=mid) update(nl,nr,l,mid,ls(p));
    if(nr>mid) update(nl,nr,mid+1,r,rs(p));
    push_up(p);
}

int main(){
    n=in(),m=in();
    build(1,1,n+1);
    FOR(i,1,m){
        x=in(),y=in();
        update(x+1,y+1,1,n+1,1);
    }
    out(ans[1]);
    puts("");
}

code3 分块:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath> 
#define maxn 500010
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;++i)
using namespace std;

int n,m,c,r,t,x,y,z,sq,anss;
int a[maxn],b[maxn],tag[maxn],ans[maxn];

inline void in(int &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9'){
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
}

inline void out(int a){
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

void doit(int x,int y){
    if(tag[b[x]]!=1)
      FOR(i,x,min(y,b[x]*sq))
        ans[b[x]]-=a[i],a[i]=0;
    if(b[x]!=b[y]&&tag[b[y]]!=1)
      FOR(i,(b[y]-1)*sq+1,y)
        ans[b[y]]-=a[i],a[i]=0;
    FOR(i,b[x]+1,b[y]-1)
      tag[i]=1,ans[i]=0;
}

int main(){
    in(n),in(m);
    sq=sqrt(n);
    FOR(i,0,n)
      a[i]=1,b[i]=(i-1)/sq+1,++ans[b[i]];
    FOR(i,1,m){
        in(x),in(y);
        doit(x,y);
    }
    FOR(i,1,b[n])
      anss+=ans[i];
    out(anss);
    puts("");
} 

小蒟蒻的题解也就到此结束啦qwq

如果有什么意见或建议的话请和小蒟蒻私信呐qwq

最后祝大家NOIP RP++!