吕秋实

线段树qwq

懒标记qwq

树状数组qaq

有个性质是深度不同的点lowbit不同,然后每次加lowbit都会使得深度减少,也就是向上跳啦

点x维护的是x~x-lowbit的所有值

所以前缀求和就是一直减

二维树状数组可以每个维度都蹦lowbit就是先x维再y维

CF323C Two permutations

二维数点/ll我太菜了

对于值为x的点,第一维是他在第一个排列中出现位置,第二维就是第二个排列出现的位置

然后主席树实现在线数点吧

线段树合并

每次合并复杂度是公共节点的个数

然后你会发现我们每次合并公共节点减少一个

所以我们一共nlogn,均摊就是nlogn

李超树

支持插入直线,询问所有直线在x处最大值

线段树每个节点维护一个当前节点中最优霸占范围最大的直线

然后考虑到修改的时候,一个直线,我们先就考虑他和当前最优的那条的交点

钦点最优的是在mid处取值最大的那个,对于另外一个直线

如果在[l,r]外相交

不递归

如果在[l,mid]处相交

递归左边

如果在[mid+1,r]处相交

递归右边

会发现,一个节点的最优直线只有可能是祖先处出现,所以直接qwq即可

会发现如果交在mid,我们直接钦定最小的放在左边就好了qwq,这样总没错qwq

实在不行特判一下端点取值

分块

单点修改区间最小值

可以每次询问复杂度O(sqrt B) 修改O1

记住要维护块内前后缀以及块之间的前后缀qwq

每个点的集合是周围所有点的点权

然后查询一个点的集合的mex,以及修改一个点点权

我们安度数大小分块,考虑一个大点被修改

用值域分块,记录一个块是否是满的这个信息,然后我们大点修改只改哪些相邻大点

~~这个用线段树维护就是离谱啊 $\sqrt n log$ 还可以平衡复杂度~~

左端点最多移动qB次,右端点是 $n^2/B$ 次

B是 $\sqrt(n^2/q)$ 就能达到 $\sqrt(n^2q)$

第一个指针O(qB)

第二个指针 $O(qB+n^2/B)$

第三个是最多移动 $O(n^3/B^2)$

为什么呢?你考虑上一维一共有多少个块,然后一个块就会导致O(n)的移动复杂度

比如第三维的,有n^2/B2个块,然后再乘上n就是完蛋了

这个块大小取 $n^{2/3}$

k维莫队是 $O(n^{2-\frac{1}{k}})$

三维的....我们先按照第一维的块排,再按照第二维的块排,再按照第三位单调排

大概我们按照k-1维奇偶性,如果是奇数就从小到大,如果是偶数就从大到小qwq

树上莫队

欧拉序拿出来

大概只会维护一个路径(也就路径需要维护)

我们会发现,[l,r]从左向右出现第一次的我们加入,从左向右出现第二次的我们删除贡献

这个l,r有讲究

首先钦定 $begx<begy$

如果 $endx>endy$ ,那么说我们应该是祖先父子关系,此时我们加入区间是begx+1到begy,因为lca是x所以不会少算

否则就是相离的,此时是就是endx到begy相当于 $[l_1,r_1][l_2,r_2],r_1->l_2$

最后会发现反例是他们的lca,求出lca然后暴力加入即可

瓶颈在于维护这个贡献哎

wc2015糖果公园

树上带修莫队

就是直接做,如果出现两次考虑删除贡献,直接变换一个糖果的贡献就好了,删除当前糖果最后一次的那个贡献

因为说我们无论如果最后都是一个 $w_i$ 前缀和* $v_j$

splay

LCT必备树

虽然我看lct的splay和一般splay也不一样qwq

就是你画个图就是知道rotate了,注意有两个子树不变就是说有两个lct

splay也是一样相同的方向先旋转父亲这样子

fhqtreap

merge

首先合并只能合并权值左边最大值小于等于右边最小值的两棵树

然后我们合并的时候,你小于我显然可以我是父亲或者我是右儿子

这个直接随机化就好了

split

我们考虑看代码


inline void split(int now,int k,int &x,int &y) {
	if(!now)x=y=0;
	else {
		if(val[now]<=k) {
			x=now;
			split(rt[now],k,rt[now],y);
		} else {
			y=now;
			split(lt[now],k,x,lt[now]);
		}
		update(now);
	}
}

可持久化平衡树

用fhqtreap,因为他不旋转

很暴力,就是我们把merge和split经过的点全部新建

同时我们唯一不变的就是每个版本只用一个根,当然可能split多次导致建出许多彻底没用的点,不过多没关系

这只是常数qwq

因为我们之前不会TLE,那现在也不会TLE的

LCT

就是一个splay维护一个实链,实链里面按照深度排序节点

然后虚边连接了不同的splay的节点

虚边认父不认子

access

打通n到根,他们都变成实边

怎么做呢?先splayn,然后考虑把n接到的节点splay到根上,然后把他的右儿子改成n(n最深)

然后重复这个过程就好了

inline void access(int x) {
		for(int y=0; x; x=f[y=x]) {
			splay(x);
			//先splayx到根
			R=y;
			//x是新splay中那个要接上去的父亲
			//然后那个点要断实边啊
			//并把实儿子改掉
			pushup(x);
			//更新
		}
	}

makeroot

就是access后翻转整个树的深度

split(x,y)

makeroot一下x,然后access一下y即可qwq

link

makeroot一个点,然后另一个如果他的父亲不是y就连

割边可能不合法

判断x,y是否连通判断y的父亲是否是x,y的左儿子是否不存在

就是说防止我们x,y之间有别的点,这样割掉就玩完了

维护子树信息

要维护轻儿子的子树信息,和所有子树的子树信息

然后update的时候所有子树的信息=轻儿子的+所有重儿子的

维护轻儿子的,要在access的时候注意一下,减去原来的(x)加上新的(R)

同时link的时候要算上,因为我们link上的是虚边

然后这个所有子树的直接pushup就好了

ETT

平衡树维护欧拉序

link

移动一段子树的欧拉序

比如y是父亲,那么把x子树整段欧拉序插入到要连接的z的st后面

这个是区间分裂然后区间合并,可以用fhqtreap

KDtree

按照横坐标mid切一刀,把那个中间点拿出来做根,左右递归

然后第二层再按剩下的纵坐标最小值切一刀,左右递归

直到底部

可以用nth_element,他会把小于的分在左边

方法二是按照两维的极差,每一刀分这个极差较大的,这个是必然要用这个的

$O(kn^{1-1/k})$ 的

单点修改,矩阵查询

Q:因为每个点都代表了一个平面??

A:是的,一个点代表了子树x最大值/最小值,y最大值/最小值的这个矩阵

然后我们矩阵查询的时候,如果已经包括了整个矩阵,直接加上返回,如果矩阵完全没交集,直接返回

Q:如果多次插入就没多少次重构一下??

A:记录一个不平衡因子,(替罪羊树的)然后O(nlogn)重构就好,这个可能和重构的效率有要求

CF1149C Tree Generator™

一个区间代表的树链长度就是去掉所有匹配括号之后的剩余括号数量

不妨设区间前缀右括号数为b,左括号数为a,我们维护的是:)))))((((

同样维护一个后缀的c,d,那么合并带来的区间贡献就是max(a+b-c+d,a-c+b+d)

那么我们只需要维护每个区间的前后缀这玩意最大值就好了

lk的做法等价于线段树维护直径,这也是括号序列的性质之一吧

我们可以发现一个空白行一个空白列上所有点是本质相同的

因为到达这个点要么从空白行要么从空白列

一个空白行与所有相交空白列连边,最短路

不难发现这样等价于交换方向

所以是 $f(x,y)=min(dis(x,y,lie)+dis(x,y,hang))$

而这个东西根据最短路,我们有两个dis最多差1,又因为是二分图,所以不可能在同样的dis行列

所以f(x,y)=(dis(x,y,lie)+dis(x,y,hang)-1)/2

故我们只需要求出这个前面的和即可qwq

然而我们要优化一下建图过程

考虑主席树优化建图,用扫描线的思想从左向右扫描,然后如果某一行出现了,就对应叶子结点连边,消失了就断开对应的边

然后对于扫到的这一列,我们直接想对应节点连边就好,这一个查询我们不能建新点啊

相当于横着修改,竖着的变成查询,01最短路就是 $nlogn$

CF482E ELCA

靠树上差分就好了

$(siz^2-\sum siz^2)*a_i$

考虑这个怎么维护,LCT是要的,因为变化树的形态

然后我们发现相当于自己子树的siz^{2,虚子树的siz}2和这两个元素会发生变化,推一下变化式子就好了,还要维护子树的答案,方便查询

那么我们先打通这个点和其祖先,删掉这个点等价于改变它的父亲和他祖先的虚子树siz^2,同时虽然更改了整个向上的链的答案

但是你想我们的link和cut多强大啊,我还需要考虑你链的变化吗??

因为我们cut是保证了父亲是根而且和u直接相连接,所以根本不可能改变其他的点

同时link我们是把一个点makeroot后再弄得,所以也不可能改变其他的点,故我们也就只会影响y一个点

那么实际上我们也只需要看pushup函数咋写qwq


//你冷静思考这个怎么pushup啊冷静
//这个修改轻重变的时候冷静啊!!
//link cut 一定都是有的不用判掉
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 7;//4
int a[MAXN], n, m;
ll n2;
namespace fastIO {
#define BUF_SIZE (1<<20)
	char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = BUF_SIZE + buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;
char s[20];

namespace LCT {
#define L (ch[x][0])
#define R (ch[x][1])
#define F (fa[x])
	int ch[MAXN][2], fa[MAXN], tag[MAXN], st[MAXN]; //能没这个?
	ll sum[MAXN], ans[MAXN], sa[MAXN], sx1[MAXN], sx2[MAXN], ax[MAXN];
	inline bool nroot(int x) {
		return ch[fa[x]][0] == x || ch[fa[x]][1] == x; //看看!
	}
	inline void outmes(int x) {
		printf("Node :%d L: %d R: %d\n", x, L, R);
		printf("sum :%lld ans: %lld sa: %lld sx1: %lld sx2: %lld ax: %lld\n", sum[x], ans[x], sa[x], sx1[x], sx2[x], ax[x]);
		puts("\n");
	}
	inline void pushup(int x) {
		sum[x] = sum[L] + sum[R] + sx1[x] + 1;
		sa[x] = sa[L] + sa[R] + (sx1[x] + 1) * a[x];
		ans[x] = ans[L] + ans[R] + ax[x] + a[x] * ((sx1[x] + 1) * (sx1[x] + 1) - sx2[x]) +
				 2 * a[x] * (sx1[x] + 1) * sum[R] + 2 * sa[L] * (sum[R] + sx1[x] + 1);
	}
	inline void rotate(int x) {
		int y = F;
		int z = fa[y];
		int k = ch[y][1] == x;
		int w = ch[x][!k];
		if(nroot(y)) {
			ch[z][ch[z][1] == y] = x;//右儿子就是右儿子
		}
		ch[x][!k] = y;
		ch[y][k] = w;
		if(w)fa[w] = y;
		fa[y] = x;
		fa[x] = z;
		pushup(y);
	}
	inline void pushR(int x) {
		L ^= R ^= L ^= R;
		tag[x] ^= 1;
	}
	inline void pushdown(int x) {
		if(tag[x]) {
			if(L)pushR(L);
			if(R)pushR(R);
			tag[x] = 0;
		}
	}
	inline void outtree() {
		for(int i = 1; i <= n; ++i) {
			printf("%d %d %d %d\n", i, fa[i], ch[i][0], ch[i][1]);
		}
		return ;
	}

	inline void splay(int x) {//先下方
		int z = 0, y = x;
		st[++z] = y;
		while(nroot(y)) {
			st[++z] = fa[y];
			y = fa[y];
			// printf("ha ? %d ?\n", y);
		}
		while(z)pushdown(st[z]), z--;
		// outtree();
		while(nroot(x)) {
			y = F;
			z = fa[y];
			// printf("huaile : %d %d %d?\n", x, y, z);
			if(nroot(y)) {
				rotate((ch[y][1] == x) ^ (ch[z][1] == y) ? x : y);
			}//不一样两次x
			rotate(x);
		}
		pushup(x);
	}
	inline void add(int x, int y, int t) {
		sx1[x] += t * sum[y];
		sx2[x] += t * sum[y] * sum[y];
		ax[x] += ans[y] * t;
	}
	inline void access(int x) {
		for(int y = 0; x; x = F) {
			splay(x);
			// printf("access : %d %d %d %d\n", x, y, R, F);
			// outmes(y);
			add(x, R, 1);
			add(x, y, -1);
			R = y;
			pushup(x);
			y = x;
			// outmes(x);
		}
	}
	inline void makeroot(int x) {
		access(x);
		splay(x);
		pushR(x);
	}
	inline void split(int x, int y) {
		makeroot(x);
		access(y);
		splay(y);
	}//这个是用来解决链修改的
	inline void link(int x, int y) {//把y到x上去
		// printf("link :%d %d\n", x, y);
		access(x);//这个要小心,如果makeroot要findroot
		splay(x);
		splay(y);
		fa[y] = x;
		add(x, y, 1);
		pushup(x);
		// outmes(y);
		// outmes(1);
		// outmes(x);
		return ;
	}
	inline void cut(int x, int y) {
		access(x);//如果这里用makeroot
		//就要split了
		splay(x);
		access(y);
		splay(y);
		ch[y][0] = 0;
		fa[x] = 0;
		pushup(y);
		return ;
	}
	inline int chk(int x, int y) {
		access(y);
		splay(y);
		splay(x);
		return nroot(y);
	}
}

using namespace LCT;

inline void outans() {
	makeroot(1);
	printf("%lf\n", ans[1] / (1.0 * n2));//makeroot上去就行了
	return ;
}
int f[MAXN];
inline void init() {
	n2 = 1ll * n * n;
	pushup(1);
	for(int i = 2; i <= n; ++i) {
		pushup(i);
		link(f[i], i); // link
	}
	outans();
	return ;
}



int main() {
	scanf("%d", &n);
	for(int i = 2; i <= n; ++i)scanf("%d", &f[i]);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	init();
	scanf("%d", &m);
	for(int i = 1, x, y; i <= m; ++i) {
		scanf("%s", s);
		scanf("%d%d", &x, &y);
		if(s[0] == 'P') {
			if(f[x] == y || f[y] == x) {
				outans();
				continue;
			}
			if(chk(x, y))swap(x, y);
			// printf("is right ?%d %d\n", x, y);
			cut(f[x], x);
			f[x] = y;
			link(y, x);//y你来啦~
		} else {
			makeroot(x);
			access(x);
			splay(x);
			a[x] = y;
			pushup(x);
		}
		outans();
	}
	return 0;
}

这里坏了许多,如果你link的时候makeroot就会导致我们要findroot....

如果你cut的时候split....那还真可以吧,但是你要注意谁是父亲谁是儿子,以及他们的dfn序关系

而只要你用了makeroot,就一定要使用findroot了,不能直接accesssplay去link了!

但是最最重要的是,这道题是有根树你不能split也不能makeroot........

CF1192B Dynamic Diameter

题目名称就是动态直径,简单的很吧

dfn为下标建树,维护每个点的dis值

然后[l,r]上维护这个区间最远点对,合并区间的时候4个点对判断是否可能出现新的点对即可

这样复杂度是两个log的,如果我们可以加速这个lca或者dep查询过程就好了/kk

野鸡啼

$a_ix_j+b_i>=y_j,i<j$ 而i,j直接有一条i->j的边

问这样的图最长链

DAG

我们考虑对于 $dp_i=max(j<i,avi(j)))dp_j+1$

这个式子我们使用线段树套李超树维护,线段树维护这个节点的

相当于二分这个答案是否可行,然后用李超树维护这个可行性,单点查询最大的是否大于这个y

我们要最大的,所以用李超树维护对应区间所有线段构成的结构,查询单点最大值就好啦

时间复杂度 $O(nlog^2n)$ 这种从值域下手的解题思路也很不错

李队又切了

就是一车区间,每次问你与[l,r]相交的所有区间构成的数组的最长连续的1的长度

直接莫队+值域分块似乎可以做到 $O(n\sqrt m)$ ,移动到一个点就把所有这个端点在上面的区间判交即可

但是直接莫队可以TLE,因为我们区间都是[1,n]的话直接莫队时间复杂度是不对的,就是移动一次端点的时间复杂度是不对的

所以说我们可以势能均摊分块,每个点的势能是在上面的区间端点数+1,然后每根号的势能分一次块即可qwq

如果突然大于根号的势能,那我们一个点单独分一块就好了

这样发现在一个块内移动的复杂度还是 $O(q\sqrt n)$

一次块外移动是O(n)的,还是对的qwq

分块

考虑我们每根号n个进行一次回答询问

前根号n个会形成 $2\sqrt n$ 个段

然后我们拿一个指针扫,在这从所有段固定一个l,然后右端点单调向右这样扫,不难对于一个询问区间在l,r,首先设置他的答案 $[1,\sqrt n]$ 的前缀最大值和后缀最大值和中间段答案

而这样扫的复杂度是O(n)的!

同样的,我们进行这样的操作根号次

然后你会发现一个区间先得到了 $[1,\sqrt n]$ 的答案,然后得到 $[\sqrt n,\sqrt 2n]$ 的答案,然后我们就可以对于这两段答案合并,因为只需要第一段后缀最大值拼上第二段前缀最大值看能否更新答案

一直这样下去就好了,时间复杂度就是 $O(n\sqrt n + m \sqrt n)$

HDU 5118

计算每个点开始有多少个不同的字符串,设为dp值

$wson[i]$ 表示i向后转移到的dp值最大的那个点

然后考虑把这样的边是重边,其他的边就是轻边,以1为根向下跳,按照字典序找,每次查询就最多会跳log次轻边

而如果是重边,我们可能会一跳解千愁On,这是不行的,你会发现重边本质上是一个树形结构,也就是说我们每次向下跳最多跳log次

等等,向下跳??

你仔细思考,发现整张图可能有很多出度为0的点,那些点才是树根!,也就是说我们实际上从一向下爬还是向上跳

那么我们就爬到一个合法的位置,满足叶子里面的rank在一个范围内,然后再从那个叶子处开始找轻儿子重复这个过程就好了!!

时间复杂度O(qlognlogw),因为我们每跳轻儿子都会让轻儿子/2

BZOJ3786

直接ETT即可

查询这个点到根的路径和也是可以,欧拉序可以直接是一个正一个负吧qwq

然后都是到根的所以都是可以哒,直接一个前缀和就好啦

如果是任意的路径和有点那难度在于求动态lca,~~可以lct实现~~

bzoj3514/P4764 [CERC2014]Pork barrel

做法很巧妙,考虑一个边应该存在一个最优时刻 $y<x$ ,满足在 $y<l_i<=x,r_i>x$ 之间时x都会被选

这个结论很显然啊,因为相当于我们越向前越可能成环替换掉他,按照边权排序

暴力做法是从这个边向后找最小生成树成环的一刻,而且他要在环上吧

实际上我们直接把边权小于这个的边建一棵最大生成树就好了,然后这条边加进去成环就直接找到边权最大的那个改掉即可

找到每条边完蛋的时间后,就是一个二维数点问题,直接主席树即可

时间复杂度 $O(mlogn)$

夏晓光(loveJY)的博客

ZR省选讲课D1