#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct dsu
{
vector<int>parent,sz;
dsu(int size)
{
parent.resize(size),sz.resize(size);
for(int i=0;i<size;i++)parent[i]=i,sz[i]=1;
}
int find_parent(int x)
{
if(x==parent[x])return x;
return parent[x]=find_parent(parent[x]);
}
void align(int a,int b)
{
a=find_parent(a),b=find_parent(b);
if(a==b)return;
if(sz[a]<sz[b])swap(a,b);
sz[a]+=sz[b],parent[b]=a;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin>>n>>m;
vector<pair<int,int>>cur_edge(m);
vector<pair<int,int>>edge_info;
vector<vector<int>>edges;
vector<int>compress;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v>>cur_edge[i].second;
compress.push_back(cur_edge[i].second);
cur_edge[i].first=0;
u--,v--;
edge_info.push_back({u,v});
}
int q;
cin>>q;
vector<vector<int>>queries(q,vector<int>(3));
for(auto &x:queries)
{
for(auto &y:x)cin>>y;
compress.push_back(x[2]);
x[1]--;
}
sort(compress.begin(),compress.end());
compress.erase(unique(compress.begin(),compress.end()),compress.end());
for(auto &x:cur_edge)x.second=lower_bound(compress.begin(),compress.end(),x.second)-compress.begin();
for(auto &x:queries)x[2]=lower_bound(compress.begin(),compress.end(),x[2])-compress.begin();
for(int i=0;i<q;i++)
{
if(queries[i][0]==2)continue;
edges.push_back({cur_edge[queries[i][1]].first,i-1,cur_edge[queries[i][1]].second,queries[i][1]});
cur_edge[queries[i][1]]={i,queries[i][2]};
}
for(int i=0;i<m;i++)edges.push_back({cur_edge[i].first,q-1,cur_edge[i].second,i});
int block_size=sqrt(q);
vector<vector<int>>base_push(compress.size());
vector<vector<int>>solve_queries(compress.size());
vector<int>weird_idx;
vector<int>ans(q);
for(int i=0;i<q;i+=block_size)
{
int r=min(q,i+block_size)-1;
for(int j=0;j<edges.size();j++)
{
if(edges[j][0]>=i&&edges[j][0]<=r||edges[j][1]>=i&&edges[j][1]<=r)weird_idx.push_back(j);
else if(edges[j][0]<=i&&edges[j][1]>=r)base_push[edges[j][2]].push_back(edges[j][3]);
}
for(int j=i;j<=r;j++)
{
if(queries[j][0]==1)continue;
solve_queries[queries[j][2]].push_back(j);
}
dsu ds(n);
vector<int>idx(n);
int cur_idx=1;
for(int it=compress.size()-1;it>=0;it--)
{
for(auto &x:base_push[it])ds.align(edge_info[x].first,edge_info[x].second);
for(auto &x:solve_queries[it])
{
int bad_idx=cur_idx++;
vector<int>all_v;
int best_v=ds.find_parent(queries[x][1]);
idx[best_v]=cur_idx++;
all_v.push_back(best_v);
for(auto &y:weird_idx)
{
if(edges[y][0]<=x&&edges[y][1]>=x&&edges[y][2]>=queries[x][2])
{
int v=edges[y][3];
int f1=ds.find_parent(edge_info[v].first),f2=ds.find_parent(edge_info[v].second);
if(idx[f1]<=bad_idx)idx[f1]=cur_idx++,all_v.push_back(f1);
if(idx[f2]<=bad_idx)idx[f2]=cur_idx++,all_v.push_back(f2);
}
}
dsu cur_s(cur_idx-bad_idx);
for(auto &y:weird_idx)
{
if(edges[y][0]<=x&&edges[y][1]>=x&&edges[y][2]>=queries[x][2])
{
int v=edges[y][3];
int f1=ds.find_parent(edge_info[v].first),f2=ds.find_parent(edge_info[v].second);
cur_s.align(idx[f1]-bad_idx-1,idx[f2]-bad_idx-1);
}
}
int nice_idx=idx[ds.find_parent(queries[x][1])];
if(nice_idx<=bad_idx)continue;
nice_idx=nice_idx-bad_idx-1;
nice_idx=cur_s.find_parent(nice_idx);
for(int i=0;i<all_v.size();i++)if(cur_s.find_parent(i)==nice_idx)ans[x]+=ds.sz[ds.find_parent(all_v[i])];
}
}
for(int i=0;i<compress.size();i++)base_push[i].clear(),solve_queries[i].clear();
weird_idx.clear();
}
for(int i=0;i<q;i++)
{
if(queries[i][0]==1)continue;
cout<<ans[i]<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |