蓝桥历年试题 套娃

时间：2020-11-25 18:48:48


标题：套娃

作为 drd 送的生日礼物，atm 最近得到了一个俄罗斯娃娃。他对这个俄罗斯娃娃的构造很感兴趣。

俄罗斯娃娃是一层一层套起来的。假设：一个大小为 x 的俄罗斯娃娃里面可能会放任意多个大小小于 x 的俄罗斯娃娃（而市场上的套娃一般大娃里只能放一个小娃）。

drd 告诉 atm ，这个俄罗斯娃娃是由 n 个小娃娃组成的，它们的大小各不相同。 我们把这些小娃娃的大小从小到大依次记为 1 到 n 。

如果 atm 想观赏大小为 k 的小娃娃，他会先看这个小娃娃是否已经在桌子上了。 如果已经在桌子上，那么他就可以观赏了。否则他就打开桌子上某一个俄罗斯娃娃，将它套住的所有的小娃娃拿出来，摆在桌子上。
一开始桌子上只有 drd 送的大小为 n 的娃娃。注意，他只会将其中所有小娃娃拿出来，如果小娃娃里面还套着另外的小娃娃，他是不会将这些更里层的这些小娃娃拿出来的。
而且 atm 天生具有最优化的强迫症。他会最小化他所需要打开的娃娃的数目。

atm 是一个怪人。有时候他只想知道观看大小为 x 的娃娃时需要打开多少个娃娃（但并不去打开）；有时候听 drd 说某个娃娃特别漂亮，于是他会打开看。现在请你输出他每次需要打开多少个娃娃。

【输入格式】
第一行两个数 n m ，表示娃娃的数目以及 atm 想看的娃娃的数目。
接下来 n - 1 行，每行两个数 u v，表示大小为 u 的娃娃里面套着一个大小为 v 的娃娃。保证 u > v 。
接下来 m 行，每行形如：
P x ：表示 atm 一定要看到大小为 x 的娃娃；
Q x ：表示 atm 只想知道为了看大小为 x 的娃娃，他需要打开多少个娃娃，但实际上并不打开他们。

【输出格式】
输出 m 行。对应输入中P操作或Q操作需要打开（或假想打开）多少个俄罗斯娃娃。

【样例输入】
5 5
5 3
5 4
3 2
3 1
Q 1
Q 4
P 2
Q 1
Q 4

【样例输出】
2
1
2
0
0

【数据范围】
对于 30% 的数据：n, m <= 1000
对于 100% 的数据：n, m <= 100000

　　这题想到思路实现后提交一直不对，在搞到后台数据后发现数据出错了。不知道我打的程序对不对，不过思路我觉得应该就是这样，毕竟是和qducxk讨论出来的。

　　首先可以看出，数据建出来是一棵树，然后Q就是看这个节点的层数（默认根节点层数是0），然后P无非就是拆树，从x点开始往上找到最上面的节点，然后把它相连的边都拆掉，然后再向下更新子树，在更新子树这里如果每次都再跑一遍树的话，肯定会超时的，我们就想到了树上的区间修改，那就是记录下dfs序，然后拆掉这个点就是对子树的节点层数都-1，因为每条边只能被拆一次，更新又是nlogn，所以时间复杂度肯定是可以的。

蓝桥历年试题 套娃蓝桥历年试题 套娃
  1 #include<cstdio>
  2 #define L(x) (x<<1)
  3 #define R(x) (x<<1|1)
  4 #define M(x) ((T[x].l+T[x].r)>>1)
  5 const int N=200118;
  6 struct Side{
  7     int v,ne;
  8 }S[N];
  9 struct Tree{
 10     int l,r,lazy,rank;
 11 }T[N<<2];
 12 char op[3];
 13 int sn,tid,head[N],fa[N],num[N],in[N],out[N],nid[N];
 14 void init(int n)
 15 {
 16     sn=tid=0;
 17     for(int i=0;i<=n;i++)
 18         head[i]=-1;
 19 }
 20 void add(int u,int v)
 21 {
 22     S[sn].v=v;
 23     S[sn].ne=head[u];
 24     head[u]=sn++;
 25 }
 26 void dfs(int u)
 27 {
 28     int v;
 29     in[u]=++tid;
 30     nid[tid]=u;//记录这个dfs序相应的编号 
 31     for(int i=head[u];~i;i=S[i].ne)
 32     {
 33         v=S[i].v;
 34         fa[v]=u;
 35         num[v]=num[u]+1;
 36         dfs(v);
 37     }
 38     out[u]=tid;
 39 }
 40 void built(int id,int l,int r)
 41 {
 42     T[id].l=l,T[id].r=r;
 43     T[id].lazy=0;
 44     if(l==r)
 45     {
 46         T[id].rank=num[nid[l]];//初始的深度 
 47         return ; 
 48     }
 49     built(L(id),l,M(id));
 50     built(R(id),M(id)+1,r);
 51 }
 52 void down(int id)
 53 {
 54     T[L(id)].lazy+=T[id].lazy;
 55     T[R(id)].lazy+=T[id].lazy;
 56     T[id].lazy=0;
 57 }
 58 void updata(int id,int l,int r)//区间懒标记更新 
 59 {
 60     if(T[id].l>=l&&r>=T[id].r)
 61     {
 62         T[id].lazy++;
 63         return ;
 64     }
 65     if(T[id].lazy)
 66         down(id);
 67     if(l<=M(id))
 68         updata(L(id),l,r);
 69     if(r>M(id))
 70         updata(R(id),l,r);
 71 }
 72 int query(int id,int pos)//单点查询 
 73 {
 74     if(T[id].l==pos&&T[id].r==pos)
 75     {
 76         T[id].rank-=T[id].lazy;
 77         T[id].lazy=0;//记得清空标记 
 78         return T[id].rank;
 79     } 
 80     if(T[id].lazy)
 81         down(id);
 82     if(pos<=M(id))
 83         return query(L(id),pos);
 84     else 
 85         return query(R(id),pos);
 86 }
 87 void dfs1(int u)
 88 {
 89     if(fa[u])
 90         dfs1(fa[u]);//上面还有节点，继续往上 
 91     int v;
 92     //往下拆边 
 93     for(int i=head[u];~i;i=S[i].ne)
 94     {
 95         v=S[i].v;
 96         updata(1,in[v],out[v]);//整个子树的层数都减1 
 97     }
 98     head[u]=-1;
 99     out[u]=in[u]; 
100 }
101 int main()
102 {
103     int n,m,u,v,x;
104     scanf("%d%d",&n,&m);
105     init(n);
106     for(int i=1;i<n;i++)
107     {
108         scanf("%d%d",&u,&v);
109         add(u,v);
110     }
111     num[n]=fa[n]=0;
112     dfs(n);
113     built(1,1,n);
114     while(m--)
115     {
116         scanf("%s%d",op,&x);
117         printf("%d\n",query(1,in[x]));
118         if(op[0]=='P')
119             dfs1(fa[x]);
120     }
121     return 0;
122 }
套中套
标签：

相关文章