TLE玄关
查看原帖
TLE玄关
1457824
__assassin_楼主2025/6/19 16:25

请问哪还能优化时间复杂度

#include<bits/stdc++.h>
using namespace std;
const int N=4e4;

int n,m;

int a[N+10];
int d[N+10];

int f[N+10],deep[N+10],siz[N+10],top[N+10],son[N+10];
int c1[N+10],c2[N+10];
int num,olx[(N<<1)+10];
vector<int> v[N+10];

int len,p[N+10];
int t[N+10],use[N+10];
struct q{int l,r,i,lca;}c[N+10];
int ans[N+10],sum;

int in(){
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+(c-'0');
		c=getchar();
	}
	return x*y;
}
void out(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else out(x/10),putchar(x%10+'0');
	putchar('\n');
}

void dfs1(int u,int fa){
	f[u]=fa;
	deep[u]=deep[fa]+1;
	c1[u]=++num;
	siz[u]=1;
	olx[num]=u;
	for(int i=0;i<v[u].size();i++){
		int j=v[u][i];
		if(j==fa) continue;
		dfs1(j,u);
		siz[u]+=siz[j];
		if(son[u]==0||siz[son[u]]<siz[j]) son[u]=j;
	}
	c2[u]=++num;
	olx[num]=u;
} 
void dfs2(int u,int tu){
	top[u]=tu;
	if(son[u]==0) return;
	dfs2(son[u],tu);
	for(int i=0;i<v[u].size();i++){
		int j=v[u][i];
		if(j==f[u]||j==son[u]) continue;
		dfs2(j,j);
	}
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		(deep[top[x]]<deep[top[y]])?y=f[top[y]]:x=f[top[x]];
	}
	return (deep[x]>deep[y])?y:x;
}

bool cmp(q x,q y){
	return (p[x.l]==p[y.l])?x.r<y.r:p[x.l]<p[y.l];
}
void del(int x){
	sum-=(--t[a[x]]==0);
}
void add(int x){
	sum+=(++t[a[x]]==1);
}
void change(int x){
	(!use[x])?add(x):del(x);
	use[x]^=1;
}
int main(){
	n=in(),m=in();
	len=2*n/sqrt(2*m/3);
	for(int i=1;i<=n;i++){
		a[i]=in();
		d[i]=a[i];
		p[i]=(i-1)/len+1;
	}
	sort(d+1,d+n+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(d+1,d+n+1,a[i])-d;
	for(int i=1;i<n;i++){
		int x,y;
		x=in(),y=in();
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=m;i++){
		int l,r;
		l=in(),r=in();
		if(c1[l]>c1[r]) swap(l,r);
		c[i].i=i;
		c[i].lca=lca(l,r);
		(l==c[i].lca)?(c[i].l=c1[l],c[i].r=c1[r],c[i].lca=0):(c[i].l=c2[l],c[i].r=c1[r]);
	}
	sort(c+1,c+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l<c[i].l) change(olx[l++]);
		while(r>c[i].r) change(olx[r--]);
		while(l>c[i].l) change(olx[--l]);
		while(r<c[i].r) change(olx[++r]);
		if(c[i].lca!=0) change(c[i].lca);
		ans[c[i].i]=sum;
		if(c[i].lca!=0) change(c[i].lca);
	}
	for(int i=1;i<=m;i++) out(ans[i]);
	return 0;
}

2025/6/19 16:25
加载中...