某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第i个装置时，它会往后弹 $k_i$ 步，达到第 $i + k_i$ 个装置，若不存在第 $i + k_i$ 个装置，则绵羊被弹飞。绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：

+ $u$ $v$ $c$：将u到v的路径上的点的权值都加上自然数c；

- $u_1$ $v_1$ $u_2$ $v_2$：将树中原有的边 $(u_1,v_1)$ 删除，加入一条新边 $(u_2,v_2)$，保证操作完之后仍然是一棵树；

* $u$ $v$ $c$：将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$；

/ $u$ $v$：询问 $u$ 到 $v$ 的路径上的点的权值和，求出答案对于 $51061$ 的余数。

辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

Link-Cut Tree学习总结

在数据结构中有一类问题叫做动态树问题（DynamicTree），它会要求你对一颗树进行切割和拼接，然后再在上面维护传统的数据结构能维护的值，为了完成这一类问题，就有了很多相应的算法来解决这类问题，Link-Cut Tree 就是其中一种比较方便实用的算法。

兔子们在玩 $k$ 个串的游戏。首先，它们拿出了一个长度为 $n$ 的数字序列，选出其中的一
个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。

兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第
$k$ 大的和是多少。

在进行算法设计时，我们常用的两种线性数据结构是数组和链表。它们各有优缺点。数组特点是元素在内存中紧挨着存储，因而优点是定位快 $O(1)$，缺点是插入删除慢 $O(n)$；而链表则不同，它通过指针将不同位置的元素链接起来，因而优缺点与数组正好相反：定位慢 $O(n)$，插入删除快 $O(1)$。而块状链表，它将数组和链表的优点结合来，各种操作的时间复杂度均为 $O(\sqrt n)$。

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A1, A2, … An}. Then the host performs a series of operations and queries on the sequence which consists:

树堆，在数据结构中也称 $Treap$，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为 $O( \log n )$。

相对于 $AVL$ 和红黑树，其实现简单，相对于 $Splay$，其效率更高，相对于替罪羊和 $SBT$，其适用范围更广(尤其是非旋转式Treap)。

这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

对于序列A，它的逆序对数定义为满足 $i < j$，且 $A_i > A_j$ 的数对 $(i, j)$ 的个数。给 $1$ 到 $n$ 的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

维护一个 $W * W$ 的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数 $M <= 160000$,询问数 $Q <= 10000,W <= 2000000$.

静态内存指针版动态开点线段树…(这名字有毒)

自行修改 $pushDown$ 和 $update$ 等…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct Node {
    Node *lc, *rc;
    int l, r;
    long long val;
    int tag;
    inline void clear() { val = tag = 0; }
    inline void cover(const int delta) { tag += delta, val += (long long)delta * (r - l + 1); }
    inline void pushDown() { if (tag) lc->cover(tag), rc->cover(tag), tag = 0; }
    inline void update(const int l, const int r, const int delta) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) cover(delta);
        else pushDown(), lc->update(l, r, delta), rc->update(l, r, delta), val = lc->val + rc->val;
    }
    inline long long query(const int l, const int r) {
        register long long ret = 0;
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return val;
        else return pushDown(), ret += lc->query(l, r), ret += rc->query(l, r), ret;
    }
} pool[(MAXN + 10) << 4], *root, *tail = pool;
inline void build(Node *&rt, const int l, const int r, int *a) {
    rt = tail++, rt->clear(), rt->l = l, rt->r = r;
    if (l == r) { rt->val = a[l]; return; }
    register int mid = l + r >> 1;
    build(rt->lc, l, mid, a), build(rt->rc, mid + 1, r, a);
    rt->val = rt->lc->val + rt->rc->val;
}

$AA$ 树是 $Arne Andersson$ 教授在他的论文 $”Balanced search trees made simple”$ 中介绍的一个红黑树变种，设计的目的是减少 $RB$ 树考虑的 $cases$。

排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回$10$ 条记录。

给定一个含有 n 个数的序列 a[1],a[2],a[3], … ,a[n]，程序必须回答这样的询问：对于给定的 i,j,k，在 a[i],a[i+1],a[i+2], … ,a[j] 中第 k 小的数是多少 (1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列 a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数 n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有 n 个数，表示 a[1],a[2]……a[n]，这些数都小于 10^9。接下来的 m 行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1） 表示询问指令，询问 a[i]，a[i+1]……a[j] 中第 k 小的数。C i t (1≤i≤n，0≤t≤10^9) 表示把 a[i] 改变成为 t。

兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游，为了方便，他们在县内的N个旅游景点上建立了n-1条观光道，构成了一棵图论中的树。同时他们推出了M条观光线路，每条线路由两个节点x和y指定，经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。
你和你的朋友打算前往兵库县旅游，但旅行社还没有告知你们最终选择的观光线路是哪一条（假设是线路A）。这时候你得到了一个消息：在兵库北有一群丧心病狂的香菜蜜，他们已经选定了一条观光线路（假设是线路B），对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路，比如有四个景点1-2-3-4，而【精神污染】的路径是1-4，那么1-3,2-4,1-2等路径也被视为被完全污染了。
现在你想知道的是，假设随便选择两条不同的路径A和B，存在一条路径使得如果这条路径被污染，另一条路径也被污染的概率。换句话说，一条路径被另一条路径包含的概率。