2020.06.27

~~菜到抠，连数字三角形都写挂了~~

T1. 看电影

Description：

听说NOIP2016大家都考得不错，于是CCF奖励省常中了 K 张变形金刚5的电影票奖励OI队的同学去看电影。可是省常中OI队的同学们共有 N（N K）人。于是机智的你想到了一个公平公正的方法决定哪K人去看电影。

N个人排成一圈，按顺时针顺序标号为1 - N，每次随机一个还存活的人的编号，将这个人踢出。继续上述操作，直到剩下K个人。

但这样显然太无聊了，于是小S又想出一个牛逼的方法。

N个人排成一圈，按顺时针顺序标号为1 - N，每次随机一个1 - N的编号，假设随机到的编号是X，如果编号为X人还未踢出，则将这个人踢出，否则看编号为X % N + 1（即顺时针顺序下一个编号）的人是否存活，如果还未踢出则将他踢出，否则继续看编号（X + 1）% N +　１的人，如果已被踢出看顺时针的下一个…………，以此类推，直到踢出一个人为止。重复上述操作，直到剩下K个人。

已知小S的编号是Id，问按照小S的方法来他有多少的概率可以不被踢出，成功得到看电影的机会。

刚开始没有头绪，就列了个概率式子。

然后手摸了几组，大胆猜个结论： $ans=\frac N K$ ，1e9的范围，看着就很结论。

补个证明：

对于n个人围成的环，被踢出的概率：

P(i)=\frac 1n+\frac 1n*\frac 2n+\frac 1n*(\frac 1n+\frac 1n*\frac 3n)\dots+\frac 1 n*(\frac 1n+\frac 1n*(\dots\frac k n))

或者令 $a_i$ 为id在第i轮被踢出的概率，用累加法求通项，再求和。得：

P(i)=\frac {n-k} n

所以存活概率为 $\frac k n$ 。

也可以大胆臆测这对每个人都是等价的，ID其实无关紧要。

T2.树塔狂想曲

Description:

相信大家都在长训班学过树塔问题，题目很简单求最大化一个三角形数塔从上往下走的路径和。走的规则是：（i，j）号点只能走向（i+1，j）或者（i+1，j+1）。如下图是一个数塔，映射到该数塔上行走的规则为：从左上角的点开始，向下走或向右下走直到最底层结束。

小S觉得这个问题so easy。于是他提高了点难度，他每次ban掉一个点（即规定哪个点不能经过），然后询问你不走该点的最大路径和。

当然他上一个询问被ban掉的点过一个询问会恢复.

考虑分拆，经过 $(i,j)$ 的最短路就是 $f1[i][j]+f2[i][j]-a[i][j]$ 。

其中f1，f2为向上，向下的最大路径。

每一层用前缀，后缀最大和计算不经过 $(i,j)$ 的最长路。

Ans[i][j]=\max(suf[j+1],pre[j-1])

循环利用数组suf和pre。

一定记住f2转移时不用判边界啊啊啊啊啊。

$100\rightarrow 35$ ，我菜死了。

T3.被粉碎的线段树

Description：

小S刚刚学习了一个牛逼（入门）的数据结构——线段树。你看他正兴高采烈的准备跟你讨论线段树的问题呢？

什么？你居然不知道什么是线段树，小S感到很吃惊，并向你作了如下解释：

（学过线段树的同学对下面的内容可以自行略过）

\1. 线段树有一个长度N。

\2. 线段树是一棵二叉树，每个节点都代表了一个闭区间。

\3. 我们递归定义这样一个线段树：

① 根节点代表的区间为

② 叶子节点代表的区间为，满足。

③ 那么对于所有非叶子节点来说，满足，并且：

设。

那么该节点的左节点代表的区间为，右节点代表的区间为。

4. 不难发现我们发现线段树有以下性质：

① 树的节点个数为。

② 树的深度不超过。

③ 区间定位所包含的线段树节点个数不超过。

*什么是区间定位：

用最少的线段树上节点表示的线段去拟合这个区间，每个点有且仅在这些线段中出现一次。

比如右图，区间的区间定位出的区间个数是3，分别是。

我们不难证明这样的区间定位是唯一的。

好了，相信你已经对线段树有所了解，但是小R的线段树没学好。于是他的线段树就有显得有些奇怪了。

他的线段树与传统线段树的唯一区别如下：

传统线段树非叶子节点的划分点，但小R线段树的划分点是自己定的。但满足，其余条件同原来线段树。

那么不难发现如下性质：

① 该线段树的节点个数依然为。

② 该线段树深度可能会超过。

③ 该线段树区间定位所包含的线段树节点个数可能超过。但区间定位的结果依然是唯一的。

小R给你这样一个小R线段树，每次询问给定区间的区间定位个数。