Data structure learning notes

Post time: 2021-04-06 18:41:58

Say in front

Save a wave of \ (rp \) before the provincial election and write a few data structures

update 2021.4.12: SDOI2021 is black... rp-- OK.

LCT

\(link cut \ tree \), a dynamic tree, which can dynamically maintain a tree or a forest. The main idea is real chain subdivision. Splay maintains the forest and maintains some values for each chain.

Several points needing attention:

  1. Code style: try to use \ (x \) to represent the current node in all functions.
  2. The difference between rotate and play is that special situations need to be considered. The operation must be carried out on the premise that it is feasible, and the points with subscript \ (0 \) must not be modified in the whole operation process!
  3. The stack used in play should be handwritten, not stl. It's too slow. Pay attention to the modification of the boundary.
  4. Before writing, first think about whether the required things can be maintained with refresh in LCT.

A wave of boards written recently:

Click to view the code
struct Link_Cut_Tree{
	struct Stack{
		int s[N],t;
		inline void clear(){t=0;}
		Stack(){clear();}
		inline void push(int x){s[++t]=x;}
		inline int top(){return s[t];}
		inline void pop(){--t;}
		inline bool empty(){return !t;}
	};
	int fa[N],val[N],ch[N][2];bool tag[N];
	inline void refresh(int x){val[x]=a[x]^val[ch[x][0]]^val[ch[x][1]];}
	inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
	inline bool chk(int x){return ch[fa[x]][1]==x;}
	inline void rotate(int x){
		int f=fa[x],gf=fa[f],k=chk(x),w=ch[x][k^1];
		fa[x]=gf;if(!isroot(f)) ch[gf][chk(f)]=x;
		if(w) fa[w]=f;ch[f][k]=w;
		fa[f]=x;ch[x][k^1]=f;
		refresh(f),refresh(x);
	}
	inline void pushdown(int x){
		if(!tag[x]) return;
		tag[ch[x][0]]^=1,tag[ch[x][1]]^=1,tag[x]=0;
		swap(ch[x][0],ch[x][1]);
	}
	inline void splay(int x){
		Stack st;
		int p=x;
		while(!isroot(p)) st.push(p),p=fa[p];
		st.push(p);
		while(!st.empty()) pushdown(st.top()),st.pop();
		while(!isroot(x)){
			int f=fa[x],gf=fa[f];
			if(!isroot(f)){
				if(chk(f)==chk(x)) rotate(f);
				else rotate(x);
			}
			rotate(x);
		}
	}
	inline void access(int x){
		for(int p=0;x;p=x,x=fa[x]) splay(x),ch[x][1]=p,refresh(x);
	}
	inline void makeroot(int x){
		access(x);
		splay(x);
		tag[x]^=1;
	}
	inline int findroot(int x){
		access(x);
		splay(x);
		while(ch[x][0]) x=ch[x][0];
		return x;
	}
	inline void split(int x,int y){
		makeroot(x);
		access(y);
		splay(y);
	}
	inline void link(int x,int y){
		makeroot(x);
		if(findroot(y)!=x) fa[x]=y;
	}
	inline void cut(int x,int y){
		split(x,y);
		if(ch[y][0]==x&&!ch[x][1]) fa[x]=ch[y][0]=0;
	}
	inline void modify(int x,int y){
		access(x);
		splay(x);
		a[x]=y,refresh(x);
	}
}T;

UPDATE 2021.5.13: then LCT failed because of cet-10

Virtual tree

The name sounds tall, but it's actually not that difficult. Virtual tree is used to solve the problem of key points on the tree. If there is a \ (q \) group query, the violent method is \ (O(qn) \) (or there is another \ (\ log \)), and the sum of the total number of points where all queries actually work is \ (O(n) \), then it can be solved with a virtual tree.

Note that in the process of building a virtual tree, the stack is used to record the rightmost chain. All key points at the left end of the chain (the subtree with smaller order of \ (dfs \) on the left) have been matched. In this way, you can \ (O(k) \) build trees through classified discussion. Pay attention to calling the element below the top of the stack during tree building. Don't make mistakes when considering the boundary.

After the virtual tree is built, it is basically the same as the practice of violence. It may need to pretreat a little more on the original tree.

board:

Click to view the code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
inline ll rd(){
	ll res=0,flag=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') flag=-1;c=getchar();}
	while(c>='0'&&c<='9') res=(res<<1)+(res<<3)+(c-'0'),c=getchar();
	return res*flag;
}
void wt(ll x){
	if(x>9) wt(x/10);
	putchar(x%10+'0');
}
inline ll min(const ll &a,const ll &b){return a<b?a:b;}
const int N=5e5+13;
const ll INF=0x3f3f3f3f3f3f3f3fll;
struct Stack{
	int s[N],t;
	inline void clear(){s[t=0]=0;}
	Stack(){clear();}
	inline void push(int x){s[++t]=x;}
	inline void pop(){--t;}
	inline int ttop(){return s[t-1];}
	inline int top(){return s[t];}
	inline bool empty(){return !t;}
};
struct Edge{int v,w,nxt;}e[N<<1];
int n,m,k,tot,h[N],fa[N],siz[N],dep[N],son[N],top[N],id[N],a[N],num;
bool vis[N];
ll f[N],minw[N];
inline void add(int u,int v,int w){e[++tot]=(Edge){v,w,h[u]};h[u]=tot;}
void dfs1(int u,int f,int deep){
	fa[u]=f,siz[u]=1,dep[u]=deep;
	int maxson=0;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;if(v==f) continue;
		minw[v]=min(minw[u],w);
		dfs1(v,u,deep+1);
		siz[u]+=siz[v];
		if(siz[v]>maxson) maxson=siz[v],son[u]=v;
	}
}
void dfs2(int u,int topf){
	top[u]=topf,id[u]=++num;
	if(!son[u]) return;
	dfs2(son[u],topf);
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
	}
}
inline int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	return id[u]<id[v]?u:v;
}
Edge E[N];int H[N],Tot;
inline bool cmp(const int &x,const int &y){return id[x]<id[y];}
inline void Add(int u,int v){E[++Tot]=(Edge){v,0,H[u]};H[u]=Tot;}
Stack st;
inline void build(){
	st.clear();Tot=0;
	sort(a+1,a+k+1,cmp);
	st.push(1);
	for(int i=1;i<=k;++i){
		int t=lca(a[i],st.top());
		if(t!=st.top()){
			while(st.t>1&&id[t]<id[st.ttop()]) Add(st.ttop(),st.top()),st.pop();
			if(t!=st.ttop()) Add(t,st.top()),st.pop(),st.push(t);
			else Add(t,st.top()),st.pop();
		}
		st.push(a[i]);
	}
	for(int i=1;i<st.t;++i) Add(st.s[i],st.s[i+1]);
}
void init(int u){
	f[u]=minw[u];
	ll sum=0;
	for(int i=H[u];i;i=E[i].nxt){
		int v=E[i].v;
		init(v);sum+=f[v];
	}
	if(!vis[u]) f[u]=min(f[u],sum);
	H[u]=0;
}
int main(){
	n=rd();
	for(int i=1,u,v,w;i<n;++i) u=rd(),v=rd(),w=rd(),add(u,v,w),add(v,u,w);
	minw[1]=INF;dfs1(1,0,0),dfs2(1,1);
	m=rd();
	for(int i=1;i<=m;++i){
		k=rd();
		for(int j=1;j<=k;++j) a[j]=rd(),vis[a[j]]=1;
		build();
		init(1);
		for(int j=1;j<=k;++j) vis[a[j]]=0;
		wt(f[1]);putchar('\n');
	}
	return 0;
}

Segment tree beats

Interval maximum value is the data structure problem with such operation:

1 x y means changing \ (a_x \) to \ (\ max(\min) (a_x,y) \).

This thing seems difficult to deal with, so we need to rethink our understanding of lazy tag when we first learned segment tree.

What is a lazy tag? Its meaning is actually the combination of some operations. If there are many addition operations in this interval, these operations can be combined here. When the sub interval of this interval needs to be used, they can be passed down together. Because if you want to write down all the operations, the complexity is obviously very high. The existence of this lazy tag ensures the complexity.

Suppose this operation is \ (\ max (a_, x, y) \), and then the interval \ (\ min \) is required at last. Then, you can maintain an interval minimum value \ (MI \), the number of values in the interval equal to the minimum value \ (c \), and the interval sub minimum value \ (SE \). In this way, if the number of \ (\ Max \) in the interval is \ (x \) every time you go to a node, consider the relationship between this value and the size of \ (mi,se \). Obviously, if \ (x\leq mi \), there must be no further modification and contribution; If \ (MI < x < se \), you only need to update the value of \ (MI \), and change other values of the interval (such as interval sum, etc.) through the number of \ (c \); If \ (x\geq se \), continue to download. The complexity of this thing seems to be very high, but it is not high. A relatively simple proof is to consider the number of different values in the search interval during each violent dfs. At least one of the left and right children in each downward pass combines the maximum value and the second maximum value, so the number of different values in this interval will be reduced. Then \ (\ log n \) layers, with a maximum of \ (O(n) \) in each layer, the complexity can prove that a lower bound is \ (O((n+m)\log n) \). If the addition operation is added, because each addition operation will modify the value of \ (O(\log n) \) points, the total complexity is one more \ (\ log \).

The core of the historical maximum value is to set a \ (preadd \) to represent the maximum value of the addition mark of each point after the last downlink. Taking advantage of the nature of lazy tag merging operation, after merging the historical maximum flag, it can be directly used to count the historical maximum value in the process of pushdown. The total complexity is \ (O((n+m)\log n \).

In addition, when the interval maximum value and historical maximum value are combined, the number is divided into maximum value and non maximum value, and the addition mark and historical maximum addition mark are maintained respectively. This complexity has been proved to be \ (O(m\log^2 n) \) before. This approach seems violent, but it can inspire us to start with the value range and divide and conquer the special value (maximum value) when a kind of statistical interval problem is very difficult. Through the excellent nature of data structures such as line segment tree, it only takes \ (1 \) to \ (2 \ (\ log \) to transform it into a relatively simple and violent way by considering the influence of special value.

When writing code, pay attention to the readability of variables and errors in small details. After problems occur, read the code silently to see if there are obvious problems in details.

Formwork P6242

Click to view the code
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return a<b?a:b;}
inline int rd(){
	int res=0,flag=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')flag=-1;
	for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
	return res*flag;
}
void wt(ll x){if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=5e5+13,INF=0x3f3f3f3f;
struct SegTree{int l,r,maxx,premax,se,cnt,add,preadd,addmax,preaddmax;ll sum;}t[N<<2];
int n,m;
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
inline void refresh(int p){
	t[p].sum=t[ls].sum+t[rs].sum;
	t[p].premax=max(t[ls].premax,t[rs].premax);
	if(t[ls].maxx>t[rs].maxx) t[p].maxx=t[ls].maxx,t[p].cnt=t[ls].cnt,t[p].se=max(t[ls].se,t[rs].maxx);
	else if(t[ls].maxx==t[rs].maxx) t[p].maxx=t[ls].maxx,t[p].cnt=t[ls].cnt+t[rs].cnt,t[p].se=max(t[ls].se,t[rs].se);
	else t[p].maxx=t[rs].maxx,t[p].cnt=t[rs].cnt,t[p].se=max(t[ls].maxx,t[rs].se);
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){t[p].sum=t[p].maxx=t[p].premax=rd(),t[p].se=-INF,t[p].cnt=1;return;}
	build(ls,l,mid);build(rs,mid+1,r);
	refresh(p);
}
inline void pushup(int p,int x,int px,int x_m,int px_m){
	t[p].sum+=1ll*t[p].cnt*x_m+1ll*(t[p].r-t[p].l+1-t[p].cnt)*x;
	t[p].premax=max(t[p].premax,t[p].maxx+px_m);
	t[p].preadd=max(t[p].preadd,t[p].add+px);
	t[p].preaddmax=max(t[p].preaddmax,t[p].addmax+px_m);
	t[p].add+=x,t[p].addmax+=x_m,t[p].maxx+=x_m;
	if(t[p].se!=-INF) t[p].se+=x;
}
inline void pushdown(int p){
	int tmp=max(t[ls].maxx,t[rs].maxx);
	if(t[ls].maxx==tmp) pushup(ls,t[p].add,t[p].preadd,t[p].addmax,t[p].preaddmax);
	else pushup(ls,t[p].add,t[p].preadd,t[p].add,t[p].preadd);
	if(t[rs].maxx==tmp) pushup(rs,t[p].add,t[p].preadd,t[p].addmax,t[p].preaddmax);
	else pushup(rs,t[p].add,t[p].preadd,t[p].add,t[p].preadd);
	t[p].add=t[p].preadd=t[p].addmax=t[p].preaddmax=0;
}
void update(int p,int l,int r,int x){
	if(l<=t[p].l&&t[p].r<=r) return pushup(p,x,x,x,x);
	pushdown(p);
	if(l<=mid) update(ls,l,r,x);
	if(r>mid) update(rs,l,r,x);
	refresh(p);
}
void modify(int p,int l,int r,int x){
	if(x>=t[p].maxx) return;
	if(l<=t[p].l&&t[p].r<=r&&x>t[p].se) return pushup(p,0,0,x-t[p].maxx,x-t[p].maxx);
	pushdown(p);
	if(l<=mid) modify(ls,l,r,x);
	if(r>mid) modify(rs,l,r,x);
	refresh(p);
}
ll query_sum(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
	pushdown(p);ll res=0;
	if(l<=mid) res+=query_sum(ls,l,r);
	if(r>mid) res+=query_sum(rs,l,r);
	return res;
}
int query_max(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r) return t[p].maxx;
	pushdown(p);int res=-INF;
	if(l<=mid) res=max(res,query_max(ls,l,r));
	if(r>mid) res=max(res,query_max(rs,l,r));
	return res;
}
int query_premax(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r) return t[p].premax;
	pushdown(p);int res=-INF;
	if(l<=mid) res=max(res,query_premax(ls,l,r));
	if(r>mid) res=max(res,query_premax(rs,l,r));
	return res;
}
inline void file(){
	freopen("P6242_1.in","r",stdin);
	freopen("P6242.out","w",stdout);
}
int main(){
	//file();
	n=rd(),m=rd();
	build(1,1,n);
	while(m--){
		int op,l,r,x;
		op=rd(),l=rd(),r=rd();
		switch(op){
			case 1:x=rd();update(1,l,r,x);break;
			case 2:x=rd();modify(1,l,r,x);break;
			case 3:printf("%lld\n",query_sum(1,l,r));break;
			case 4:printf("%d\n",query_max(1,l,r));break;
			case 5:printf("%d\n",query_premax(1,l,r));break;
		}
	}
	return 0;
}

Li Chao line segment tree

Li Chao tree is a line segment tree used to maintain line segments. Consider that if there are \ (m \) line segments added, and the largest line segment on a \ (x \) coordinate is queried many times, which cannot be done with an ordinary line segment tree, then a Li Chao tree is needed. The core idea of Li Chao tree is to record the current "optimal" line segment of each interval. Finally, because there is only a single point query, the optimal values of all line segments on the path from this point to the root on the line segment tree can be directly counted.

Consider adding a line segment \ (u \) and the optimal line segment number of the current node is \ (v \), then the classification discussion is as follows:

First, discuss the slope size:

If \ (u.k=v.k \), you only need to compare the values of the two line segments at \ (mid \). The larger line segment must be better at any position, and you can exit directly.

If \ (U.K > V.K \), compare the values of \ (val(u,mid) \) and \ (val(v,mid) \) at \ (mid \):

  1. \Better \ (i.e. on the left \ (mid, \), better \ (possible) \ (u, \, on the right) \ (mid, \);
  2. \(Val (u, mid) < val (v, mid) \), \ (v \) must be better on the left, and \ (u \) may be better on the right.

If \ (U.K < V.K \), still compare the values \ (val(u,mid) \) and \ (val(v,mid) \) of the two line segments at \ (mid \):

  1. \(Val (u, mid) > val (v, mid) \), \ (u \) must be better on the left, and \ (v \) may be better on the right;
  2. \(Val (u, mid) < val (v, mid) \), \ (v \) must be better on the right, and \ (u \) may be better on the left.

All cases of \ (val(u,mid)=val(v,mid) \) can be classified into either of the two cases.

Now that we have discussed all the cases, consider how to realize \ (update \) a straight line. It can be found that if the optimal line segment is \ (u \) in the interval represented by the current node, then this line segment does not need to be transmitted down. Only when it is replaced by a better line segment, through the above analysis, if it may be better in a certain interval below, it will be transmitted down. Therefore, the total modification complexity is \ (O(\log^2 n) \) and the query complexity is \ (O(\log n) \).

Template P4097

Click to view the code
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=40000+13,M=1e5+13;
const double eps=1e-10;
struct Segment{double k,b;}a[M];
struct Node{
	int id;double y;
	bool operator<(const Node &a)const{
		if(fabs(y-a.y)<eps) return id>a.id;
		return y<a.y;
	}
};
int n=39989,m,lim=1e9,cnt;
inline int add(int x0,int y0,int x1,int y1){
	++cnt;
	if(x0==x1) a[cnt].k=0,a[cnt].b=max(y0,y1);
	else{
		a[cnt].k=1.0*(y1-y0)/(x1-x0);
		a[cnt].b=y0-a[cnt].k*x0;
	}
	return cnt;
}
inline double val(int id,int x){return a[id].k*x+a[id].b;}
struct SegTree{int l,r,id;}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r) return;
	build(ls,l,mid);build(rs,mid+1,r);
}
void update(int p,int l,int r,int id){
	if(l<=t[p].l&&t[p].r<=r){
		if(!t[p].id){t[p].id=id;return;}
		if(t[p].l==t[p].r){
			if(val(id,t[p].l)>val(t[p].id,t[p].l)) t[p].id=id;
			return;
		}
		if(fabs(a[id].k-a[t[p].id].k)<eps){
			if(val(id,mid)>val(t[p].id,mid)) t[p].id=id;
		}
		else if(a[id].k>a[t[p].id].k){
			if(val(id,mid)>val(t[p].id,mid)){
				update(ls,l,r,t[p].id);
				t[p].id=id;
			}
			else update(rs,l,r,id);
		}
		else{
			if(val(id,mid)>val(t[p].id,mid)){
				update(rs,l,r,t[p].id);
				t[p].id=id;
			}
			else update(ls,l,r,id);
		}
		return;
	}
	if(l<=mid) update(ls,l,r,id);
	if(r>mid) update(rs,l,r,id);
}
Node query(int p,int x){
	Node res=(Node){t[p].id,val(t[p].id,x)};
	if(t[p].l==t[p].r) return res;
	return max(res,x<=mid?query(ls,x):query(rs,x));
}
int main(){
	//freopen("P4097_1.in.txt","r",stdin);
	//freopen("P4097.out","w",stdout);
	build(1,1,n);
	scanf("%d",&m);int lastans=0;
	while(m--){
		int op,x0,y0,x1,y1,x;
		scanf("%d",&op);
		if(op){
			scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
			x0=(x0+lastans-1)%n+1,x1=(x1+lastans-1)%n+1;
			y0=(y0+lastans-1)%lim+1,y1=(y1+lastans-1)%lim+1;
			if(x0>x1) swap(x0,x1),swap(y0,y1);
			int id=add(x0,y0,x1,y1);
			update(1,x0,x1,id);
		}
		else{
			scanf("%d",&x);x=(x+lastans-1)%n+1;
			Node ans=query(1,x);
			printf("%d\n",(lastans=ans.id));
		}
	}
	return 0;
}

Segment tree divide and conquer

Segment tree divide and conquer is an off-line method to solve the problem that the on-line algorithm is not good enough. First, build a line segment tree on the timeline, and then put all modifications into the \ (O(\log n) \) intervals of the line segment tree. Finally, the dfs line segment tree finds the answer of the leaf node again. Note that the modification operations here must support revocability. For example, the merge query set can only be merged by rank, and the stack should be used to support revocability.

The board problem roughly means that we need to judge that a graph is a bipartite graph if and only if it has no odd ring. The solution of odd ring is to expand the field and look up the set.

Formwork P5787

Click to view the code
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
inline int rd(){
	int res=0;char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
	return res;
}
const int N=2e5+13;
int n,m,k;bool ans[N];
struct edge{int u,v;}E[N];
struct SegTree{int l,r;vector<int>e;}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r) return;
	build(ls,l,mid),build(rs,mid+1,r);
}
void update(int p,int l,int r,int x){
	if(l<=t[p].l&&t[p].r<=r) return t[p].e.push_back(x);
	if(l<=mid) update(ls,l,r,x);
	if(r>mid) update(rs,l,r,x);
}
struct Node{int x,y,k;};
stack<Node> s;
int fa[N],dep[N];
int find(int x){return fa[x]==x?x:find(fa[x]);}
inline void merge(int u,int v){
	int x=find(u),y=find(v);
	if(x==y) return;
	if(dep[x]>dep[y]) swap(x,y);
	fa[x]=y,dep[y]+=(dep[x]==dep[y]);
	s.push((Node){x,y,dep[x]==dep[y]});
}
inline bool check(int u,int v){return find(u)==find(v);}
void dfs(int p){
	int lim=t[p].e.size(),tmp=s.size();bool flag=1;
	for(int i=0;i<lim;++i){
		int u=E[t[p].e[i]].u,v=E[t[p].e[i]].v;
		if(check(u,v)){flag=0;break;}
		merge(u,v+n),merge(v,u+n);
	}
	if(flag){
		if(t[p].l==t[p].r) ans[t[p].l]=1;
		else dfs(ls),dfs(rs);
	}
	lim=s.size();
	while(lim>tmp){
		fa[s.top().x]=s.top().x,dep[s.top().y]-=s.top().k;
		s.pop();--lim;
	}
}
int main(){
	n=rd(),m=rd(),k=rd();
	build(1,1,k);
	for(int i=1;i<=m;++i){
		E[i].u=rd(),E[i].v=rd();
		int l=rd(),r=rd();
		if(l<r) update(1,l+1,r,i);
	}
	for(int i=1;i<=(n<<1);++i) fa[i]=i,dep[i]=1;
	dfs(1);
	for(int i=1;i<=k;++i) puts(ans[i]?"Yes":"No");
	return 0;
}

Cartesian Tree

Cartesian tree is a binary search tree. Each point has two weights \ ((x_i,y_i) \), which meet two conditions:

  1. All \ (x_i \) form a binary search tree.
  2. All \ (y_i \) form a small root heap.

The general establishment is to monotonically increase \ (x_i \) first, so that if the point inserted each time is the child of the original point, it must be the right son; If the original point is the child of this point, it must be the left son. Then there is a \ (O(n) \) method to establish Cartesian tree:

Take the monotone stack to store the rightmost chain of the current tree (always follow the chain of the right son). Then every time a point comes in, you must find the position of the deepest \ (y < y_i \) on this chain and connect it below this point. Then the original points at the bottom are connected to the left subtree of this point, and finally put this point into the stack. Because each point will only be put into and out of the stack once, the total time complexity is \ (O(n) \).

Formwork P5854

Click to view the code
#include<iostream>
#include<cstdio>
#define rint register int
using namespace std;
inline int rd(){
	int res=0;char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
	return res;
}
const int N=1e7+13;
int n,a[N],s[N],top,L[N],R[N];
int main(){
	n=rd();
	for(rint i=1;i<=n;++i){
		a[i]=rd();rint pos=top;
		while(pos&&a[s[pos]]>a[i]) --pos;
		if(pos) R[s[pos]]=i;
		if(pos<top) L[i]=s[pos+1];
		s[top=(++pos)]=i;
	}
	long long ans1=0,ans2=0;
	for(rint i=1;i<=n;++i) ans1^=1ll*i*(L[i]+1),ans2^=1ll*i*(R[i]+1);
	printf("%lld %lld\n",ans1,ans2);
	return 0;
}

Point divide and conquer

Point divide and conquer can solve a class of tree problems. The board question is to ask whether there is a point pair with a distance of \ (k \) on a tree with edge power.

There are two methods: the first is to enumerate the middle points of this distance and match directly in the subtree. The specific method is to add all \ (D \) in the subtree to a data structure. When each subsequent \ (D \) comes in, find out whether there is one with a value of \ (k-d \) and not in the same subtree in the data structure. If so, the answer to this question is OK. This can be done by using buckets \ (O(nm\log n) \).

However, if buckets cannot be used (the data range is large), you may need to use balanced tree maintenance. The second method is a good solution: put all points in the subtree into an array, sort from small to large according to \ (d \), and then define two pointers \ (l,r \) to scan from the beginning and end respectively. Note that because \ (l \) increases monotonically, then \ (r \) will only be monotonous, so the complexity of scanning is \ (O(n) \).

Wait, is there a problem? If the tree is a chain, is the complexity false?

How to solve this problem? Consider finding the center of gravity of the subtree every time you enter a subtree. In this way, each downward recursion will reduce at least \ (\ frac12 \), so the total number of times you need to sweep like the above is \ (O(\log n) \). When you count the sorting, the total complexity is \ (O(n\log^2 n+nm\log n) \).

Click to view the code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int max(const int &a,const int &b){return a>b?a:b;}
const int N=1e4+13;
struct Edge{int v,w,nxt;}e[N<<1];
int n,m,q[N],tot,cnt,h[N],rt,siz[N],maxson[N],a[N],b[N],d[N];
bool vis[N],ans[N];
inline bool cmp(const int &x,const int &y){return d[x]<d[y];}
inline void add(int u,int v,int w){e[++tot]=(Edge){v,w,h[u]};h[u]=tot;}
void getroot(int u,int fa,int total){
	siz[u]=1,maxson[u]=0;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;if(v==fa||vis[v]) continue;
		getroot(v,u,total);
		siz[u]+=siz[v];
		maxson[u]=max(maxson[u],siz[v]);
	}
	maxson[u]=max(maxson[u],total-siz[u]);
	if(!rt||maxson[u]<maxson[rt]) rt=u;
}
void init(int u,int fa,int sum,int top){
	a[++cnt]=u,d[u]=sum,b[u]=top;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;if(v==fa||vis[v]) continue;
		init(v,u,sum+e[i].w,top);
	}
}
void solve(int u){
	vis[u]=1;a[cnt=1]=u,b[u]=u,d[u]=0;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;if(vis[v]) continue;
		init(v,0,e[i].w,v);
	}
	sort(a+1,a+cnt+1,cmp);
	for(int i=1;i<=m;++i){
		if(ans[i]) continue;
		int l=1,r=cnt;
		while(l<r){
			if(d[a[l]]+d[a[r]]>q[i]) --r;
			else if(d[a[l]]+d[a[r]]<q[i]) ++l;
			else if(b[a[l]]==b[a[r]]){
				if(d[a[r-1]]==d[a[r]]) --r;
				else ++l;
			}
			else{ans[i]=1;break;}
		}
	}
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;if(vis[v]) continue;
		rt=0,getroot(v,0,siz[v]);getroot(rt,0,siz[rt]);
		solve(rt);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<n;++i) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	for(int i=1;i<=m;++i) scanf("%d",&q[i]);
	getroot(1,0,n);
	solve(rt);
	for(int i=1;i<=m;++i) puts(ans[i]?"AYE":"NAY");
	return 0;
}

Posted by lbraine on Tue, 03 May 2022 21:10:30 +0300