[COCI2010-2011#7] UPIT

约定:视\(n,q\)同阶

看一下题目的操作

1.区间赋值

2.区间差分加

3.插入元素

4.区间查询

我们知道1,2操作都是可以用懒标记维护的，具体过程可能有一点细节

1.记录区间差分加的过程，要记录等差数列首项和公差，两个等差数列相加直接首项和公差都相加即可

2.区间赋值的优先级要高于加法，即打上赋值标记就要清空加法标记，标记下传时注意先下传赋值标记

然后具体问题落到如何实现插入元素这个操作上

块状链表

对于静态的数组，可以直接静态分块来做

而要动态插入时，找到对应块，插入即可，但是涉及到编号问题

所以需要每个块维护一个\(Size\)，块内每个元素维护一个标号\(id_i\)

同时需要对于块的\(Size\)累前缀和\(SumSize\)，则块\(i\)内编号为\(j\)的元素在数组中的实际编号为\(SumSize_{i-1}+j\)

插入时把整个块内的元素取出重新标号即可

但是这样插入后，一个块的\(Size\)会变大，再实现分块的操作时复杂度没有保证

因此需要加入一个操作:当\(Size_i>2\sqrt n\)时,\(O(n)\)重构整个序列，这样每\(\sqrt n\)次插入操作会导致一次重构，复杂度为均摊的\(O(n\sqrt n)\)

然后可以用类似分块的方法来直接维护

线段树

静态的操作线段树可以直接维护

在线段树上额外维护一个01，表示这个元素是否出现

将插入操作转化为在让对应位置的0变为1，但是由于不知道插入后的位置，所以不能直接操作

于是有两种解决办法

暴力值域

静态情况下我们对于\([1,n]\)建树，但是动态可以对于\([1,n\cdot q]\)建函数式线段树

离线

离线维护，预处理出插入的位置

平衡树

下面是安利时间

来学Treap吧

它可以

1.查询k大

2.插入元素

3.区间修改

4.区间翻转

5.可持久化!!

6.吊打Splay

Treap 即树堆，意思是在满足二叉查找树的性质同时满足二叉堆的性质

给定每个节点一个额外的随机权值，让二叉查找树对于这个权值满足堆的性质即可

这样构造的二叉查找树，树高是\(O(\log n)\)的

带旋Treap

像普通二叉查找树一样每次插入节点到叶子位置后，可能不满足二叉堆的性质，因此需要不断向上zig/zag来调整满足

区间操作可以尝试像写线段树一样写

但是它不可持久化

非旋Treap

维护两个基础操作

1.平衡树合并，操作需要满足两棵树的大小顺序确定，返回新的根

2.平衡树分裂为\([1,d],[d+1,n]\)的两部分，返回两棵树的根

1.合并操作\(x,y\)

按照节点的权值比较谁是平衡树的根，然后将根的左/右子树与另一棵树合并作为新的子树，递归实现

2.分裂\(x,d\)

维护\(Size\)判断是要分裂左子树还是右子树，将子树分裂得到的部分作为\(x\)新的子树，递归实现即可

typedef pair <int,int> Pii;
#define mp make_pair
int Union(int x,int y) {
	if(!x || !y) return x|y;
	Down(x),Down(y);
	if(key[x]<key[y]) return rs[x]=Union(rs[x],y),Up(x),x;
	return ls[y]=Union(x,ls[y]),Up(y),y;
}

Pii Split(int x,int d){
	if(!x) return mp(x,x);
	if(sz[x]<=d) return mp(x,0);
	if(d==0) return mp(0,x);
	Down(x);
	if(sz[ls[x]]+1<=d) {
		Pii y=Split(rs[x],d-sz[ls[x]]-1);
		return rs[x]=y.first,Up(x),mp(x,y.second);
	} else {
		Pii y=Split(ls[x],d);
		return ls[x]=y.second,Up(x),mp(y.first,x);
	}
}

插入操作可以分裂前\(k\)个，将新节点和得到的两棵树按次合并

区间更新可以分裂两次，将对应区间的子树操作即可

[COCI2010-2011#7] UPIT

原文：https://www.cnblogs.com/chasedeath/p/13564451.html