思路：
各种方法。
代码:
1.遍历树1 时间 0.314 s 平均内存 2.96 MB
#include<cstdio>
using namespace std;
const int N=; int n,Enum,cnt,H[N<<],fa[N],Ans;//,Dfn[N],Size[N];
struct Edge
{
int to,nxt;
}e[N<<]; int read()
{
int now=;bool f=;char c=getchar();
while(c<''||c>'')
{
if(c=='-')f=;
c=getchar();
}
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return f?-now:now;
} void AddEdge(int u,int v)
{
e[++Enum].to = v;
e[Enum].nxt = H[u];
H[u] = Enum;
} void DFS(int cur,int f,int cmp)
{
// Dfn[cur]=++cnt;//printf("%d:%d\n",cnt,cur);
for(int i=H[cur];i;i=e[i].nxt)
{
int to=e[i].to;//printf("%d OK\n",cur);
if(to!=f)
{
if(to<cmp) ++Ans;
DFS(to,cur,cmp);
// Ans[cur]+=Ans[to];
// Size[cur]+=Size[to]+1;
}
}
} int main()
{
// freopen("counttree.in","r",stdin);
// freopen("counttree.out","w",stdout);
n=read();
int sta;
for(int i=;i<=n;i++)
{
fa[i]=read();
if(fa[i]==) sta=i;
else AddEdge(fa[i],i),AddEdge(i,fa[i]);
}
// DFS(sta,0);
// printf("%d ",sta);
// for(int i=1;i<=n;i++)
// printf("%d ",Ans[i]);
for(int i=;i<=n;i++)
{
Ans=;
DFS(i,fa[i],i);
printf("%d\n",Ans);
}
fclose(stdin);fclose(stdout);
return ;
}
2.遍历父节点 时间 0.151 s 平均内存 1.05 MB
#include<cstdio>
using namespace std;
const int N=; int n,fa[N],Num[N]; int read()
{
int now=;bool f=;char c=getchar();
while(c<''||c>'')
{
if(c=='-')f=;
c=getchar();
}
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return f?-now:now;
} int main()
{
freopen("counttree.in","r",stdin);
freopen("counttree.out","w",stdout);
n=read();
for(int a,i=;i<=n;i++)
a=read(),fa[i]=a;
for(int i=;i<=n;i++)
{
int t=i;
while(fa[t])
{
if(fa[t]>i)
++Num[fa[t]];
t=fa[t];
}
}
for(int i=;i<=n;i++)
printf("%d\n",Num[i]);
fclose(stdin);fclose(stdout);
return ;
}
3.DFS序+树状数组（参考） 时间 0.154 s 内存使用 3.72MB
#include<cstdio>
using namespace std;
const int N=; int n,Enum,cnt,in[N],out[N],H[N<<],Tree[N];
struct Edge
{
int to,nxt;
}e[N<<]; int read()
{
int now=;bool f=;char c=getchar();
while(c<''||c>'')
{
if(c=='-')f=;
c=getchar();
}
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return f?-now:now;
} void AddEdge(int u,int v)
{
e[++Enum].to = v;
e[Enum].nxt = H[u];
H[u] = Enum;
} void DFS(int cur,int f)
{
in[cur]=++cnt;
for(int i=H[cur];i;i=e[i].nxt)
{
int to=e[i].to;
if(to!=f)
DFS(to,cur);
}
out[cur]=cnt;
} inline int lb(int x)
{
return x&-x;
}
void Update(int p,int v)
{
while(p<=n)
Tree[p]+=v,p+=lb(p);
}
int Query(int p)
{
int tmp=;
while(p)
tmp+=Tree[p],p-=lb(p);
return tmp;
} int main()
{
freopen("counttree.in","r",stdin);
freopen("counttree.out","w",stdout);
n=read();
int sta;
for(int a,i=;i<=n;i++)
{
a=read();
if(!a)
sta=i;
else
AddEdge(a,i),AddEdge(i,a);
}
DFS(sta,-);
for(int i=;i<=n;i++)
{
printf("%d\n",Query(out[i])-Query(in[i]-));
Update(in[i],);
}
fclose(stdin);fclose(stdout);
return ;
}
2.COGS.1682. [HAOI2014]贴海报
思路：
看到这题就想起zhx讲过，当时好像是用并查集做的？然而题目数据范围1e7，没敢用（也不知怎么写==），就用的分块（其实也是暴力，然而写错了点，比暴力还低4分）。
正解：1.线段树：维护区间是否被染色：区间修改没被染色的点，标记，++ans；如果区间的点全被染过色，那ans不变。
2.浮水法：网上并不能搜到很多东西。一篇有关博客：http://www.cnblogs.com/SueMiller/archive/2011/08/05/2128794.html
代码:
1.线段树：时间：0.127s 内存使用：38.44MiB
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=,M=; int n,m,Ans,A[M],B[M];
bool flag,colored[N<<]; int read()
{
int now=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return now;
} void PushUp(int rt)
{
colored[rt]= colored[rt<<]&&colored[rt<<|];
} /*void Build(int l,int r,int rt)
{
if(l==r)
return;
int m=(l+r)>>1;
Build(l,m,rt<<1);
Build(m+1,r,rt<<1|1);
PushUp(rt);
}*/ void Modify(int l,int r,int rt,int L,int R)
{
if(colored[rt]) return;
if(L<=l && r<=R)
{
flag=;colored[rt]=;
return;
}
int m=(l+r)>>;
if(L<=m) Modify(l,m,rt<<,L,R);
if(m<R) Modify(m+,r,rt<<|,L,R);
PushUp(rt);
} int main()
{
freopen("ha14d.in","r",stdin);
freopen("ha14d.out","w",stdout);
n=read();m=read();
// Build(1,n,1);
for(int i=;i<=m;i++)
A[i]=read(),B[i]=read();
for(int i=m;i>=;i--)
{
flag=;
Modify(,n,,A[i],B[i]);
if(flag) ++Ans;
}
printf("%d",Ans);
fclose(stdin);fclose(stdout);
return ;
}/*
1000 12
1 100
50 80
80 99
50 98
1 56
100 200
200 300
300 500
500 600
600 1000
260 560
160 580
*/
线段树
2.浮水法：时间：0.015s 内存使用：0.30MiB
#include<cstdio>
using namespace std;
const int N=,M=; int n,m,Ans,cur,A[M],B[M];
bool vis[M]; int read()
{
int now=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return now;
} void Solve(int a,int b,int now)
{
if(vis[cur]) return;
while(now<=m && (a>=B[now]||b<=A[now]))//需要等于
++now;
if(now>m)
{
++Ans,vis[cur]=;//printf("%d:%d--%d\n",Ans,a,b);
return;
}
if(a<A[now] && A[now]<b) Solve(a,A[now],now+);//不能等于
if(b>B[now] && B[now]>a) Solve(B[now],b,now+);
} int main()
{
// freopen("ha14d.in","r",stdin);
// freopen("ha14d.out","w",stdout);
n=read();m=read();
for(int i=;i<=m;i++)
A[i]=read(),B[i]=read(),++B[i];//右端点再加1，因为两端点是都不能放其他海报的(看不见)
for(cur=m-;cur>=;cur--)
Solve(A[cur],B[cur],cur+);
printf("%d",++Ans);
// fclose(stdin);fclose(stdout);
return ;
}
浮水法
3.76分的分块（懒得纠正了）
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=,M=; int n,m,Ans,Size,Blo[N],A[M],B[M];
bool flag,colblo[],colored[N]; int read()
{
int now=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return now;
} void Solve(int a,int b)
{
flag=;
int ba=Blo[a],bb=Blo[b];
if(!colblo[ba])
for(int i=a;i<=min(a*Size,b);i++)
if(!colored[i])
colored[i]=,flag=;
if(ba!=bb && !colblo[bb])
for(int i=(bb-)*Size+;i<=b;i++)
if(!colored[i])
colored[i]=,flag=;
for(int i=ba+;i<=bb-;i++)
if(!colblo[i])//当一些点把一整块覆盖时，无法有效判断.
colblo[i]=,flag=;
if(flag) ++Ans;//printf("l:%d r:%d\n",a,b);
} int main()
{
// freopen("ha14d.in","r",stdin);
// freopen("ha14d.out","w",stdout);
n=read();m=read();
Size=sqrt(n);
for(int i=;i<=n;i++)
Blo[i]=(i-)/Size+;
for(int i=;i<=m;i++)
A[i]=read(),B[i]=read();
for(int i=m;i>=;i--)
Solve(A[i],B[i]);
// printf("%d\n",Blo[n]);
// for(int i=1;i<=Blo[n];i++)
// printf("%d:All:%d\n",i,(int)colblo[i]);
printf("%d",Ans);
fclose(stdin);fclose(stdout);
return ;
}
76
3.COGS.1619. [HEOI2012]采花
思路：
一眼就看出是个莫队，然而之前没看我不会写==。果断三分钟敲出暴力。
正解：1.学了莫队 用莫队写了一遍，过了==好简单。。5s限时可以的。
2.树状数组：
这题首先在线是没法做的，所以我们可以考虑离线算法
首先记录下每种颜色的下一种颜色所在的位置
将所有询问按照左端点进行排序
将所有颜色的第一个点x a[x]++
然后从左往右扫
扫到一个点x将a[next[x]]++
碰到一个询问l,r输出sum[r]-sum[l-1]
其中sum是a数组的前缀和
求前缀和可以用树状数组（是不是很眼熟，没错摘自黄学长博客）
对于本题只需改一小部分。
代码:
1.莫队 时间：15.293s 内存使用：23.18MiB
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=; int n,c,m,size,color[N],Times[N],now,ans[N];
struct Ques
{
int l,r,id;
}q[N]; int read()
{
int now=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return now;
} bool cmp(Ques a,Ques b)
{//左端点所在块为第一关键字，右端点为第二关键字
//if((a.l-1)/size+1 == (b.l-1)/size+1) return a.r < b.r;
if(a.l/size == b.l/size) return a.r < b.r;
return a.l/size < b.l/size;
} inline void Add(int p)
{
++Times[p];
if(Times[p]==)
++now;
}
inline void Subd(int p)
{
--Times[p];
if(Times[p]==)
--now;
} int main()
{
freopen("1flower.in","r",stdin);
freopen("1flower.out","w",stdout);
n=read();c=read();m=read();
size=sqrt(n);
for(int i=;i<=n;i++)
color[i]=read();
for(int i=;i<=m;i++)
q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+,q++m,cmp);
for(int i=,l=,r=;i<=m;i++)
{
int ln=q[i].l,rn=q[i].r;
while(l>ln)
Add(color[--l]);
while(l<ln)
Subd(color[l++]);
while(r<rn)
Add(color[++r]);
while(r>rn)
Subd(color[r--]);
ans[q[i].id]=now;
}
for(int i=;i<=m;i++)
printf("%d\n",ans[i]);
fclose(stdin);fclose(stdout);
return ;
}
莫队
2018.2.26 Update:
+一些小优化
时间：10.803s 内存使用：16.89MiB
#include <cmath>
#include <cctype>
#include <cstdio>
#include <algorithm>
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=1e6+,MAXIN=1e6; int n,c,m,size,color[N],Times[N],now,ans[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Ques
{
int l,r,id;
bool operator <(const Ques &b)const{
return l/size==b.l/size ? ((l/size)&?r>b.r:r<b.r): l/size<b.l/size;
//左端点所在块为第一关键字，右端点为第二关键字
}
}q[N]; inline int read()
{
int now=;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*+c-'',c=gc());
return now;
}
inline void Add(int p){
if(++Times[p]==) ++now;
}
inline void Subd(int p){
if(--Times[p]==) --now;
} int main()
{
freopen("1flower.in","r",stdin);
freopen("1flower.out","w",stdout); n=read(),c=read(),m=read(),size=n/sqrt(m*/);
for(int i=;i<=n;i++) color[i]=read();
for(int i=;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
std::sort(q+,q++m);
for(int i=,l=,r=;i<=m;i++)
{
int ln=q[i].l,rn=q[i].r;
while(l>ln) Add(color[--l]);
while(l<ln) Subd(color[l++]);
while(r<rn) Add(color[++r]);
while(r>rn) Subd(color[r--]);
ans[q[i].id]=now;
}
for(int i=;i<=m;i++) printf("%d\n",ans[i]); fclose(stdin);fclose(stdout);
return ;
}
莫队2
2.树状数组 时间：2.226s 内存使用：30.81MiB
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=; int n,c,m,color[N],Tree[N],Last[N],Next[N],Ans[N];
struct Ques
{
int l,r,id;
bool operator <(const Ques &a)const
{
return l<a.l;
}
}q[N]; int read()
{
int now=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return now;
} inline int lb(int x)
{
return x&(-x);
} void Update(int p,int v)
{
while(p<=n)
Tree[p]+=v,p+=lb(p);
} int Query(int p)
{
int tmp=;
while(p)
tmp+=Tree[p],p-=lb(p);
return tmp;
} int main()
{
// freopen("1flower.in","r",stdin);
// freopen("1flower.out","w",stdout);
n=read();c=read();m=read();
for(int i=;i<=n;i++)
color[i]=read();
for(int i=n;i>;i--)
Next[i]=Last[color[i]],Last[color[i]]=i;
for(int i=;i<=c;i++)
if(Next[Last[i]])//颜色i第一个位置的下一个，即出现过2次，往后+1
Update(Next[Last[i]],);
for(int i=;i<=m;i++)
q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+,q++m);
for(int i=,l=;i<=m;i++)
{
while(l<q[i].l)
{
if(Next[l]) Update(Next[l],-);//颜色i第一次出现的位置，往后-1(不算在内)
if(Next[Next[l]]) Update(Next[Next[l]],);//颜色i第二次出现，往后+1
++l;
}
Ans[q[i].id]=Query(q[i].r)-Query(q[i].l-);
}
for(int i=;i<=m;i++)
printf("%d\n",Ans[i]);
// fclose(stdin);fclose(stdout);
return ;
}
树状数组
20分的暴力
#include<cstdio>
using namespace std;
const int N=; int n,c,m,Ans,color[N],Times[N];
bool vis[N]; int read()
{
int now=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')now=(now<<)+(now<<)+c-'',c=getchar();
return now;
} int main()
{
freopen("1flower.in","r",stdin);
freopen("1flower.out","w",stdout);
n=read();c=read();m=read();
for(int i=;i<=n;i++)
color[i]=read();
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
vis[j]=Times[j]=;
Ans=;
int l=read(),r=read();
for(int j=l;j<=r;j++)
{
if(vis[color[j]])continue;
++Times[color[j]];
if(Times[color[j]]>)
vis[color[j]]=,++Ans;
}
printf("%d\n",Ans);
}
fclose(stdin);fclose(stdout);
return ;
}