<span>模拟40 题解</span>

非常显然的数据结构优化dp，

线段树下标为a的最小值，

要求支持区间最值，区间加，单点取max。

随便写下转移方程就好了。

树上数颜色？

但是要求了一个深度。

我的做法是将询问离线，

显然在一个询问中我们只关注每种颜色在该子树中出现的最低深度。

维护动态开点线段树，下标为颜色，维护每个颜色出现的最低深度，

同时将这个最低深度更新在一个树状数组里，树状数组的下标是深度。

因为数状数组是所有子树共用的，

考虑如何去掉其它子树的贡献，用天天爱跑步一题用到的思路：

在进入dfs时减去一个答案，退出dfs时加上一个答案，最终答案就是该子树的贡献。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 using namespace std;
 5 const int N=1e5+7;
 6 inline int read(register int x=0,register char ch=getchar(),bool f=0){
 7     while(!isdigit(ch)) f=ch=='-',ch=getchar();
 8     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
 9     return f?-x:x;
10 }
11 int n,m,tot;
12 struct Bit{
13     #define lowbit(x) (x&-x)
14     int s[N];
15     inline void add(int x,int val){
16         for(;x<=n;x+=lowbit(x)) s[x]+=val;
17     }
18     inline int query(int x){
19         int ans=0;
20         for(;x;x-=lowbit(x)) ans+=s[x];
21         return ans;
22     }
23     inline int query(int l,int r){
24         return query(r)-query(l-1);
25     }
26 }bit;
27 vector<pair<int,int> > ve[N];
28 int c[N],f[N],head[N],nxt[N],to[N],ans[N],dep[N],bl[N];
29 inline void add(int a,int b){
30     nxt[++tot]=head[a];
31     head[a]=tot;
32     to[tot]=b;
33 }
34 struct node{
35     node *lch,*rch;
36     int val;
37 }*root[N],pool[N*30],*ptr=pool;
38 void insert(node *&p,int pos,int val,int l,int r){
39     p=ptr++;
40     if(l==r){
41         bit.add(p->val=val,1);
42         return ;
43     }
44     int mid=l+r>>1;
45     if(pos<=mid) insert(p->lch,pos,val,l,mid);
46     else insert(p->rch,pos,val,mid+1,r);
47 }
48 node* merge(node *a,node *b,int l,int r){
49     if(!a) return b;
50     if(!b) return a;
51     if(l==r){
52         bit.add(max(a->val,b->val),-1);
53         a->val=min(a->val,b->val);
54         return a;
55     }
56     int mid=l+r>>1;
57     a->lch=merge(a->lch,b->lch,l,mid);
58     a->rch=merge(a->rch,b->rch,mid+1,r);
59     return a;
60 }
61 void dfs(int x){
62     for(unsigned int i=0;i<ve[x].size();++i) ans[ve[x][i].first]-=bit.query(dep[x],min(dep[x]+ve[x][i].second,n));
63     insert(root[x],c[x],dep[x],0,n);
64     for(int i=head[x];i;i=nxt[i]){
65         dep[to[i]]=dep[x]+1;
66         dfs(to[i]);
67         root[x]=merge(root[x],root[to[i]],0,n);
68     }
69     for(unsigned int i=0;i<ve[x].size();++i) ans[ve[x][i].first]+=bit.query(dep[x],min(dep[x]+ve[x][i].second,n));
70 }
71 int main(){
72     //freopen("x.in","r",stdin);
73     //freopen("me.out","w",stdout);
74     n=read(); m=read();
75     for(int i=1;i<=n;++i) c[i]=read();
76     for(int i=2;i<=n;++i) add(f[i]=read(),i);
77     for(int i=1,x;i<=m;++i){
78         x=read();
79         ve[x].push_back(make_pair(i,read()));
80     }
81     dfs(dep[1]=1);
82     for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
83     return 0;
84 }

View Code

正解是在线，然而没打，只能乱说：

首先将每个点拍在dfs序上。

如果不考虑深度，则子树中的每一个颜色应该只作出一次贡献，

直接在线段树该点对应dfs序上加减。

使用某个称为链并的做法，也就是维护一下lca，去除lca处重复的贡献。

如果考虑深度，问题就稍复杂一些，

考虑将上述的一些加减操作由深度从小到大加入。

同时以深度为时间戳，建可持久化线段树，线段树的下标仍然为dfs序。

于是可以在线回答。

先打了暴力，然后想dp。

打了样例的小表，然后就找出了规律。

其实不难想，dp以每个位置结束的不同长度的子序列，稍微去重一下就行。

模拟40 题解

A. 队长快跑

B. 影魔

C. 抛硬币