ツリーチェーンの分割テーマのまとめ+ボード

4876 ワード
データ構造
辛辣なニワトリの私はついに木のチェーンを学んで分を切り開いたことを始めて、lyが集まって早くいずれもQQを行いました.
まず板の問題です.板です.
洛谷-P 384-【テンプレート】木のチェーンの分割
テーマリンク:https://www.luogu.org/problemnew/show/P3384
四種類の操作で、板.
考え方:板.線分樹のメンテナンスで分離されたチェーンです.
ACCode(ボード):
//#pragma comment(linker, "/STACK:1024000000,1024000000")
  
#include
#include 
#include 
   
#include  
#include
#include 
#include 
#include 
#include
#include 
#include
#include 
#include 
using namespace std; 
  
#define ll long long 
#define Pair pair
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)>1;
		Build(l,mid,rt<<1,a);Build(mid+1,r,rt<<1|1,a);
		Tree[rt]=(Tree[rt<<1]+Tree[rt<<1|1]+P)%P;
	}
	public : void Update(int ql,int qr,int val,int l,int r,int rt){
		if(ql<=l&&r<=qr){
			Tree[rt]+=Size[rt]*val;
			Lazy[rt]+=val;
			return ;
		}int mid=(l+r)>>1;
		PushDown(rt);
		if(ql<=mid) Update(ql,qr,val,l,mid,rt<<1);
		if(qr>mid) Update(ql,qr,val,mid+1,r,rt<<1|1);
		Tree[rt]=(Tree[rt<<1]+Tree[rt<<1|1]+P)%P;
	}
	public : int Query(int ql,int qr,int l,int r,int rt){
		if(ql<=l&&r<=qr) return Tree[rt];
		PushDown(rt);
		int mid=(l+r)>>1;
		int ans=0;
		if(ql<=mid) ans=(ans+Query(ql,qr,l,mid,rt<<1)+P)%P;
		if(qr>mid) ans=(ans+Query(ql,qr,mid+1,r,rt<<1|1)+P)%P;
		return ans;
	}
	public : void Show(int l,int r,int rt){
		printf("rt=%d l=%d r=%d Tree[rt]=%d
",rt,l,r,Tree[rt]);
		if(l==r) return ;
		int mid=(l+r)>>1;
		Show(l,mid,rt<<1);Show(mid+1,r,rt<<1|1);
	}
};
struct Node1{
	int v,val,nxt;
	Node1(int _v=0,int _val=0,int _nxt=0){
		v=_v;val=_val;nxt=_nxt;
	}
};
Segment Seg;
Node1 Edge[MAXN<<2];
int Head[MAXN],Ecnt;
int Deep[MAXN],Fa[MAXN],Size[MAXN],Son[MAXN];
int Idx[MAXN],Icnt;//     
int Top[MAXN];
int A[MAXN],B[MAXN];
int n,m,R,P;

void Intt(){
	clean(Head,-1);Ecnt=0;
	clean(Deep,0);clean(Fa,-1);clean(Size,0);clean(Son,-1);
	Icnt=0;
}
void AddEdge(int u,int v,int val){
	Edge[Ecnt]=Node1(v,val,Head[u]);
	Head[u]=Ecnt++;
}
int DFS1(int u,int fa,int dep){
	Deep[u]=dep;
	Fa[u]=fa;
	Size[u]=1;
	int maxson=-1;
	for(int i=Head[u];i+1;i=Edge[i].nxt){
		int temp=Edge[i].v;
		if(temp==fa) continue;
		Size[u]+=DFS1(temp,u,dep+1);
		if(Size[temp]>maxson){
			maxson=Size[temp];
			Son[u]=temp;
		}
	}return Size[u];
}
void DFS2(int u,int topfa){
	Idx[u]=++Icnt;
//	cout<Deep[r]) swap(l,r);
	Seg.Update(Idx[l],Idx[r],val,1,n,1);
}
int QueryPath(int l,int r){
	int ans=0;
	while(Top[l]!=Top[r]){
		if(Deep[Top[l]]Deep[r]) swap(l,r);
	ans=(ans+Seg.Query(Idx[l],Idx[r],1,n,1)+P)%P;
	return ans;
}
void UpdateSubTree(int rt,int val){
	int l=Idx[rt],r=Idx[rt]+Size[rt]-1;
	Seg.Update(l,r,val,1,n,1);
}
int QuerySubTree(int rt){
	int l=Idx[rt],r=Idx[rt]+Size[rt]-1;
	int ans=Seg.Query(l,r,1,n,1);
	return ans;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&R,&P);
	Intt();Seg.SetMod(P);
	for(int i=1;i<=n;++i){
		scanf("%d",&A[i]);
	}
	for(int i=1;i
はい、ボードはもうあります.残りはいくつかの練習です.
洛谷-P 379【テンプレート】最近の公衆祖先(LCA)(強引に木でLCAを書きます)
テーマリンク:https://www.luogu.org/problemnew/show/P3379
状態:ACになりました.問題:https://blog.csdn.net/qq_40482358/articale/detail/89677947
洛谷-P 590[ZJOI 2008]樹の統計
テーマリンク:https://www.luogu.org/problemnew/show/P2590
状態:ACになりました.問題:https://blog.csdn.net/qq_40482358/articale/detail/89679241
洛谷-P 378[HAOI 2015]樹上操作
テーマリンク:https://www.luogu.org/problemnew/show/P3178
状態:ACになりました.問題:https://blog.csdn.net/qq_40482358/articale/detail/89680488
洛谷P 038[USACO 11 DEC]牧草栽培Grass Planting
テーマリンク:  https://www.luogu.org/problemnew/show/P3038
状態:ACになりました.問題:https://blog.csdn.net/qq_40482358/articale/detail/89853548
洛谷-P 256[NOI 2015]パッケージマネージャ
テーマリンク: https://www.luogu.org/problemnew/show/P2146
状態:ACになりました.問題:https://blog.csdn.net/qq_40482358/articale/detail/9017650
洛谷-P 486[SDOI 2011]染色
テーマリンク:https://www.luogu.org/problemnew/show/P2486
状態:ACになりました.問題:https://blog.csdn.net/qq_40482358/articale/detail/90208349
木の鎖は特定のテーマを切り開いてしばらく1段落を告げて、書いたのはすべていくらかの水の問題ですが、しかし私も一応木の鎖が分割したことを理解して、後で良いテーマに出会います.
Update:2019/5/15/13:54.
前のテーマを書く時、いくつかの木の断面の問題にぶつかりました.難しくはないですが、まとめましょう.
POJ-2763-Housewind
テーマリンク:http://poj.org/problem?id=2763
クイズ:https://blog.csdn.net/qq_40482358/articale/detail/90234558
チェーン表シリーズの文章(二)