盐城专业做网站的公司哪家好照片查询百度图片搜索

原题链接：码题集OJ-我会修改图​​​​​​

题目大意：给你一张n个点（编号为1∼n），m条边（编号为1∼m）的无向图，图上每个点都有一个点权，权值分别为a1​,a2​,…,an​，你需要支持以下询问或操作，总共有q次。

1 x把编号为x(1≤x≤m)的边删除。

2 x y询问从点x(1≤x≤n)出发，能够到达多少个不同的点t(t!=x)，满足ax​+at​=y。

思路：因为操作二需要找到与当前点连接的符合条件的点，所以可以很自然的想到并查集，但是操作一会导致并查集的图断开，并且并查集这个算法不能很好的分离出点。正难则反，如果记录每一个操作，并且倒序的进行，对于操作二，查询并不会出错，对于操作一，并查集可以很好的将二个不连通的图联通。但是仍然会超时，因为数据很大，所以需要加快操作二查询有效点的速度，可以开一个map数组，代表以某个点为根的并查集中的数的总数。

//冷静，冷静，冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=4e5+10,mod=1000000007;
ll fa[N];//并查集的数组
ll p[N];//每个点的权值
pii op[N];//建立的边
bool st[N];//删除的边
struct node
{ll cz;//操作的类型，是删除边还是求符合条件的点 ll a;//如果是删除边，这个就是边的序号，如果是求点，这就是点的编号 ll b;//先加得到得值 
}kp[N];
map<ll,ll> cnt[N];//例如cnt[2]，就是以2为首得并查集里面所有数得集合，cnt[2][1]就是以2为首的并查集中1的个数
ll find(ll x)
{if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
void hb(pii v)
{ll x=v.first,y=v.second;x=find(x);y=find(y);if(x==y)return;if(cnt[x].size()>cnt[y].size())swap(x,y);fa[x]=y;for(auto vb:cnt[x])//因为合并了，那么就要将二个并查集中的数字数量也合并，对于这种情况，将小的并查集合并到大的并查集中 {cnt[y][vb.first]+=vb.second;}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n,m,q;cin>>n>>m>>q;for(int i=1;i<=n;i++){cin>>p[i];fa[i]=i;cnt[i][p[i]]++;}for(int i=1;i<=m;i++){cin>>op[i].first>>op[i].second;}for(int i=1;i<=q;i++){cin>>kp[i].cz;if(kp[i].cz==1){cin>>kp[i].a;st[kp[i].a]=1; }else{cin>>kp[i].a>>kp[i].b;}}for(int i=1;i<=m;i++)//建立最终的并查集{if(st[i])continue;hb(op[i]);}vector<ll> ans;for(int i=q;i;i--){if(kp[i].cz==1)//相反的操作，最终合成出最初的并查集 {ll v=kp[i].a;hb(op[v]);}else{ll x=kp[i].a,y=kp[i].b;ll v=p[x];x=find(x);ans.push_back(cnt[x][y-v]-(y-v==v));//题目要求不能和自己 }}for(int i=ans.size()-1;i>=0;i--)cout<<ans[i]<<endl; return 0;
}