青竹qingzhu

技巧

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

全部文章 / 技巧（共3篇）

康托展开——全排列的本质

康托展开——全排列的本质参考链接 X=a[n]* (n-1)!+a[n-1] * (n-2)!+…+a[i] * (i-1)!+…+a[1]*0! 1.求一个排列是原排列的按字典序的第几个排列。 #include<cstdio> #include<iostream> u...

2020-07-13

0 451

K小数查询求k小数的非主席树做法

题目链接题意给出一个长度为 n 的数列 A，接下来有m 次操作，操作有两种： 1 l r x，表示对i属于[l,r]，令Ai = min(Ai,x) 2 l r k，表示询问区间[l,r]中第k小的数。思路第k小的数，也就是说小于第k小的有k-1个，考虑二分加分块，分块询问的时候求的是小于m...

2020-07-13

0 441

最大子矩形问题

大佬博客讲解算法一 O（S^2），S是障碍点的个数。算法思想：以每个障碍点作为极大子矩形的左边界和右边界，枚举所有的极大子矩形，再找出最大的子矩形，最后还要算一下遗漏的以范围内的左边界和右边界为极大子矩形的左右边框的矩形大小。 P1578 奶牛浴场题目描述由于John建造了牛场围栏，激起...

2020-07-13

0 648