一种离线处理方法
可以处理“具体哪个修改对询问有影响”、可以贡献不独立、可以支持插入删除。
例题
对这道题来说，对修改开线段树，线段树上每个节点开一个 \(vector\) 来维护出现在这段区间的线段，加入一个线段的区间，直接在区间查询时对所包含的节点压入这条线段就可以。
然后从根节点递归，先左子树再右子树，对途中经过的结点上的线段计算答案，这里用不压缩路径的并查集维护。对于加入，只需要将个数小的合并到个数多的（启发式合并），只需要将祖先的父亲和大小更改，所以开一个栈维护这个操作，对于删除就是将祖先更改过来。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
struct asd{
int op,x,y;
}a[N],b[N];
struct tree{
int l,r;
}tr[N*4];
struct qwe{
int x,y,sizx,sizy;
}st[N];
int top=0;
vector<int> s[N*4];
map<int,int> mp[N],rk[N];
int cnt=0;
int mgml(int x,int p){
int ans=1;
while(p){
if(p&1) ans=(ans*x)%mod;
x=(x*x)%mod;
p>>=1;
}
return ans;
}
void build(int p,int l,int r){
tr[p].l=l,tr[p].r=r;
if(l==r) return;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void change(int p,int l,int r,int v){
if(tr[p].l>=l && tr[p].r<=r){
s[p].push_back(v);
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid) change(p*2,l,r,v);
if(r>mid) change(p*2+1,l,r,v);
}
int fa[N];
int sum[N];
int get_fa(int x){
if(fa[x]==x) return x;
else return get_fa(fa[x]);
}
int ans=1;
int anss[N];
void add(int p){
for(int i=0;i<s[p].size();i++){
int id=s[p][i];
int x=b[id].x,y=b[id].y;
int fx=get_fa(x),fy=get_fa(y);
if(fx==fy) continue;
if(sum[fx]>sum[fy]) swap(fx,fy);
st[++top]={fx,fy,sum[fx],sum[fy]};
fa[fx]=fy;
ans=ans*(sum[fx]+sum[fy])%mod*mgml(sum[fx]*sum[fy]%mod,mod-2)%mod;
ans%=mod;
sum[fy]+=sum[fx];
}
}
void dele(int now,int p){
while(top>now){
int x=st[top].x,y=st[top].y;
int sizx=st[top].sizx,sizy=st[top].sizy;
ans=ans*sizx%mod*sizy%mod*mgml((sizx+sizy)%mod,mod-2)%mod;
ans%=mod;
fa[x]=x,fa[y]=y;
sum[x]=sizx,sum[y]=sizy;
top--;
}
}
void dfs(int p){
int now=top;
add(p);
if(tr[p].l==tr[p].r){
anss[tr[p].l]=ans;
}
else{
dfs(p*2),dfs(p*2+1);
}
dele(now,p);
}
signed main(){
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
fa[i]=i;
sum[i]=1;
}
build(1,1,m);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&a[i].op,&a[i].x,&a[i].y);
if(rk[a[i].x][a[i].y]==0){
rk[a[i].x][a[i].y]=rk[a[i].x][a[i].y]=++cnt;
b[cnt].x=a[i].x,b[cnt].y=a[i].y;
}
}
for(int i=1;i<=m;i++){
if(a[i].op==1){
mp[a[i].x][a[i].y]=mp[a[i].y][a[i].x]=i;
}
else{
int st=mp[a[i].x][a[i].y];
mp[a[i].x][a[i].y]=mp[a[i].y][a[i].x]=0;
change(1,st,i-1,rk[a[i].x][a[i].y]);
}
}
for(int i=1;i<=m;i++){
if(mp[a[i].x][a[i].y]){
int st=mp[a[i].x][a[i].y];
mp[a[i].x][a[i].y]=mp[a[i].y][a[i].x]=0;
change(1,st,m,rk[a[i].x][a[i].y]);
}
}
dfs(1);
for(int i=1;i<=m;i++){
cout<<anss[i]<<endl;
}
}