loj #2049. 「HNOI2016」网络 ( JSOIP2022练习赛1 t2 )

题面太长

操作应当是按照时间插入，此时一个思路是考虑线段树分治，但是发现并不需要 .

考虑加入一个交互会发生什么，除了当前路径上的点最大值会取 \(\max\) ，因为当前路径在树链剖分上是 \(\log n\) 个区间，那么，除去这个路径的部分也是 \(\log n\) 个区间 . 依旧可以树链剖分 + 线段树 .

此时，这个操作是需要撤销的，所以考虑维护一个 \(\rm{multiset}\) 来支持撤销的操作 . 此时的时间复杂度就是 \(O(n\log^3n)\) . 在 loj 开了 Ofast 需要跑接近 3s，显然不太好 .

**此时考虑将 \(\rm{multiset}\) 换成 \(\rm{priority\_queue}\) 则会快很多，考虑维护两个栈 \(q_1\) 和 \(q_2\)，其中 \(q_1\) 维护当前出现过，还没有被删除的值 , \(q_2\) 维护删除的值 . 当 \(q_1.top()=q_2.top()\) 的时候，需要弹出 \(q_1.top()\) **. 具体实现 :

class node{
	public:
	priority_queueq1,q2;
	inline void ins(int val){q1.push(val);}
	inline void era(int val){q2.push(val);}
	inline int top(){
		while(!q2.empty()&&q2.top()==q1.top())q1.pop(),q2.pop();
		return q1.empty()?-1:q1.top();
	}
};

将操作改成用两个 \(\rm{pq}\) 维护就好很多 ，每个点跑了 300ms 不到，是 10 倍的差距，同时在内存上也显示出了优势，从接近 400MB 变为了 75MB- .

时间复杂度 : \(O(n\log^3 n)\)

空间复杂度 : \(O(n\log n)\)

code

//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include
using namespace std;
char in[100005];
int iiter=0,llen=0;
inline char get(){
	if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
	if(llen==0)return EOF;
	return in[iiter++];
}
inline int rd(){
	char ch=get();while(ch<'0'||ch>'9')ch=get();
	int res=0;while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=get();
	return res;
}
inline void pr(int res){
	if(res==0){putchar('0');return;}
	static int out[10];int len=0;
	while(res)out[len++]=res%10,res/=10;
	for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int N=1e5+10,M=2e5+10;
int n,m;
vectorg[N];
int id[N],hv[N],sz[N],hd[N],pa[N],dep[N],Pos[N],cnt=0;
void get_hv(int x,int fa){
	sz[x]=1;hv[x]=-1;pa[x]=fa;
	for(auto to:g[x]){
		if(to==fa)continue;
		dep[to]=dep[x]+1;
		get_hv(to,x);
		sz[x]+=sz[to];
		if(hv[x]==-1||sz[to]>sz[hv[x]]){
			hv[x]=to;
		}
	}
}
void depo(int x,int fa){
	if(hv[x]!=-1){
		hd[hv[x]]=hd[x];
		Pos[cnt]=hv[x];
		id[hv[x]]=cnt++;
		depo(hv[x],x);
	}
	for(auto to:g[x]){
		if(to==fa||to==hv[x])continue;
		hd[to]=to;
		Pos[cnt]=to;
		id[to]=cnt++;
		depo(to,x);
	}
}
class SGT{
public:
	class node{
		public:
		priority_queueq1,q2;
		inline void ins(int val){q1.push(val);}
		inline void era(int val){q2.push(val);}
		inline int top(){
			while(!q2.empty()&&q2.top()==q1.top())q1.pop(),q2.pop();
			return q1.empty()?-1:q1.top();
		}
	}ts[N<<2];
	void upd_add(int x,int l,int r,int cl,int cr,int val){
		if(l==cl&&r==cr){
			ts[x].ins(val);
			return;
		}
		int mid=(l+r)>>1;
		if(cr<=mid)upd_add(x<<1,l,mid,cl,cr,val);
		else if(mid+1<=cl)upd_add(x<<1|1,mid+1,r,cl,cr,val);
		else upd_add(x<<1,l,mid,cl,mid,val),upd_add(x<<1|1,mid+1,r,mid+1,cr,val);
	}
	void upd_del(int x,int l,int r,int cl,int cr,int val){
		if(l==cl&&r==cr){
			ts[x].era(val);
			return;
		}
		int mid=(l+r)>>1;
		if(cr<=mid)upd_del(x<<1,l,mid,cl,cr,val);
		else if(mid+1<=cl)upd_del(x<<1|1,mid+1,r,cl,cr,val);
		else upd_del(x<<1,l,mid,cl,mid,val),upd_del(x<<1|1,mid+1,r,mid+1,cr,val);
	}
	int qry(int x,int l,int r,int pos){
		if(l==r)return ts[x].top();
		int mid=(l+r)>>1;
		if(pos<=mid)return max(qry(x<<1,l,mid,pos),ts[x].top());
		else return max(qry(x<<1|1,mid+1,r,pos),ts[x].top());
	}
}T;
int tp[M],A[M],B[M],w[M],t[M],pos[M],ans[M];
int lca(int u,int v){
	while(hd[u]!=hd[v]){
		if(dep[hd[u]]>dep[hd[v]])swap(u,v);
		v=pa[hd[v]];
	}
	return dep[u] >v,int tmp
	sort(v.begin(),v.end());
	if(0 >ve;
	int u=A[i],v=B[i],r=lca(u,v);
	while(hd[u]!=hd[r]){
		ve.pb(mp(id[hd[u]],id[u]));
		u=pa[hd[u]];
	}
	ve.pb(mp(id[r],id[u]));
	while(hd[v]!=hd[r]){
		ve.pb(mp(id[hd[v]],id[v]));
		v=pa[hd[v]];
	}
	if(id[r]+1<=id[v])ve.pb(mp(id[r]+1,id[v]));
	op_ins(ve,i);
}
void op_del(vector >v,int tmp){
	sort(v.begin(),v.end());
	if(0 >ve;
	while(hd[u]!=hd[r]){
		ve.pb(mp(id[hd[u]],id[u]));
		u=pa[hd[u]];
	}
	ve.pb(mp(id[r],id[u]));
	while(hd[v]!=hd[r]){
		ve.pb(mp(id[hd[v]],id[v]));
		v=pa[hd[v]];
	}
	if(id[r]+1<=id[v])ve.pb(mp(id[r]+1,id[v]));
	op_del(ve,i);
}
vectorQ[M];
int main(){
	n=rd();m=rd();
	for(int i=0;i