题解 P1047 【校门外的树】
Juan_feng
2018-10-12 18:22:39
为何要用树状数组？只是为了炫耀你们的学识吗？用模拟难道不是更好吗？
——为何要用模拟？只是为了炫耀你们的学识吗？用线段树难道不是更好吗？
——为何要用线段树？只是为了炫耀你们的学识吗？用分块难道不是更好吗？
——为何要用分块？只是为了炫耀你们的学识吗？用**珂朵莉树**难道不是更好吗？
（以上改编自本题一题解的评论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++!