"Problem solving" Luogu P8339 [AHOI2022] key

Violence: when walking the \ (u\to v \) path, if you encounter a key, press it into the stack of the corresponding color. If you encounter a treasure chest, match the key on the top of the stack with it and pop up the key.

Special property A: considering A key \ (x \) and its corresponding treasure chest \ (Y \), it will contribute \ (1 \) to all paths containing \ (x\to y \) (the inclusion requirements here and \ (x\to y \) are in the same direction). Then consider that on the \ (dfn\times dfn \) plane, \ ((x,y) \) represents the answer corresponding to \ (x\to y \). The path corresponding to each key and its treasure chest \ (x\to y \). According to whether \ (x,y \) is the ancestor relationship, the path containing it is the rectangle of the subtree complementing \ (\ times \) subtree, or the rectangle of the subtree complementing \ (\ times \) subtree, or the rectangle of the subtree complementing \ (\ times \) subtree. Then the problem becomes A rectangular \ (+ 1 \) single point evaluation problem, which can be solved by scanning the line of the tree array.

The positive solution considers using the ideas of the above two practices for reference.

Considering a violent greedy matching process, which treasure chest a key matches, it has nothing to do with the keys encountered before the key and their matching. Therefore, for each key, in the process of greedy matching, go in all directions, and the matching treasure chest collection is certain.

The process of finding this set is to take the key \ (x \) as the root dfs, maintain A stack, store only the key with the same color as the root, and then match. Until the key represented by the treasure chest \ (Y \) and the root is successfully matched, then \ (x\to y \) will produce A \ (1 \) contribution to all paths containing \ (x\to y \), which can be solved by using the scan line of special property A.

Because the process of dfs is only related to the same color, pull out the one with the same color and find the treasure box on the virtual tree.

Time complexity \ (\ mathcal{O}(n\log n) \)

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n';
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<typename T>
T &read(T &r){
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x, T2& ...y){ read(x); read(y...); }
inline int lowbit(int x){return x&(-x);}
const int N=1000010;
int n,m,ct[N];
int t[N],c[N];
int ctc[N][3];
int fa[N],dep[N];
vi eg[N];
namespace ac{
	int dfn[N],ofn[N],fi[N],ed[N],oft,dft,dep[N],fa[N][21],lg[N],siz[N];
	int st[21][N],nowc;
	int top,stk[N];
	vi vec[N],et[N];
	void dfs1(int x,int f){
		fa[x][0]=f;dep[x]=dep[f]+1;siz[x]=1;
		dfn[x]=++dft;fi[x]=++oft;ofn[oft]=x;
		for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
		for(auto v:eg[x])if(v!=f){
			dfs1(v,x);
			siz[x]+=siz[v];
			ed[v]=++oft;
			ofn[oft]=x;
		}
	}
	int LCA(int x,int y){
		x=fi[x];y=fi[y];
		int l=min(x,y),r=max(x,y);
		int k=lg[r-l+1];
		return dep[st[k][l]]<dep[st[k][r-(1<<k)+1]] ? st[k][l] : st[k][r-(1<<k)+1];
	}
	void merge(int x,int y){
		et[x].pb(y);et[y].pb(x);
	}
	int Findsbt(int x,int y){
		for(int i=20;~i;i--)
			if(dep[fa[y][i]]>dep[x])
				y=fa[y][i];
		return y;
	}
	int lct;
	struct Line{
		int l,r,h,v;
	}li[N*10];
	struct Que{
		int x,y,i;
	}q[N];
	int ans[N];
	int tree[N];
	void modify(int x,int v){
		for(;x<=n;x+=lowbit(x))tree[x]+=v;
	}
	void modify(int l,int r,int v){
		modify(l,v);
		if(r<n)modify(r+1,-v);
	}
	int query(int x){
		int s=0;
		for(;x;x-=lowbit(x))s+=tree[x];
		return s;
	}
	void Push(int l1,int r1,int l2,int r2){
		if(l1>r1||l2>r2)return ;
//		cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
		li[++lct]={l2,r2,l1,1};
		if(r1<n)li[++lct]={l2,r2,r1+1,-1};
	}
	void dfs2(int x,int f,int h,int aci){
		if(x!=aci&&c[x]==nowc){
			if(t[x]==1)++h;
			else{
				if(!h){
					if(fi[aci]<=fi[x]&&ed[x]<=ed[aci]){
						int y=Findsbt(aci,x);
						int l=dfn[x],r=dfn[x]+siz[x]-1;
						Push(1,dfn[y]-1,l,r);
						Push(dfn[y]+siz[y],n,l,r);
					}
					else{
						if(fi[x]<=fi[aci]&&ed[aci]<=ed[x]){
							swap(x,aci);
							int y=Findsbt(aci,x);
							int l=dfn[x],r=dfn[x]+siz[x]-1;
							Push(l,r,1,dfn[y]-1);
							Push(l,r,dfn[y]+siz[y],n);
						}
						else{
							Push(dfn[aci],dfn[aci]+siz[aci]-1,dfn[x],dfn[x]+siz[x]-1);
						}
					}
					return ;
				}
				--h;
			}
		}
		for(auto v:et[x])if(v!=f){
			dfs2(v,x,h,aci);
		}
	}
	void init(){
		dfs1(1,0);
		ed[1]=++oft;ofn[oft]=1;
		for(int i=1;i<=oft;i++)st[0][i]=ofn[i];
		for(int i=2;i<=oft;i++)lg[i]=lg[i>>1]+1;
		for(int i=1;i<=20;i++)
			for(int j=1;j+(1<<i)-1<=oft;j++)
				st[i][j]=dep[st[i-1][j]]<dep[st[i-1][j+(1<<(i-1))]] ? st[i-1][j] : st[i-1][j+(1<<(i-1))];
		for(int i=1;i<=m;i++){
			int x,y;read(x,y);
			q[i]={dfn[x],dfn[y],i};
		}
	}
	void JiTangLaiLe(){
		for(int i=1;i<=n;i++)vec[c[i]].pb(i);
		for(int o=1;o<=n;o++){
			nowc=o;
			stk[top=1]=1;
			sort(vec[o].begin(),vec[o].end(),[](const int &x,const int &y){return dfn[x]<dfn[y];});
			vi po;
			for(auto x:vec[o]){
				if(x==1)continue;
				int t=LCA(x,stk[top]);
				while(top>1&&dep[t]<dep[stk[top-1]]){
					merge(stk[top-1],stk[top]);
					po.pb(stk[top]);--top;
					t=LCA(x,stk[top]);
				}
				if(dep[t]<dep[stk[top]]){
					merge(t,stk[top]);
					po.pb(stk[top]);--top;
					if(t!=stk[top])stk[++top]=t;
					stk[++top]=x;
				}
				else stk[++top]=x;
			}
			while(top>1){
				merge(stk[top],stk[top-1]);
				po.pb(stk[top]);--top;
			}
			po.pb(1);
			for(auto x:vec[o]){
				if(t[x]==1){
					dfs2(x,0,0,x);
				}
			}
			for(auto x:po){
				vi().swap(et[x]);
			}
		}		
	}
	void Sao(){
		sort(li+1,li+lct+1,[](const Line &x,const Line &y){return x.h<y.h;});
		sort(q+1,q+m+1,[](const Que &x,const Que &y){return x.x<y.x;});
		int pos=1;
		for(int i=1;i<=m;i++){
			while(pos<=lct&&li[pos].h<=q[i].x){
				modify(li[pos].l,li[pos].r,li[pos].v);
				++pos;
			}
			ans[q[i].i]=query(q[i].y);
		}
	}
	void main(){
		init();
		JiTangLaiLe();
		Sao();
		for(int i=1;i<=m;i++)cout << ans[i] << '\n';
	}
}
signed main(){
	read(n,m);
	for(int i=1;i<=n;i++){
		read(t[i],c[i]);
		ctc[c[i]][t[i]]++;
	}
	for(int i=1;i<n;i++){
		int x,y;read(x,y);
		eg[x].pb(y);eg[y].pb(x);
	}
	ac::main();
    #ifdef do_while_true
		cerr<<'\n'<<"Time:"<<clock()<<" ms"<<'\n';
	#endif
	return 0;
}

Posted by toibs on Fri, 13 May 2022 03:08:06 +0300