wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

[主席树][学习笔记]

可持久化线段树可持久化线段树就是支持历史版本的查询和修改的线段树。主席树就是可持久化线段树的一种思想如果正常情况下我们想要保留每个历史版本的话。那么假如有n次操作，就要搞n棵线段树。但是我们发现，第i棵与第i-1棵线段树的大部分节点都是相同的，那么可不可以共用这些节点，从而减小时空复杂...

2018-12-11

0 376

[bzoj2588][ Count on a tree]

题目链接思路查询区间第k小，考虑主席树。因为是从u到v的简单路径上，考虑将路径分为从u到lca和从lca到v两部分。所以对于每个点都维护出从根节点到当前节点中的点。查询的时候只要用ans[u] + ans[v] - ans[lca] - ans[fa[lca]]就行了。也就是在主席树的查询代...

2018-12-11

0 379

[bzoj2588][ Count on a tree]

题目链接思路查询区间第k小，考虑主席树。因为是从u到v的简单路径上，考虑将路径分为从u到lca和从lca到v两部分。所以对于每个点都维护出从根节点到当前节点中的点。查询的时候只要用ans[u] + ans[v] - ans[lca] - ans[fa[lca]]就行了。也就是在主席树的查询代...

2018-12-11

0 427

[bzoj3524][Couriers]

题目链接思路观察这个\((r - l + 1)/2\)，很容易证明，如果一个数出现次数大于\((r - l + 1) / 2\)，那么这个区间内第\((r - l + 1) / 2 + 1\)大一定是这个数。所以只要用主席树查询出区间内第\((r - l + 1) / 2 + 1\)大,然后...

2018-12-11

0 371

[bzoj3524][Couriers]

题目链接思路观察这个\((r - l + 1)/2\)，很容易证明，如果一个数出现次数大于\((r - l + 1) / 2\)，那么这个区间内第\((r - l + 1) / 2 + 1\)大一定是这个数。所以只要用主席树查询出区间内第\((r - l + 1) / 2 + 1\)大,然后...

2018-12-11

0 431

[luogu3834][可持久化线段树 1(主席树)]

题目链接思路裸的主席树。查询的时候，通过相减求出区间内左子树中数的个数a。然后判断要查找的k是否比这个z要大。如果比这个值大，那么就去右子树中查找第k - z大，否则去左子树中查找第k大。代码 /* * @Author: wxyww * @Date: 2018-12-11 16:2...

2018-12-11

0 0

[luogu3834][可持久化线段树 1(主席树)]

题目链接思路裸的主席树。查询的时候，通过相减求出区间内左子树中数的个数a。然后判断要查找的k是否比这个z要大。如果比这个值大，那么就去右子树中查找第k - z大，否则去左子树中查找第k大。代码 /* * @Author: wxyww * @Date: 2018-12-11 16:2...

2018-12-11

0 371

[luogu3810][bzoj3262][陌上花开]

题目链接思路听说可以CDQ分治，然后我不会，所以我写树套树首先肯定先按照a拍个序。然后就成了在b，c这两个数组中查询了。用一个树状数组套treap来维护。当插入一个数的时候，就在树状数组的b这个位置的treap里加入一个c。然后查询的时候就直接把小于等于c的数的个数进行前缀和就行了。注意...

2018-12-11

0 412

[luogu3810][bzoj3262][陌上花开]

题目链接思路听说可以CDQ分治，然后我不会，所以我写树套树首先肯定先按照a拍个序。然后就成了在b，c这两个数组中查询了。用一个树状数组套treap来维护。当插入一个数的时候，就在树状数组的b这个位置的treap里加入一个c。然后查询的时候就直接把小于等于c的数的个数进行前缀和就行了。注意...

2018-12-11

0 469

[树套树][学习笔记]

思想树套树像他的名字一样，就是一棵树套另一棵树。用一棵外层树来维护一些区间之类的东西。然后外层树的每个节点都是一棵内层树。就这样一道模板题 bzoj3196 思路这是一道线段树套平衡树的模板题。外层用一棵线段树来维护区间操作。然后线段树的每个节点都是一棵平衡树操作1:查询从l到r中...

2018-12-11

0 376