Rewinner

数据结构

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 未归档(70)

/ 注册

全部文章 / 数据结构（共16篇）

[CQOI2011]动态逆序对【主席树+树状数组】

传送门废话：这道题和当初队长他们去电子科技大学的校赛A题几乎是一样，这道题没有挂在他们的OJ上，无意之间发现了这道题，赶紧补一下。这道题的做法也太多了吧。。。。。分块会板子(这道题不会)，CDQ分治不会，只会大佬说的动态主席树板子题，然后拿来改一下就能过了。。。解题思路：求解逆序数，我们常常用到...

2019-05-09

0 490

P2617 Dynamic Rankings【动态第K大树状数组+主席树】

传送门中文题目，题意不再叙述！实现方法：静态第K大，我们利用就是前缀和的思想来建立的线段树，[L,R]的状态由R状态的线段树减去L-1状态的线段树得到的。既然就是前缀和而且存在修改操作，我们可以利用树状数组来解决这个问题。原本处于下标 i 的线段树代表[1 - i ]所有元素的线段树，那么在...

2019-05-09

0 501

Power OJ 2840 伯陵防线【可持久化线段树】

传送门废话一波：这道题是几个月前比赛的题，当时就我一个人开了这道题，我当时写的可持久化线段树，但是思维出错了，一直WA。这道题还可以用树状数组或者线段树来写，但是我想不到。。。。出题人博客：https://blog.csdn.net/swust5120166213/article/deta...

2019-05-08

0 480

SPOJ D-query 【可持久化线段树】

传送门题目描述：多次询问一个区间内不同数的数量。解题思路：一个区间内存在相同的数，所以我们的线段树就不能维护数，应该去维护下标?为什么去维护下标呢，就算一个数相同，但是它们的下标肯定是不同的，我们的线段树维护下标存在的情况。如果区间内存在重复的数，意味着不同下标对应相同的数，如果我们记录多个下...

2019-04-25

0 475

Count on a tree SPOJ - COT 【可持久化线段树树上第K小】

传送门题目描述：给你一个树，每个点有权值，多次询问两点之间的链的第k小权值掉入的坑：必须离散化，不离散化过不了，(第一反应用的二分答案，发现没有题目上没给数据范围，不离散化，会RE到死。。。)解题思路：我们每次儿子的状态室友父亲更新过来，我们要如何得到这条链的信息呢？首先LCA我们肯定是会用到的...

2019-04-24

0 557

2019年ICPC南昌网络赛 J. Distance on the tree【树链剖分/DFS序+可持久化线段树】

传送门题目描述：给你一个树，多次询问一条链上边权小于等于 k 边的数量。解题思路：树链剖分+可持久化线段树：主要是两个模板的合并使用，主要细节即可（可持久化主席树查询时注意时间戳）。 DFS序+可持久化线段树：每个儿子的状态都是由父亲得到的，我们只需要用父亲的状态来更新儿子即可，最后求一个L...

2019-04-24

0 454

牛客小白月赛9 树上求和【树链剖分模板】

传送门题目描述：给你一棵根为1的有N个节点的树，以及Q次操作。每次操作诸如: 1 x y：将节点x所在的子树的所有节点的权值加上y 2 x：询问x所在子树的所有节点的权值的平方和，答案模23333后输出输入描述：第一行两个整数N,Q 第二行N个整数，第i个表示节点i的初始权值接下来N...

2019-04-02

0 415

Code froces 1137B Camp Schedule 【贪心+KMP】

传送门题意：给你一个文本串a，和一个模式串b，你可以重组a，使a中出现b的次数最多，可以叠在一起（a：10101，b=101，b最多可以出现过2次）。思路：两个串里面只有 0 和 1 字符，我们需要记录 a 串中的 0 1个数。然后去构造 b 串，如果已经构造完一个 b 串了，我们想要 b...

2019-03-10

0 549

HDU 4639 离线树状数组

题目链接：传送门题意：给你一个 1—n 的排列，询问你区间 [ L,R ]中连续数的组数比如 1 4 3 5 6，就是3 （4 5 6一组，1 一组，3 一组）。 ///#include<bits/stdc++.h> ///#include<unordered_ma...

2019-01-25

0 471

HDU 4417 Super Mario 可持久化线段树

题意：询问区间[ L , R] 中比 H 小的数的个数，注意题目中给的区间是从0下标开始的。思路：用upper_bound跑出 H 的相对大小，去查找 L-1 和 R 时间戳小于H的的改变数量注意点：如果找到的H相对大小为0，就不用去寻找（否则会T），可以直接输出0即可。 ///#inc...

2019-01-24

0 600