P2633 Count on a tree 题目链接 题目大意 给一棵树，有点权，每次询问，x到y路径上点点权的第k小是多少？ 强制在线， 题解 第k小，肯定会想到主席树。 但是怎么处理呢？ 数组中求区间第k小的方法是 把数组的每个前缀建个权值线段树，然后要查询 l~r 区间的值，就用r的权值线段树中的数量减去l - 1中的就好了。也就是T® - T(l - 1) 现在是在树里面。 方法是：根节点到每个点都建个权值线段树。（当然是主席树那样的，） 然后现在知道了根到每个点，怎么求一个路径上的？ 当然是 T(x) + T(y) - T(lca(x,y)) - T(fa(lca(x,y)))； 这...

Game 题目链接 题目大意  初始有n列木块，第 i 列有 a[i] 个。 有两种操作： 1 x y ： 向左推第x列的从下到上第y个，（如上图所示） 2 x ：查询第x列有多少个木块 题解 用平衡树维护，我用的是fhq treap （因为我只会这个，我好菜hhhh） 操作二就是找第x个值是多少，很简单。。 我这里是把树按大小分裂。第一个树L有x - 1个数，剩下的在另一棵树R里，然后把R再分裂，按1分裂，分裂成Y，Z。然后Y就只有x这个节点了。返回x的权值就好了。 看操作一： 往左推一下，然后设可以推动的这个区间是 l ~ r ，l 左边的第一个数是L。 于是 L这个位置的数量就加 l 位...

Permutation Counting 题目链接 题目大意 给一个只包含0、1，长度维n - 1的数组b， b[i] = 1 表示a[i] > a[i + 1] b[i] = 0 表示a[i] < a[i + 1] a数组是1~n的一个排列，问有多少种a数组。 题解 lg过的，我不会，我是真的菜，好难想啊 怎么根据这个01数组构造出来a数组？ 先给数组加入一个1，从 2~n 如果第 i 位是0，就在前一个后面某一个位置加入 i ，如果第 i 位是1，就在前一个加入的位置前面某一个地方加入 i 。 设得到的是数组c，然后a[ci] = i，就可以满足b数组。 为什么可以这样呢？ 就...

Mine Sweeper 题目链接 题目大意 扫雷，一个数字代表周围一圈里有多少个雷。 给出一个数N，代表所有数字的和。 让构造一个所有数字和是N的棋盘。 （雷的地方没有数字） 要求大小行、列都小于等于25 题解 艹，没有看数据范围是1000，还在想怎么能装下最多的，最多装多少。。 x代表炸弹.代表没有炸弹 由于 . 太小了，看不见，我们用@代替 n是1的情况：X@ n是2的情况：X@X n是3的情况：X@X@ 一次类推，可以得到n小于等于24的情况。（因为这个只是一行） 在一个九个格子的中间放一个，可以贡献8， 还有在右下角放一个贡献3， 所以可以把25以后的变成8x + 3y的形式。（y ...

Coin Game 题目链接 题目大意 有n台机器可以产生硬币，每一台机器按第一次产生a[i] 个硬币，按第二次产生b[i] 个硬币，按第三次又产生a[i] 个硬币， 之后再按就不会产生硬币了。 设按x次可以得到的最多的硬币数量是 f(x) ，问f(1) ^ f(2) ^ f(3) ^ …… ^ f(m); n范围：5e6 m：1.5 * 1e7 题解 把一个机器分成两个，a[i] 和 b[i] + a[i], 为什么可以这样分呢？ 按一次： a[i] 按两次：a[i] + b[i] 按三次：a[i] + a[i] + b[i] ; 然后可以排个序， O(m) 计算答案。 每次加入一个的时候，...

P2042 [NOI2005]维护数列 题目的链接 众多平衡树独爱fhq 题目 有好多种操作： 1、添加一堆数 2、删除一个区间里的数 3、把一个区间里的数全变成同一个数 4、反转一个区间 5、求区间和 6、求最大的连续子序列的和。 因为要求连续的子序列的和，就想到了线段树区间合并。 这个，，应该可以想到。 所以就维护 lnum,rnum,num 做的时候的zz问题 崩溃了~~ 做的时候 我tmd 崩溃了，， 快神经了啊 我 一、添加一堆数我刚开始一个一个添加，， 因为方便（tle） 二、反转一个区间的时候没有反转lnum，rnum 这个问题很愚蠢，很快找到bug 三、update的时候没有判...

E. Boboniu Walks on Graph 题目链接 题目意思 给一个有向图，在图上走的时候，出度为 i 的边，只能走到边权大小为第 ci 小的边上面，问c数组有多少种，要每个点都满足：从这个点开始走都可以回到这个点。 每个点的入度都小于等于9 题解 都可以回到这个点，，但是每个点的出边只能有一条，所以n个点，入度都为1。 因为入度都是小于10的所以可以暴力枚举一下c数组，然后check。 怎么check？ 只要按照枚举出来的 c 数组走，每个点的入度等于1就可以。 所以可以预处理一下，预处理入读为 i 的所有点走权值大小为 j 的时候，可以走到哪些点。 刚开始用的bitset，果断t...

Egor in the Republic of Dagestan 题目链接 题目大意 给一张有向图，边的边权只有0和1，让给点染色，点是0的点只能走边权是0 的边，点是1的点只能走边权是1的边， 有一个人要从1走到n，让给点染色，使这个人走不到n，如果不能让他走不到n，那就让他走的最短路距离最大。 输出最短路的距离和点权。 题解 目的是要把每个点走到n的最短路给封住， 建反向图，从n开始走，如果这是第一次走到点x，就把x的颜色变成跟这个边的颜色不同的颜色，因为第一次走到是最短距离，把这个最短距离封住就好。然后其他的就是最短路了。 为什么要倒着呢？因为这个点的颜色是根据下一个边定的。 #incl...

HDU - 4010 题目链接 题意 给一棵树，四个操作 1 x y x~y连一条边 2 x y 把x变成根，断开y跟他的父节点 3 w x y 把 x 到 y 路径上的点权加w 4 x y 查询 x ~ y 路径上的点权的最大值 我的zz问题 做这个题真的是脑抽 题要看对，2操作不是断开x跟y的边。题看错wa死了 2操作 void cut(int x,int y) {  makeroot(x); if(findroot(y) != x || node[y].fa != x || node[y].ch[0]) return; node[y].fa =0 ; node[x].ch[1] = 0;...

C. Fixed Point Removal 题目链接 题目大意 给一个数组，如果ai == i 那就可以删除ai , 之后后面的就可以并上来，也就是后面的下标都-1. 问最多可以删除多少个。 有m组询问 每次询问输入 x，y 就是 把前x个和后y个变成n + 1, 后，答案是多少。 瞎bb 单纯理一下思路。。 如果没有查询 可以注意到删掉后面的，对前面的没有影响。如果当前的 ai > i 那必不可能删除这个值了。所以应该从后往前删，如果当前的 ai <= i 并且 前面删除的个数大于等于i - ai 那这个值就一定可以删除。 有查询 有查询操作怎么办？ 把前x个后y个变成n + ...