HBC236066[SHOI2013]扇形面积并,二分,树状数组,数据结构,分治Pass the Ball!题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

n balls. Both children and balls are numbered from. . It is guaranteed that no child will pass his ball to himself, which means. =i. Moreover, we also know that after each round, each child will hold exactly one ball.

There are n n children playing with n n balls. Both children and balls are numbered from 1 1 to n n. Before the game, n n integers p_1, p_2, cdots, p_n p 1 ​ ,p 2 ​ ,⋯,p n ​ are given. In each round of the game, child i i will pass the ball he possesses to child p_i p i ​ . It is guaranteed that no child will pass his ball to himself, which means p_i neq i p i ​  ​ =i. Moreover, we also know that after each round, each child will hold exactly one ball. Let b_i b i ​ be the ball possessed by child i i. At the beginning of the game, child i i ( 1 le i le n 1≤i≤n) will be carrying ball i i, which means b_i=i b i ​ =i initially. You're asked to process q q queries. For each query you're given an integer k k and you need to compute the value of sumlimits_{i=1}^{n} i times b_i i=1 ∑ n ​ i×b i ​ after k k rounds.

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC236066[SHOI2013]扇形面积并 二分 树状数组 数据结构 分治Pass the Ball!题解