wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

[动态开点线段树][学习笔记]

权值线段树所谓权值线段树，就是指线段树内存的是权值。好像是废话。给出一些数，要查询一个区间内的数的个数。这时可以用权值线段树，开个n(n为给出的数的最大值)个点的线段树。然后就能轻松的维护了当然树状数组更简单动态开点为什么要动态开点呢?当然是因为空间不够啊。比如还是上面那个例子。加入给出...

2018-12-10

0 1008

[动态开点线段树][学习笔记]

权值线段树所谓权值线段树，就是指线段树内存的是权值。好像是废话。给出一些数，要查询一个区间内的数的个数。这时可以用权值线段树，开个n(n为给出的数的最大值)个点的线段树。然后就能轻松的维护了当然树状数组更简单动态开点为什么要动态开点呢?当然是因为空间不够啊。比如还是上面那个例子。加入给出...

2018-12-10

0 636

[luogu5077][Tweetuzki 爱等差数列]

题目链接思路数学题首先列出等差数列求和的式子。 \[S = \frac{(n + m)(n - m + 1)}{2}(n为末项，m为首项)\] \[S * 2= (n + m)(n - m + 1)\] 若想让m更小，那么肯定要让等差数列中数字的数目更多。也就是让\((n - m + 1)...

2018-12-10

0 361

[luogu5077][Tweetuzki 爱等差数列]

题目链接思路数学题首先列出等差数列求和的式子。 \[S = \frac{(n + m)(n - m + 1)}{2}(n为末项，m为首项)\] \[S * 2= (n + m)(n - m + 1)\] 若想让m更小，那么肯定要让等差数列中数字的数目更多。也就是让\((n - m + 1)...

2018-12-10

0 0

[luogu1110][报表统计]

题目链接思路 set+map+优先队列就可以水过去。可以发现，每插入一个元素，都会使得操作2中原来相邻的那个差值消失，然后多了两个新的差值。对于新的差值，只要直接扔到优先队列里就好了。那么删除呢。可以用map记录一下当前元素被删除了多少次。然后查询的时候将被删除的跳过即可。对于操作3，只要将插...

2018-12-09

0 456

[luogu1110][报表统计]

题目链接思路 set+map+优先队列就可以水过去。可以发现，每插入一个元素，都会使得操作2中原来相邻的那个差值消失，然后多了两个新的差值。对于新的差值，只要直接扔到优先队列里就好了。那么删除呢。可以用map记录一下当前元素被删除了多少次。然后查询的时候将被删除的跳过即可。对于操作3，只要将插...

2018-12-09

0 374

[luogu3391][文艺平衡树]

题目链接思路 splay区间操作的裸题。假如要对l-r这段区间操作，那么就先把l-1伸展到根节点，然后把r +１伸展为根的儿子。这样r + 1的左儿子就是要操作的区间了。只要在上面打上标记，以后每次查询的时候pushdown一下。然后对于l-1和r+1节点可能不存在，所以可以放两个标兵元素...

平衡树 splay

2018-12-09

0 444

[luogu3391][文艺平衡树]

题目链接思路 splay区间操作的裸题。假如要对l-r这段区间操作，那么就先把l-1伸展到根节点，然后把r +１伸展为根的儿子。这样r + 1的左儿子就是要操作的区间了。只要在上面打上标记，以后每次查询的时候pushdown一下。然后对于l-1和r+1节点可能不存在，所以可以放两个标兵元素...

平衡树 splay

2018-12-09

0 348

[Splay][学习笔记]

胡扯因为先学习的treap，而splay与treap中有许多共性，所以会有很多地方不会讲的很细致。关于treap和平衡树可以参考这篇博客关于splay splay,又叫伸展树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert...

2018-12-09

0 433

[bzoj1116][POI2008][CLO]

题目链接思路可以先考虑一棵树如图，如果是一棵树我们肯定会想这样子做，但是现在根没有入度。所以现在需要再加入一条边使他变成基环树。假如现在加入一条边\(3-2\)，那就会出现一个3-1-2-3的环。然后以这个环上的点为根，就可以找到很多棵满足条件的树可以发现，这样就解决了根没有入度的...

2018-12-02

0 491