洛谷P1047 [NOIP2005 普及组] 校门外的树 题解
前言
如何把一道入门题写成省选题？（手动滑稽）
本题解是我在练习分块时突发奇想写的，真就把入门题写成省选题的感觉（
才发现原来这些简单题这么有趣（
题目链接： P1047 [NOIP2005 普及组] 校门外的树
题意：马路上砍树，问砍了 $m$ 次还有几棵树
一、模拟解法（正常解法）
我们只要把每次砍掉的树标记一下，最后统计未标记的数量即可
注意下标从 $0$ 开始，共 $n+1$ 个数
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(1e4+5)
int n,m,ans;
bool a[MAXN];
signed main()
{
scanf("%lld%lld",&n,&m);
for(R int i=1,l,r; i<=m; i++)
{
scanf("%lld%lld",&l,&r);
for(R int j=l; j<=r; j++)
a[j]=1;
}
for(R int i=0; i<=n; i++)ans+=(a[i]==0);
printf("%lld\n",ans);
return 0;
}二、线段树解法（开始奇怪起来）
直接用线段树维护区间，没什么特别的
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(1e4+5)
template<typename T>inline void read(R T &k)
{
R char ch=getchar(); R T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
k=x*f;
}
int n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
inline int ls(R int x){return x<<1;}
inline int rs(R int x){return x<<1|1;}
void proc(R int l,R int r,R int at)
{
R int u=at>>1;
if(tag[u])ans[at]=0,tag[at]=1;
}
void push_up(R int at){ans[at]=ans[ls(at)]+ans[rs(at)];}
void push_down(R int l,R int r,R int at)
{
R int mid=(l+r)>>1;
proc(l,mid,ls(at));
proc(mid+1,r,rs(at));
tag[at]=0;
}
void build(R int l,R int r,R int at)
{
tag[at]=0;
if(l==r){ans[at]=a[l];return;}
R int mid=(l+r)>>1;
build(l,mid,ls(at));
build(mid+1,r,rs(at));
push_up(at);
}
void update(R int nl,R int nr,R int l,R int r,R int at)
{
if(nl<=l&&r<=nr)
{
ans[at]=0;
tag[at]=1;
return;
}
R int mid=(l+r)>>1;
push_down(l,r,at);
if(nl<=mid)update(nl,nr,l,mid,ls(at));
if(nr>mid)update(nl,nr,mid+1,r,rs(at));
push_up(at);
}
int query(R int nl,R int nr,R int l,R int r,R int at)
{
R int res=0;
if(nl<=l&&r<=nr)
return ans[at];
R int mid=(l+r)>>1;
push_down(l,r,at);
if(nl<=mid)res+=query(nl,nr,l,mid,ls(at));
if(nr>mid)res+=query(nl,nr,mid+1,r,rs(at));
return res;
}
signed main()
{
read(n);read(m);++n;
for(R int i=1; i<=n; i++)
a[i]=1;
build(1,n,1);
while(m--)
{
R int l,r;
read(l);read(r);
update(l+1,r+1,1,n,1);
}
printf("%lld\n",query(1,n,1,n,1));
return 0;
}三、分块解法 （开始毒瘤起来）
只有一个要注意的，就是每次暴力减的时候要防止减为负数
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(1e4+5)
template<typename T>inline void read(R T &k)
{
R char ch=getchar(); R T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
k=x*f;
}
int n,m,len;
int a[MAXN],ans[MAXN],id[MAXN],tag[MAXN];
void add(R int l,R int r)
{
R int lid=id[l],rid=id[r];
if(lid==rid)
{
for(R int i=l; i<=r; i++)
ans[id[i]]-=a[i],a[i]=0;
return;
}
for(R int i=l; i<=lid*len&&!tag[lid]; i++)
ans[id[i]]-=a[i],a[i]=0;
for(R int i=lid+1;i<rid; i++)
tag[i]=1,ans[i]=0;
for(R int i=(rid-1)*len+1; i<=r&&!tag[rid]; i++)
ans[id[i]]-=a[i],a[i]=0;
}
int sum(R int l,R int r)
{
R int res=0;
R int lid=id[l],rid=id[r];
if(tag[lid])
{
for(R int i=(lid-1)*len+1; i<=len*lid; i++)
ans[id[i]]-=a[i],a[i]=0;
}
if(tag[rid])
{
for(R int i=(rid-1)*len+1; i<=len*rid; i++)
ans[id[i]]-=a[i],a[i]=0;
}
if(lid==rid)
{
for(R int i=l; i<=r; i++)
res+=a[i];
return res;
}
for(R int i=l; i<=lid*len; i++)
res+=a[i];
for(R int i=lid+1; i<rid; i++)
res+=ans[i];
for(R int i=(rid-1)*len+1; i<=r; i++)
res+=a[i];
return res;
}
signed main()
{
read(n);read(m);++n;len=sqrt(n);
for(R int i=1; i<=n; i++)
{
a[i]=1;
id[i]=(i-1)/len+1;
ans[id[i]]++;
}
while(m--)
{
R int x,y;
read(x);read(y);
add(x+1,y+1);
}
printf("%lld\n",sum(1,n));
return 0;
}四、珂朵莉树解法 （非常珂学）
一看这个推平操作，立马就想到了珂朵莉树
如果不知道珂朵莉树的可以看看我写的这篇文章
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(1e4+5)
template<typename T>inline void read(R T &k)
{
R char ch=getchar(); R T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
k=x*f;
}
int n,m;
int a[MAXN];
struct node
{
int l,r;
mutable int v;
bool operator<(const node &o)const
{return l<o.l;}
};
set<node>s;
set<node>::iterator split(R int pos)
{
set<node>::iterator it=s.lower_bound({pos});
if(it!=s.end()&&it->l==pos)return it;
--it;
if(it->r<pos)return s.end();
R int l=it->l,r=it->r,v=it->v;
s.erase(it);
s.insert({l,pos-1,v});
return s.insert({pos,r,v}).first;
}
void assign(R int l,R int r)
{
set<node>::iterator itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert({l,r,0});
}
int sum(R int l,R int r)
{
R int res=0;
set<node>::iterator itr=split(r+1),itl=split(l);
for(set<node>::iterator it=itl; it!=itr; it++)
res+=it->v*(it->r-it->l+1);
return res;
}
signed main()
{
read(n);read(m);++n;
s.insert({1,n,1});
while(m--)
{
R int x,y;
read(x);read(y);
assign(x+1,y+1);
}
printf("%lld\n",sum(1,n));
return 0;
}总结
本文简单介绍了几种解法来解决此题
题外话
数据太水了，所以这几种做法的速度都很快
附上提交记录叭…
