Tree(DaShuiTi)【问题描述】给定一棵N个节点的树，每个点有一个权值，有M个询问(a,b,c)若a为1，回答b到c路径上的最小权值，若a为2，回答b到c路径上的最大权值，若a为3，回答b到c路径上的所有权值的中位数，k个数的中位数定义为从0到k-1编号从小到大排序后k/2号的那个数。【输入格式】第一行两个整数N，M第二行N个整数，v[1]~v[n]，代表每个节点的权值。接下来N-1行每行两个整数x，y代表x和y有一条边最后M行每行三个整数a，b，c，表示一组询问。【输出格式】共M行，每行一个整数，代表询问的答案。【样例输入】531324512244345115213315【样例输出】144【数据范围】共20个数据数据1~3N,M<=1000数据4~6N,M<=5000数据7~10N,M<=10000数据11~18N,M<=30000数据19~20N,M<=100000Solution：块状树的话也可以做。函数式线段树的做法比较容易，对于每个结点建立出从根到这个点所有权值的权值线段树。无论询问最大最小还是中位数我们都可以用询问第k小解决。我们找到x，y两点的lca，利用它们的三棵线段树进行二分即可。Missingonthetree时限：1.5s，内存限制：256M【问题描述】你有一棵以1号节点为根的有根树。。。【输入格式】第一行一个数n表示节点个数第2到n行，每行一个数x，第i行的x表示i节点的父亲为x接下来一个数m，表示操作与询问个数的总和接下来m行，每行的开头有1个数p若p为0，则接下来有2个数x，y，表示将x号节点的权值加上y若p为1，则接下来有3个数x，y，z，表示将x号节点到y号节点的这条链上的每个节点的权值加上z若p为2，则接下来有2个数x，y，表示将以x号节点为根的子树的每个节点的权值加上z若p为3，则接下来有2个数x，y，表示询问x号节点到y号节点的这条链上每个节点的权值和，你需要输出这个和若p为4，则接下来有2个数x，y，表示询问x号节点到y号节点的这条链上每个节点的权值的最大值，你需要输出这个最大值若p为5，则接下来有2个数x，y，表示将x号节点的父亲改为y号节点【输出格式】对于每个3与4操作，输出1行，表示答案【样例输入】3112123-1323【样例输出】-3【数据范围】保证任何时候每个节点的权值的绝对值小于400004%的数据n,m<=5另外12%的数据n,m<=10000另外40%的数据，没有5操作另外20%的数据，没有2操作100%的数据N<=50000，m<=100000Solution：Link-CutTree，对于0、1、3、4、5的操作都是lct的基本操作，不再赘述。对于第二个操作，对一棵子树加上一个值，我们可以在这棵子树的根结点打上一个标记，对于某一条链链形成的splay（我们默认左子树比较浅），在更新每个结点的时候我们看左子树是否有标记，有的话右子树以及当前这个结点用来更新答案的数据也进行相应的改变，并且更新完后这个标记再放到本身这个结点上。CatchThePenguins(ctps.cpp/c/pas)TimeLimit：2sMemoryLimit：256M【问题描述】Xyz带着他的教徒们乘着科考船一路破冰来到了南极大陆，发现这里有许许多多的企鹅。邪恶的Xyz想要抓很多企鹅回去开动物园，当宠物玩。但动物保护协会很快赶来，他必须尽快行动！我们把南极大陆看成一个三维直角坐标系。有N只企鹅，每只企鹅会在一定的时刻的出现，第i只企鹅在Ai时刻出现在坐标为(Bi,Ci,Di)的地方。Xyz要在某一时刻在某一地方(X,Y,Z)撒一张大网，将(0,0,0)到(X,Y,Z)这个大长方体里的企鹅全都网进去捕捉回家(还没出现的企鹅就不会被捉进去了)。为了快准狠而且保证不铺张浪费网，Xyz想知道不同时间不同地点撒网能抓到几个企鹅(这样的询问有Q个)。然后他再行动。【输入格式】第一行一个整数N表示企鹅个数。第二行到N+1行每行四个实数(Ai,Bi,Ci,Di)，表示企鹅的出现时间和位置第N+2行一个整数Q表示询问个数。接下来Q行每行四个实数(T,X,Y,Z)，表示询问的时间和位置。【输出格式】输出共Q行，每行一个整数，回答每个询问能抓到几个企鹅。【样例输入】1000021111.0111-1【样例输出】10【数据范围】共20个数据数据1~3N,Q<=1000数据4~6N,Q<=5000数据7~10N,Q<=10000数据11~14N<=30000,Q<=1