数据结构问题总结

时间：2020-07-16 11:12:32 收藏：0 阅读：51

数据结构问题总结

线段树 && 树状数组

P1908 逆序对

这题太经典了，做法有很多，可以归并排序，可以树状数组，可以权值线段树，这里只说一下权值线段树的做法。权值线段树的作用是维护值域中每个数在序列中出现了多少次，所以其占用空间与值域很有关系。如果值域过大，我们需要离散化一下（就是排序一下，然后用二分查每个数的排名）。我们知道线段树之类的东西需要有询问或者修改操作才行，那么这个问题有什么询问和修改操作呢？可以这样想，我们每次往树中插入一个数，然后看看这个数和它前面的数能组成多少逆序对，那么修改就是插入数，查询就是看比这个数小的数现在出现了多少个，即每个数出现次数的前缀和，然后用目前已经插入的数的个数减去不大于它的数的个数，就是前面已经插入的比它大的数的个数，对于插入数，其实就是某个数出现次数+1，查询前缀和就不用说了。如果没接触过权值线段树的话，可能还是比较难想到这个做法的。在这里我贴上权值线段树的AC代码：

PS：我这个题卡了好久，离散化和二分，甚至单点修改都静态debug了好久，不过还好一发提交就AC了。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define ll long long
using namespace std;
const int N=5e5+9;
ll a[N],q[N];
ll f[4*N],n;
void pushup(ll k);
int cmp(const void *a,const void *b);
void modify(ll left,ll right,ll pos,ll k);
ll query(ll left,ll right,ll ql,ll qr,ll k); 
int main(){
	ll l,r,mid,pos,ans=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		q[i]=a[i];
	}
	qsort(q+1,n,sizeof(ll),cmp);
	for(int i=1;i<=n;i++){
		l=1;
		r=n;
		while(l<=r){
			mid=(l+r)/2;
			if(q[mid]<a[i]){ //找到离散化之后的数据 
				l=mid+1;
			} else {
				pos=mid;
				r=mid-1;
			}
		}
		modify(1,n,pos,1); //pos是a[i]离散化之后的数据 
		ans=ans+i-query(1,n,1,pos,1); //把前i个数里面小于等于pos的数据统计起来，i-cnt就是大于的个数  
	}
	printf("%lld\n",ans);
	return 0;
}
void pushup(ll k){
	f[k]=f[2*k]+f[2*k+1];
}
ll query(ll left,ll right,ll ql,ll qr,ll k){
	if(ql<=left && right<=qr){
		return f[k];
	}
	ll mid=(left+right)/2;
	ll ansleft=0,ansright=0;
	if(ql<=mid){
		ansleft=query(left,mid,ql,qr,2*k);
	}
	if(qr>mid){
		ansright=query(mid+1,right,ql,qr,2*k+1);
	}
	return ansleft+ansright;
}
void modify(ll left,ll right,ll pos,ll k){ //我发现我现在不会写单点修改了！！！
	if(pos<left || pos>right){
		return;
	}
	if(left==right && left==pos){
		f[k]++;
		return;
	}
	ll mid=(left+right)/2;
	if(pos<=mid){
		modify(left,mid,pos,2*k);
	} else {
		modify(mid+1,right,pos,2*k+1);
	}
	pushup(k);
}
int cmp(const void *a,const void *b){
	ll *p1=(ll*)a;
	ll *p2=(ll*)b;
	return (*p1)-(*p2);
}

P4588 数学计算

题目大意见原题。

这个题目我是从线段树题单里找到的，所以这个题目肯定用线段树能做，但是怎么做呢？我们连序列都没有啊！没关系，我们可以想办法构造序列，然后建立线段树。注意到操作1是乘法，我们不难想到，如果是第i次操作是1，乘了m，那么我们可以把序列的第i个位置改成m，这样求前缀积，再取模，就是当前的模数了。又看到操作2，相当于是对乘法的撤销，但是带着取模咋撤销呢？可以这样想，撤销相当于不乘那个数了，也就是变成乘1了，所以我们只需要把对应位置改为1，然后刷新区间积的模数就好了。这个题目总体来说建模不是很难，关键在于构造出能建立线段树的序列。事实上，在没有显式序列时，我们经常会对一个全是0或者全是1或者其他数的序列建立线段树，然后通过题目叙述的修改和查询来把序列中的数改为有意义的数据。

代码就不放出来了，因为和线段树的模板大同小异，只要能建模出来，就只需要把模板改一下能AC了。
P1966 火柴排队

题目大意见原题。

印象深刻，教训深刻的一道题目。对于一个出现数学公式的题目，我们一定不能放任着他不管，除非它根本不可化简或者计算，否则一定要做一些必要的化简工作，即便是重新组合一下顺序，把形式相同的项放在一起也很有用。比如之前做过一道题，就是如果把式子展开并且按照形式归类之后，发现可以用前缀和减少重复计算。本题虽然不是用前缀和简化计算，但是不化简的话，很难做出来本题。把待求式化简之后，我们发现：\(\sum a_i^{2}\)和\(\sum b_i^2\)都是固定的，不管怎么调换顺序都是不变的，唯一的变量是\(\sum a_ib_i\) ，为了让待求式最小，我们需要让这个和最大。如果学过排序不等式的话，肯定知道顺序和>=乱序和>=反序和。所以为了让这个和最大，需要进行一些排序的工作，让这两个序列大小排名相同的火柴放在一起。那么如何看需要移动多少次才能实现这一点呢？可以这样想：我们先拷贝一份数组a到c中，然后对数组c排序，然后构造数组q，q[i]存储的是a中第i个元素的排名（您可能看出来了这里是在做离散化），接着，我们可以对b数组进行相同操作，即拷贝后排序，构造编号数组r[]。这时候，不难发现q和r都是1-n的一个排列，我们想做的事情就是通过对其中一个排列进行操作，得到另一个排列。假设q是1 3 2 4 5，r是1 5 4 2 3，不妨把q变成a b c d e，这样r就得变成a e d c b（rxz大佬将LCS转化为LIS问题时的思想）。如果按照字典序的话，q已经有序了，我们只需要看看需要多少次交换才能让r变得有序就好了，这就成了一个求逆序对有多少个的问题。逆序对可以权值线段树搞定，但是这里显然用mergesort更简单。为了便于理解，我可能进行了多次不必要的拷贝和映射，如果脑子比较好用，大可一步到位，一次映射搞定问题。

代码如下，可能省去了很多不必要的拷贝和映射，不过思想是一样的：
```
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+9;
const int mod=1e8-3;
typedef struct{
	ll value,pos;
}NB;
NB a[N],b[N],tmp[N],q[N];
ll n,ans;
void Mergesort(ll start,ll end,NB m[]);
void Merge(ll start,ll mid,ll end,NB m[]);
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i].value);
		a[i].pos=i;
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i].value);
		b[i].pos=i;
	}
	Mergesort(1,n,a);
	Mergesort(1,n,b);//离散化 
	for(ll i=1;i<=n;i++){
		q[a[i].pos].value=b[i].pos;
	}
	ans=0;
	Mergesort(1,n,q);
	printf("%lld\n",ans);
	return 0;
}
void Mergesort(ll start,ll end,NB m[]){
	if(start<end){
		ll mid=(start+end)/2;
		Mergesort(start,mid,m);
		Mergesort(mid+1,end,m);
		Merge(start,mid,end,m);
	}
}
void Merge(ll start,ll mid,ll end,NB m[]){
	ll i=start,j=mid+1,k=start;
	for(;i<=mid && j<=end;k++){
		if(m[i].value<=m[j].value)
			tmp[k]=m[i++];
		else{
			tmp[k]=m[j++];
			ans=(ans+mid-i+1)%mod;
		}	
	}
	for(;i<=mid;i++,k++)
		tmp[k]=m[i];
	for(;j<=end;j++,k++)
		tmp[k]=m[j];
	for(i=start;i<=end;i++)
		m[i]=tmp[i];
	return;
}
```
P6584 重拳出击

未完待续

题目大意：有一棵树，你最开始在某个结点上，树上每个结点有点权，每次删除操作，你都可以把离你所在的结点距离不超过\(k\)的结点的点权都修改为0，然后你可以选择将自己移动一步或者不移动，其他节点的点权必须沿着向你的方向的简单路径转移，求需要多少次删除操作才能把树上的点的点权全部变成0？

这道题看起来是一道数据结构题。这道题的规则花里胡哨的，我们一个一个看一下，想想怎么搞。首先，把所有离某个结点距离不超过某个数\(k\)的结点的点权全部变成0，不是传统的子树修改或者区间修改，直接暴力修改的话就是迭代加深，如果是把初始点记为根节点的话，其实就是层次遍历，如果想比较快的修改的话，可能考虑树剖，那样的话就得想怎么把对应的区间的编号算出来，由于刚才的层次遍历的启发，我想到一种定义\(bfs\) 序，然后建立线段树维护的方法（结果查了一下天哪真的有\(bfs\)序这种东西）。这样的话，删除的区间在\(bfs\)序上就比较容易求出来，一次修改复杂度是\(O(log^2n)\) 。

其次，对于换根操作（有了刚才的思考，我觉得把这个操作叫做换根并不为过）,动手画了几个图之后，没有想出来怎么表示今后的修改区间。

最后，对于移动操作，如果根不换的话，就是把儿子的权值加到父亲上，然后儿子的权值清零。

上面的思路有很多操作并不能高效实现，可能废了。

下面是L_C_A大佬给出的思路：我们杀死所有小怪所用的时间的最小值，取决于离我们最远的小怪有多远，想到这一点，可能会有二分的冲动。假设最远距离是\(maxdist\)，则在\([1,maxdist]\)中二分答案。怎样写check呢？看了看数据范围，应该需要在\(O(n)\)的时间内完成check。考虑到我们check的时候一般都是贪心的，所以这里我们也贪心地去验证\(key\)回合能否杀死所有小怪。显然，如果当前的\(maxdist<=k\)，则可以1回合杀完，否则的话，我们先杀光范围内的小怪，然后考虑移动：如果自己不移动的话，就是所有其他的小怪离自己的距离-1，如果自己移动的话，肯定是往最远的小怪的方向移动，并且最远的小怪也会向自己移动，这样就相当于最远的小怪离自己的距离-2了，那其他小怪呢？显然，自己移动的方向上的所有小怪的距离都是-2，除此之外的小怪，离自己的距离不变。如何判断哪些结点是在最大值方向的结点呢？看起来好像和子树有关系。自己走到了一个新的节点，那么那个节点的子树上的所有小怪离自己的距离就会-2。

线段树单点修改板子：

void modify(ll left,ll right,ll pos,ll val,ll k){
	if(pos<left || pos>right ) return ; //必须要有，否则会无限递归
	if(left==pos && pos==right){
		f[k]=val;
		return;
	}
	ll mid=(left+right)/2;
	if(pos<=mid){ //一定按照线段树的规则
		modify(left,mid,pos,val,2*k);
	} else {
		modify(mid+1,right,pos,val,2*k+1);
	}
	pushup(k);
}

牛客数学问题

题目大意：有一个数列，长度为n，允许你用两个不相交的长度为k的区间去覆盖数列，求覆盖的部分的数的和的最大值。

这道题目我的想法是枚举左面那个区间，然后用\(O(logn)\)的时间求出来它对应的右边区间的最大值。如何实现对数查询呢？我开始想的是倍增，但是不太会写。后来看了题解，发现可以线段树。如果对区间长度为k的区间的和的数组建立线段树，那么查询最大值就是单点查询了，十分简单。

当然，这道题还有一个\(dp\)做法：枚举点，对于一个点，求它左边的长度为k的区间的最大值和右边长度为k的区间的最大值，动态更新答案。

这道题的经验是：
1. 对数查询优先考虑线段树，考虑构造相应数列来建树。
2. 对于不带修的查询，考虑前缀和。

P2572 序列操作

题目大意：有一个数列，你需要快速将某个区间内所有的数变成1或者0或者取反或者查询1的个数或者查询连续的1的个数。

考虑前两个操作：都是覆盖性的操作，性质相同，所以如果只维护这两个的话是完全没有问题的。

考虑第三个操作：如果只有取反的话，也好说，但是取反操作和前两种操作的性质明显不一样，所以需要再开一个标记来做。模拟一下可以发现，在对一个极大区间标记取反之前，我们要把前两种覆盖性的操作的标记下放然后清空，不然的话之后就不知道是先取反还是先覆盖的了。然后根据老师的提示，注意到如果有一个区间有取反标记，然后又被染色的话，就不用取反了。

考虑第四个操作：其实还好，我们可以让线段树的结点的值就存储该结点表示的区间的1的个数，然后根据那些标记进行修改就好了。

考虑第五个操作：最多多少个连续的1，显然单个点很好说，如果是区间的话，我们要知道包含区间左端点的最多连续的1的个数是多少（记为\(cnt_1\)），包含右端点的最多连续的1的个数是多少（记为\(cnt_2\)），除此之外最多连续的1的个数是多少（记为\(cnt_3\)），然后在合并的时候假设左边的区间叫x，右边的区间叫y，则区间合并之后的结果就是\(max(xcnt_1,xcnt_3，xcnt_2+ycnt_1,ycnt_2,ycnt_3)\) 。注意，在查询的时候，应该是左边区间的查询结果、右边区间的查询结果以及左区间右连续+右区间左连续的结果的最大值。还有一点是，左区间右连续的结果和右区间左连续的结果要保证在\([ql,qr]\)的范围内，也就是说得取一个min，详见代码注释。

这道题目的经验是：对于覆盖性操作标记和其他类型标记，在打覆盖性标记时可能会让其他标记失效，类似地，在已经有覆盖性标记时又打其他标记，覆盖性标记也会发生变化。

代码如下(很长)：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+9;
const int M=4e5+9;
typedef struct{
	ll cnt; //这个区间有多少个数 
	ll sum;
	ll concrete_one,concrete_zero;
	ll left_zero_cnt,right_zero_cnt,mid_zero_cnt;
	ll left_one_cnt,right_one_cnt,mid_one_cnt;
	ll color,reverse; //color初始化为-1 
}SMT;
SMT f[4*N];
ll n,m,a[N];
void pushup(ll k);
void build(ll left,ll right,ll k);
void pushdown(ll left,ll right,ll k);
void modify0(ll left,ll right,ll ql,ll qr,ll k);
void modify1(ll left,ll right,ll ql,ll qr,ll k);
void modify2(ll left,ll right,ll ql,ll qr,ll k);
ll query3(ll left,ll right,ll ql,ll qr,ll k);
ll query4(ll left,ll right,ll ql,ll qr,ll k);
int main(){
	ll op,l,r;
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(ll i=1;i<=M;i++){
		f[i].color=-1;
	}
	build(1,n,1);
	while(m--){
		scanf("%lld %lld %lld",&op,&l,&r);
		if(op==0){
			modify0(1,n,l+1,r+1,1);
		} else if(op==1){
			modify1(1,n,l+1,r+1,1);
		} else if(op==2){
			modify2(1,n,l+1,r+1,1);
		} else if(op==3){
			printf("%lld\n",query3(1,n,l+1,r+1,1));
		} else {
			printf("%lld\n",query4(1,n,l+1,r+1,1));
		}
	}
	return 0;
} 
void modify1(ll left,ll right,ll ql,ll qr,ll k){
	if(ql<=left && right<=qr){
		f[k].color=1;
		f[k].concrete_one=f[k].cnt;
		f[k].left_one_cnt=f[k].cnt;
		f[k].mid_one_cnt=f[k].cnt;
		f[k].right_one_cnt=f[k].cnt;
		f[k].left_zero_cnt=0;
		f[k].mid_zero_cnt=0;
		f[k].right_zero_cnt=0;
		f[k].concrete_zero=0;
		f[k].reverse=0;
		f[k].sum=f[k].cnt;
		return;
	}
	pushdown(left,right,k);
	ll mid=(left+right)/2;
	if(ql<=mid){
		modify1(left,mid,ql,qr,2*k);
	}
	if(qr>mid){
		modify1(mid+1,right,ql,qr,2*k+1);
	}
	pushup(k);
} 
void modify2(ll left,ll right,ll ql,ll qr,ll k){
	if(ql<=left && right<=qr){
		if(f[k].color!=-1){ //如果这个区间已经有了染色标记，则把染色标记翻转 
			f[k].color^=1;
		} else { //如果没有染色标记，则翻转标记加一 
			f[k].reverse^=1; 
		}
		swap(f[k].concrete_one,f[k].concrete_zero);
		swap(f[k].left_one_cnt,f[k].left_zero_cnt);
		swap(f[k].mid_one_cnt,f[k].mid_zero_cnt);
		swap(f[k].right_one_cnt,f[k].right_zero_cnt);
		f[k].sum=f[k].cnt-f[k].sum;
		return;
	}
	pushdown(left,right,k);
	ll mid=(left+right)/2;
	if(ql<=mid){
		modify2(left,mid,ql,qr,2*k);
	}
	if(qr>mid){
		modify2(mid+1,right,ql,qr,2*k+1);
	}
	pushup(k);
}
void modify0(ll left,ll right,ll ql,ll qr,ll k){
	if(ql<=left && right<=qr){
		f[k].color=0;
		f[k].concrete_one=0;
		f[k].left_one_cnt=0;
		f[k].mid_one_cnt=0;
		f[k].right_one_cnt=0;
		f[k].left_zero_cnt=f[k].cnt;
		f[k].mid_zero_cnt=f[k].cnt;
		f[k].right_zero_cnt=f[k].cnt;
		f[k].concrete_zero=f[k].cnt; 
		f[k].reverse=0;
		f[k].sum=0;
		return;
	}
	pushdown(left,right,k);
	ll mid=(left+right)/2;
	if(ql<=mid){
		modify0(left,mid,ql,qr,2*k);
	}
	if(qr>mid){
		modify0(mid+1,right,ql,qr,2*k+1);
	}
	pushup(k);
}
ll query4(ll left,ll right,ll ql,ll qr,ll k){
	if(ql<=left && right<=qr){
		return f[k].concrete_one;
	}
	pushdown(left,right,k);
	ll mid=(left+right)/2;
	ll ans=0;
	if(ql<=mid){
		ans=query4(left,mid,ql,qr,2*k);
	}
	if(qr>mid){
		ans=max(ans,query4(mid+1,right,ql,qr,2*k+1));
	}
	if(ql<=mid && qr>mid)
		ans=max(ans,min(f[2*k].right_one_cnt,mid-ql+1)+min(f[2*k+1].left_one_cnt,qr-mid)); //很关键，防止越界
	return ans;
}
ll query3(ll left,ll right,ll ql,ll qr,ll k){
	if(ql<=left && right<=qr){
		return f[k].sum;
	}
	pushdown(left,right,k);
	ll mid=(left+right)/2;
	ll ret=0;
	if(ql<=mid){
		ret+=query3(left,mid,ql,qr,2*k);
	}
	if(qr>mid){
		ret+=query3(mid+1,right,ql,qr,2*k+1);
	}
	return ret;
}
void pushdown(ll left,ll right,ll k){
	if(f[k].color!=-1){
		f[2*k].color=f[k].color;
		f[2*k+1].color=f[k].color;
		f[2*k].reverse=0; //取反失效 
		f[2*k+1].reverse=0;
		if(f[k].color==0){
			f[2*k].sum=0;
			f[2*k].left_one_cnt=0;
			f[2*k].mid_one_cnt=0;
			f[2*k].right_one_cnt=0;
			f[2*k].left_zero_cnt=f[2*k].cnt;
			f[2*k].mid_zero_cnt=f[2*k].cnt;
			f[2*k].right_zero_cnt=f[2*k].cnt;
			f[2*k].concrete_one=0;
			f[2*k].concrete_zero=f[2*k].cnt;
			f[2*k+1].sum=0;
			f[2*k+1].left_one_cnt=0;
			f[2*k+1].mid_one_cnt=0;
			f[2*k+1].right_one_cnt=0;
			f[2*k+1].left_zero_cnt=f[2*k+1].cnt;
			f[2*k+1].mid_zero_cnt=f[2*k+1].cnt;
			f[2*k+1].right_zero_cnt=f[2*k+1].cnt;
			f[2*k+1].concrete_one=0;
			f[2*k+1].concrete_zero=f[2*k+1].cnt;
		} else {
			f[2*k].sum=f[2*k].cnt;
			f[2*k].left_one_cnt=f[2*k].cnt;
			f[2*k].mid_one_cnt=f[2*k].cnt;
			f[2*k].right_one_cnt=f[2*k].cnt;
			f[2*k].left_zero_cnt=0;
			f[2*k].mid_zero_cnt=0;
			f[2*k].right_zero_cnt=0;
			f[2*k].concrete_one=f[2*k].cnt;
			f[2*k].concrete_zero=0;
			f[2*k+1].sum=f[2*k+1].cnt;
			f[2*k+1].left_one_cnt=f[2*k+1].cnt;
			f[2*k+1].mid_one_cnt=f[2*k+1].cnt;
			f[2*k+1].right_one_cnt=f[2*k+1].cnt;
			f[2*k+1].left_zero_cnt=0;
			f[2*k+1].mid_zero_cnt=0;
			f[2*k+1].right_zero_cnt=0;
			f[2*k+1].concrete_one=f[2*k+1].cnt;
			f[2*k+1].concrete_zero=0;
		}
		f[k].color=-1;
	}
	if(f[k].reverse!=0){
		f[2*k].sum=f[2*k].cnt-f[2*k].sum;
		swap(f[2*k].left_one_cnt,f[2*k].left_zero_cnt);
		swap(f[2*k].mid_one_cnt,f[2*k].mid_zero_cnt);
		swap(f[2*k].right_one_cnt,f[2*k].right_zero_cnt);
		swap(f[2*k].concrete_one,f[2*k].concrete_zero);
		
		f[2*k+1].sum=f[2*k+1].cnt-f[2*k+1].sum;
		swap(f[2*k+1].left_one_cnt,f[2*k+1].left_zero_cnt);
		swap(f[2*k+1].mid_one_cnt,f[2*k+1].mid_zero_cnt);
		swap(f[2*k+1].right_one_cnt,f[2*k+1].right_zero_cnt);
		swap(f[2*k+1].concrete_one,f[2*k+1].concrete_zero);
		
		f[2*k].reverse^=f[k].reverse;
		f[2*k+1].reverse^=f[k].reverse;
		f[k].reverse=0;
	}
	//下面应该是pushup的内容 
//	f[k].concrete_zero=max(f[2*k].left_zero_cnt,max(f[2*k].mid_zero_cnt,max(f[2*k].right_zero_cnt+f[2*k+1].left_zero_cnt,max(f[2*k+1].mid_zero_cnt,f[2*k+1].right_zero_cnt))));
//	f[k].concrete_one=max(f[2*k].left_one_cnt,max(f[2*k].mid_one_cnt,max(f[2*k].right_one_cnt+f[2*k+1].left_one_cnt,max(f[2*k+1].mid_one_cnt,f[2*k+1].right_one_cnt))));
}
inline void pushup(ll k){
	if(f[2*k].left_one_cnt==f[2*k].cnt){
		f[k].left_one_cnt=f[2*k].left_one_cnt+f[2*k+1].left_one_cnt; //左区间内全是1 
	} else {
		f[k].left_one_cnt=f[2*k].left_one_cnt; 
	}
	if(f[2*k].left_zero_cnt==f[2*k].cnt){
		f[k].left_zero_cnt=f[2*k].left_zero_cnt+f[2*k+1].left_zero_cnt;
	} else {
		f[k].left_zero_cnt=f[2*k].left_zero_cnt;
	}
	f[k].mid_one_cnt=max(f[2*k].right_one_cnt+f[2*k+1].left_one_cnt,max(f[2*k].mid_one_cnt,f[2*k+1].mid_one_cnt)); //可能有点问题 
	f[k].mid_zero_cnt=max(f[2*k].right_zero_cnt+f[2*k+1].left_zero_cnt,max(f[2*k].mid_zero_cnt,f[2*k+1].mid_zero_cnt));
	if(f[2*k+1].right_one_cnt==f[2*k+1].cnt){
		f[k].right_one_cnt=f[2*k+1].right_one_cnt+f[2*k].right_one_cnt;
	} else {
		f[k].right_one_cnt=f[2*k+1].right_one_cnt;
	}
	if(f[2*k+1].right_zero_cnt==f[2*k+1].cnt){
		f[k].right_zero_cnt=f[2*k+1].right_zero_cnt+f[2*k].right_zero_cnt;
	} else {
		f[k].right_zero_cnt=f[2*k+1].right_zero_cnt;
	}
	f[k].sum=f[2*k].sum+f[2*k+1].sum; //总共的1的个数 
	f[k].concrete_zero=max(f[2*k].left_zero_cnt,max(f[2*k].mid_zero_cnt,max(f[2*k].right_zero_cnt+f[2*k+1].left_zero_cnt,max(f[2*k+1].mid_zero_cnt,f[2*k+1].right_zero_cnt))));
	f[k].concrete_one=max(f[2*k].left_one_cnt,max(f[2*k].mid_one_cnt,max(f[2*k].right_one_cnt+f[2*k+1].left_one_cnt,max(f[2*k+1].mid_one_cnt,f[2*k+1].right_one_cnt))));
	f[k].cnt=f[2*k].cnt+f[2*k+1].cnt;
}
void build(ll left,ll right,ll k){
	if(left==right){
		f[k].cnt=1;
		f[k].sum=a[left];
		f[k].concrete_one=a[left];
		f[k].concrete_zero=1-a[left];
		f[k].left_one_cnt=a[left];
		f[k].left_zero_cnt=1-a[left];
		f[k].mid_one_cnt=a[left];
		f[k].mid_zero_cnt=1-a[left];
		f[k].right_one_cnt=a[left];
		f[k].right_zero_cnt=1-a[left];
		return; 
	}
	ll mid=(left+right)/2;
	build(left,mid,2*k);
	build(mid+1,right,2*k+1);
	pushup(k);
}

树链剖分

P4427 求和

题目大意：有一棵树，每个点都有点权，查询树上一条路径上的点的权值的k次方和，其中1<=k<=50

这个题我是从树剖的题单找过去的，所以我自然往树剖上想的。如果是查询某确定次方和的话，就是树剖裸题，注意到本题k范围比较小，所以我们可以预处理出每个点的点权的1-50次方，然后查询的时候直接用树剖转换为区间问题，用树状数组查相应的前缀和，作差就是结果了。对于本题来说，有一个坑点：由于要取模，所以最后作差可能出现负数，所以我们应该作差之后+mod，然后再%mod，这样才保证了结果的正确性，不这么做会爆零。另外，这个题目数据是3e5，我们的算法复杂度有两个log，所以需要读写优化+内联进行卡常才能通过。

代码不放了，基本上树剖的代码长得都差不多，主要是题目建模（但这是个裸题）。

另外，这个题正解并不是树剖，以后有机会会补上正解。

做了一些题之后，明白了，这种有结合律并且还不带修改的信息，完全可以倍增维护，复杂度降低一个\(log\)。
P3038 边权树剖

这是一道模板题，让用树剖维护树上的边权信息。

这道题做法是把边权转化为点权，一种转化方法是把边权转化为它较深的端点的点权。路径修改边权时，即修改点权，但对于路径来说，lca的点权不能修改，因为显然lca的点权代表的边权不在路径上。在查询边权时，即查询边的较深的端点的点权就好了。捎带说一句，之前我是没用树剖求过lca的，但是这里我知道了，树剖两个点最后跳到同一条重链的时候，深度小的那个就是原来那两个点的lca。

代码不放了，几乎就是树剖的模板，只改了上述几个地方。
P3979 换根树剖

题目大意：一棵树，你需要修改某条路径上的点权为同一个数，可以指定某个点为根，可以查询以某个点为根的子树中的点权的最小值。

换根我们现在是第二次碰到了，思考方法主要是考虑使用新根和使用老根之间的变与不变。

首先，修改操作不管换不换根都是不变的，因为他是路径修改而不是子树修改。

换根之后，一种想法是，把信息都修改了，但是太慢了。

其实不用改它们的信息，我们最开始默认按照1号为根进行树剖预处理，然后在查询的时候，根据查询的点和新的根的关系，确定查询的区间就好了。

根据要查询的结点和\(newroot\)的逻辑关系来分类：

第一种情况，更简洁的表述是\(i\)不是\(newroot\)的祖先，这个是容易判断的，可以利用树剖\(lca\)，看\(i和newroot\)的最近公共祖先。注意先判断第四种情况，因为那时候\(lca\)和这种情况是一样的。

\(i\)是\(newroot\)本尊，则直接按照1号根查询全局最小值就好了。

\(i\)在以\(newroot\) 为根的子树中，则换根前后查询结果不变。

\(i\)在\(newroot\)和\(oldroot\)这条链上，则可以画图看一下，按照以\(newroot\)为根，适当把边进行一下旋转，能够发现，\(i\)的查询范围，就是整个树-\(i\)的包含\(newroot\) 那棵子树。记那棵子树的根为\(y\)，则\(y\)是换根之前\(i\)的儿子，且\(y\)的所有后代里面有\(newroot\) 。现在的问题是如何快速查询这个补集的信息呢？思考一下发现，\(y\)及其子树的dfs序的区间是\([v[y].id,v[y].id+v[y].size-1]\) ，所以我们只需要查询\([1,v[y].id-1]\) 和\([v[y].id+v[y].size,n]\) 就可以了。

本题主要在于如何合理利用树剖，代码的主要部分还是树剖的模板，所以就不放了。关于代码细节，这道题我的\(pushdown\)函数写错了，很致命，要知道线段树里面最核心的部分就是\(pushdown\)了，所以一定要谨慎思考；另外树剖预处理部分的dfs也写错了，不过静态debug发现了;然后我写的树上倍增居然也错了，好像是移位数太多了。不得不说这个题数据很水，犯了三个致命错误，居然可以得到90分。
P4092 树

题目大意：有一棵树，最开始树上的点都没有标记，我们可以对树进行两种操作：对一个结点打标记；查询离某个结点最近的打标记的祖先结点。

我们先考虑链上的做法：一个显然的暴力是每次询问的时候就直接往前找，但会超时。我们考虑维护区间的信息来加速，即在标记了一个结点之后，储存某个区间内的一些额外信息，比如某个区间\([l,r]\)内的深度最深的打标记的点。考虑一个经典的长度为8的链的例子，建立线段树，假设对5号点进行标记，那么\([1,8],[5,8],[5,6],[5,5]\)这四个区间维护的区间内打标记最深点的深度都有可能被刷新，这个可以在进行单点修改之后回溯时用\(pushup\)函数来实现。查询的话，比如查询7号点，那么可以直接查区间\([1,7]\)的那个信息，只要在查询时对各个极大区间取\(max\)就好了。这样的话，树上的也很明了了：修改一个点时就用\(dfs\)序来刷新信息，查询一个点时，即查询该点到根这条路径上的最深的打标记的点。问题解决！
P6584 打怪

未完待续

题目大意：有一棵树，你最开始在某个结点上，树上每个结点有点权，每次删除操作，你都可以把离你所在的结点距离不超过\(k\)的结点的点权都修改为0，然后你可以选择将自己移动一步或者不移动，其他节点的点权必须沿着向你的方向的简单路径转移，求需要多少次删除操作才能把树上的点的点权全部变成0？

这道题看起来是一道数据结构题。这道题的规则花里胡哨的，我们一个一个看一下，想想怎么搞。首先，把所有离某个结点距离不超过某个数\(k\)的结点的点权全部变成0，不是传统的子树修改或者区间修改，直接暴力修改的话就是迭代加深，如果是把初始点记为根节点的话，其实就是层次遍历，如果想比较快的修改的话，可能考虑树剖，那样的话就得想怎么把对应的区间的编号算出来，由于刚才的层次遍历的启发，我想到一种定义\(bfs\) 序，然后建立线段树维护的方法（结果查了一下天哪真的有\(bfs\)序这种东西）。这样的话，删除的区间在\(bfs\)序上就比较容易求出来，一次修改复杂度是\(O(log^2n)\) 。

其次，对于换根操作（有了刚才的思考，我觉得把这个操作叫做换根并不为过）,动手画了几个图之后，没有想出来怎么表示今后的修改区间。

最后，对于移动操作，如果根不换的话，就是把儿子的权值加到父亲上，然后儿子的权值清零。

莫队算法

P1972 HH的项链

题目大意：给定一个数列，给定查询区间[l,r]，求这段区间内有多少不一样的数。

虽然这个题正解不是莫队，离线也很容易被卡，但是本人感觉这个题可以作为一个莫队算法的入门题目。莫队算法步骤大概是：分块，询问排序，按新顺序动态调整区间与答案进行回答，最后按照原序输出询问结果。关于莫队算法究竟如何操作，我已经写在笔记本上了，下面就只贴上代码了。

//TLE 58pts
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
typedef struct{
	ll l,r,order,blocknum;
}Query;
const int N=1e6+9;
Query q[N];
ll n,m,a[N],blocksize,ans[N],cnt[N],now;
void add(ll p);
void sub(ll p);
int cmp(const void *a,const void *b);
int main(){
	ll left=1,right=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	scanf("%lld",&m);
	blocksize=sqrt(n);
	for(int i=1;i<=m;i++){
		scanf("%lld %lld",&q[i].l,&q[i].r);
		q[i].order=i;
		q[i].blocknum=q[i].l/blocksize;
	}
	qsort(q+1,m,sizeof(Query),cmp);
//	for(int i=1;i<=m;i++){
//		printf("%lld %lld\n",q[i].l,q[i].r);
//	}
	for(int i=1;i<=m;i++){
		while(left<q[i].l){
			sub(left);
			left++;
		}
		while(left>q[i].l){
			left--;
			add(left);
		}
		while(right<q[i].r){
			right++;
			add(right);
		}
		while(right>q[i].r){
			sub(right);
			right--;
		}
		ans[q[i].order]=now;
	}
	for(int i=1;i<=m;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}
void add(ll p){
	if(cnt[a[p]]==0){
		now++;
	}
	cnt[a[p]]++;
}
void sub(ll p){
	cnt[a[p]]--;
	if(cnt[a[p]]==0){
		now--;
	}
}
int cmp(const void *a,const void *b){
	Query *p1=(Query*)a;
	Query *p2=(Query*)b;
	if(p1->blocknum==p2->blocknum){
		return p1->r-p2->r;
	}
	return p1->blocknum-p2->blocknum;
}

平衡树

dbp我现在只会写AVL树，并且只写过了普通平衡树。等到我学会了splay，写过了文艺和二逼之后，再回来补上。

Trie树

P4551 最长异或路径

题意：在树中找一条路径，使得这条路径的边权的异或和最大。

预处理每个节点到根的异或和是套路。然后，考虑枚举两个点，\(O(1)\)查询其异或和，这样的话总的复杂度是\(O(n^2)\)。为了提高效率，我们要利用数据结构的力量。根据经验，解决最大异或值的问题的时候一般是从高位往下找，且一般会使用trie树来实现这个贪心。所以我们考虑用trie做这个题。

为了保证结果正确，我们建trie树的时候，要让所有的数的二进制表达长度一样。然后就是把trie建出来，然后贪心就好了。

代码如下：

#include <bits/stdc++.h>
#define ll long long
#define INF 999999999999
using namespace std;
const int N=1e5+9;
typedef struct{
	ll to,nxt,weight;
}Edge;
typedef struct ss{
	ll value;
	struct ss *child[3];
	bool isend;
	ll seq;
}Node;
typedef Node* Nodeptr;
Edge edge[2*N];
ll head[N],cnt,n,val[N],component[N];
void add(ll x,ll y,ll z);
ll query(ll v,Nodeptr root);
void dfs(ll now,ll fa,ll sum);
Nodeptr insert(ll v,Nodeptr root,ll seq);
int main(){
	ll x,y,z,now,ans=0;
	Nodeptr root=NULL;
	scanf("%lld",&n);
	for(int i=0;i<=n;i++){
		head[i]=-1;
	}
	for(int i=1;i<n;i++){
		scanf("%lld %lld %lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	dfs(1,0,0);
	for(int i=1;i<=n;i++){
		root=insert(val[i],root,i);
	}
	for(int i=1;i<=n;i++){
		now=query(val[i],root);
		ans=max(ans,now);
	}
	printf("%lld\n",ans);
	return 0;
} 
ll query(ll v,Nodeptr root){
	ll tmp=v,cnt=0,ret=0;
	Nodeptr p;
	p=root;
	for(int i=0;i<=33;i++){
		component[i]=0;
	}
	while(tmp){
		if(tmp&1){
			component[cnt++]=1;
		} else {
			component[cnt++]=0;
		}
		tmp=tmp>>1;
	}
	for(int i=33;i>=0;i--){
		if(p->child[component[i]^1]!=NULL){
			p=p->child[component[i]^1];
		} else {
			p=p->child[component[i]];
		}
	}
	if(p->isend){
		ret=v^(val[p->seq]);
	}
	return ret;
}
Nodeptr insert(ll v,Nodeptr root,ll seq){
	ll tmp=v,cnt=0;
	Nodeptr p;
	if(root==NULL){
		root=(Nodeptr)malloc(sizeof(Node));
		root->value=0;
		root->isend=false;
		for(int i=0;i<3;i++){
			root->child[i]=NULL;
		}
	}
	p=root;
	for(int i=0;i<=33;i++){
		component[i]=0;
	}
	while(tmp){
		if(tmp&1){
			component[cnt++]=1;
		} else {
			component[cnt++]=0;
		}
		tmp=tmp>>1;
	}
	for(int i=33;i>=0;i--){ //从高位到低位开始插入，长度对齐 
		if(p->child[component[i]]!=NULL){
			p=p->child[component[i]]; 
		} else {
			p->child[component[i]]=(Nodeptr)malloc(sizeof(Node));
			p=p->child[component[i]];
			p->value=component[i];
			p->isend=false;
			for(int j=0;j<3;j++){
				p->child[j]=NULL;
			}
		}
	}
	p->isend=true;
	p->seq=seq;
	return root;
}
void dfs(ll now,ll fa,ll sum){
	val[now]=sum;
	for(ll i=head[now];i>=0;i=edge[i].nxt){
		if(edge[i].to!=fa){
			dfs(edge[i].to,now,sum^edge[i].weight);
		}
	}
}
void add(ll x,ll y,ll z){
	edge[cnt].to=y;
	edge[cnt].weight=z;
	edge[cnt].nxt=head[x];
	head[x]=cnt++;
}

并查集

P1955 程序自动分析

题目大意：有一些变量相等或者不等的限制条件，现在判定这些条件是否能同时满足。

相等是一种等价关系，所以我们可以考虑用并查集来表示这种二元关系。不等，意味着两个元素不应该在一个集合中，我们只需要调用together方法进行判定就好了。注意，我们需要先把所有的相等关系都弄好之后，才能处理不等关系，否则有可能出现最开始两个元素不在一个集合，但是后来又被合并的情况。

本题多组数据，注意清零。为了无bug，建议完全清零。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+9;
unordered_map<int,int> table; //假的hash表 
int f[N],t,n,cnt;
typedef struct{
	int i,j,e;
}Node;
Node a[N];
int find(int x);
void un(int x,int y);
bool together(int x,int y);
int main(){
	scanf("%d",&t);
	while(t--){
		bool flag=true;
		table.erase(table.begin(),table.end()); //先清空map
		cnt=0;
		scanf("%d",&n); 
		for(int k=1;k<=n;k++){
			f[k]=k;
		}
		for(int k=1;k<=n;k++){
			scanf("%d %d %d",&a[k].i,&a[k].j,&a[k].e);
		}
		sort(a+1,a+n+1); //1放在前面，0放在后面 
		for(int k=1;k<=n;k++){
			if(table.find(a[k].i)==table.end()){
				table[a[k].i]=++cnt;
			}
			if(table.find(a[k].j)==table.end()){
				table[a[k].j]=++cnt;
			}
			if(a[k].e==1){
				un(table[a[k].i],table[a[k].j]);
			} else {
				if(together(table[a[k].i],table[a[k].j])){
					flag=false;
				}
			}
		}
		if(flag){
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}
inline bool operator <(const Node &a,const Node &b){
	if(a.e>b.e){
		return true;
	} else {
		return false;
	} 
}
inline bool together(int x,int y){
	return find(x)==find(y);
}
int find(int x){
	if(x==f[x]) return x;
	return f[x]=find(f[x]); 
}
void un(int x,int y){
	x=find(x);
	y=find(y);
	f[x]=y;
}

原文：https://www.cnblogs.com/BUAA-Wander/p/13311305.html