menu zcmimi's blog

arrow_back 数据结构

SPOJ的GSS系列是关于区间统计技巧的集合

GSS1,GSS3: 最大子段和:

每个节点记录区间和,最大后缀和,最大前缀和,答案

```cpp node operator+(node x,no

zcmimi
2020-05-25 19:22

简介

k-D Tree(KDT,k-Dimension Tree)是一种可以高效处理k维空间信息的数据结构。

[维基百科](https://wiki.zcmimi.workers.d

zcmimi
2020-04-14 10:26

link-cut tree是一个挺复杂的东西,本文主要用于复习巩固link-cut tree

推荐:

zcmimi
2020-03-29 16:58

此题非常之毒瘤,我写的整个人都二逼了

共有一下几种解法:

  1. 树状数组套线段树
  2. 线段树套平衡树
  3. 权值线段树套平衡树
  4. 分块
  5. 整体二分

树状数组套线段树

离散化+树

zc
2020-03-27 20:17

整体二分是离线算法

顾名思义就是将所有答案一起二分

solve(l,r,st,ed)表示答案在[l,r],解决第sted个询问或操作

以静态区间第k小为例,[LG P383

zcmimi
2020-03-25 17:13

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2020-03-23 08:44

允许离线处理

可以看成三维偏序(坐标和时间)

考虑如果要求的点都在当前点的左上方

那么也就是要求x_j\le x_i,y_j\le y_i,time_j\le time_i

$xi+y

zc
2020-03-21 23:31

```cpp

include<bits/stdc++.h>

typedef long long ll;typedef double db;typedef unsigned long long ull

zc
2020-03-20 21:22

二维偏序

先按 第一维 排序, 第二维 用数据结构维护

例题: [SHOI2007]园丁的烦恼

离线

zcmimi
2020-03-20 20:36

总结一下各种启发式合并

什么是启发式合并

可以算是一种技巧

比如要合并集合A,B,设|A|<|B|

这时候将 向B中插入A 的效率要比 向A插入B

这就是启

zcmimi
2020-03-01
1 / 2
Search
search