题解：CF2129E Induced Subgraph Queries
Netheris
·
·
题解
简单题。
对于这个贡献，发现我们其实并不好拆位算，貌似整体维护的比拆开更有前途。
可是这样有一个问题：我们莫队移动一个端点的代价就成为了 $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;
}
```