题解：CF2129E Induced Subgraph Queries

简单题。

对于这个贡献，发现我们其实并不好拆位算，貌似整体维护的比拆开更有前途。

1.5\times 10^5

，开了

5 s

，我们考虑莫队，然后第

k

小可以直接用个值域分块去做。

可是这样有一个问题：我们莫队移动一个端点的代价就成为了

O(du_u)

，其中

du_u

表示

u

的度数。

不妨设在

u

的后面添加

du_u

个点，然后询问的区间对应添加后的序列改变，这样再莫队时间复杂度就是

O((n+2m)\sqrt{n+2m})

的了。正确性显然。

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=1.5e5+5,B=666,V=262143+5;
int n,m,belong[Maxn*3];
struct edge{
	int u,v;
}e[Maxn];
int q,ans[Maxn];
struct Query{
	int l,r,k,id;
}Q[Maxn];
vector<int>a[Maxn];
int sum[Maxn];
int b[V],g[V];
inline void modify(int x,int p){
	g[x/B]+=p;b[x]+=p;
}
inline int query(int k){
	int now=0;
	while(g[now]<k)k-=g[now++];
	for(int i=now*B;i<min(262144,now*B+B);i++){
		if(b[i]>=k)return i;
		k-=b[i];
	}assert(0);
}
int res[Maxn];
inline void moved(int x,int l,int r,int op){
	if(op)modify(res[x],-1);
	for(int y:a[x])
		if(l<=y&&y<=r)modify(res[y],-1),modify((res[y]^=x),1),res[x]^=y;
	if(!op)modify(res[x],1);
}
inline void solve(){
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i].clear(),sum[i]=1,res[i]=0;
	for(int i=0;i<=min(262143,n*2);i++)b[i]=g[i]=0;
	for(int i=1;i<=m;i++){
		e[i]={read(),read()};
		a[e[i].u].push_back(e[i].v);
		a[e[i].v].push_back(e[i].u);
		sum[e[i].u]++;sum[e[i].v]++;
	}
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
	q=read();
	for(int i=1;i<=q;i++)Q[i]={read(),read(),read(),i};
	sort(Q+1,Q+1+q,[&](Query a,Query b){
		if(belong[sum[a.r]]==belong[sum[b.r]]){
			if(belong[sum[a.r]]&1)return a.l<b.l;
			return a.l>b.l;
		}
		return belong[sum[a.r]]<belong[sum[b.r]];
	});
	int l=1,r=0;
	for(int i=1;i<=q;i++){
		while(Q[i].l<l)moved(--l,l,r,0);
		while(Q[i].r>r)moved(++r,l,r,0);
		while(Q[i].r<r)moved(r--,l,r,1);
		while(Q[i].l>l)moved(l++,l,r,1);
		ans[Q[i].id]=query(Q[i].k);
	}
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	for(int i=1;i<=4.5e5;i++)belong[i]=i/B;
	int T=read();
	while(T--)solve();
	return 0;
}

题解：CF2129E Induced Subgraph Queries

文章操作

相关推荐

评论

题解：CF2129E Induced Subgraph Queries