#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int BC=300, SZ=1<<17;
vector<int> adj[100000], BB, tree[2*SZ];
vector<tuple<int,int,int>> qry;
vector<pair<int,int>> E;
map<pair<int,int>,int> idx;
int N, ans[100000], B[100000], LL[100000], color[100000], cnt[100000];
bool EX[100000];
void add_edge(int s, int e, int v)
{
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) tree[s++].push_back(v);
if(~e&1) tree[e--].push_back(v);
}
}
void flip_edge(int c, int i)
{
if(EX[c]) add_edge(LL[c],i-1,c);
else LL[c]=i;
EX[c]^=1;
}
int find_(int a)
{
while(color[a]!=a) a=color[a];
return a;
}
void union_(int a, int b)
{
a=find_(a); b=find_(b);
if(a==b) return;
if(cnt[a]<cnt[b]) swap(a,b);
cnt[color[b]=a]+=cnt[b];
BB.push_back(b);
}
void restore(int sz)
{
while(BB.size()>sz) {
cnt[color[BB.back()]]-=cnt[BB.back()];
color[BB.back()]=color[BB.back()];
BB.pop_back();
}
}
void solve(int bit, int s, int e)
{
int m=(s+e)>>1, bsz=BB.size();
if(qry.size()<=s) return;
for(auto e: tree[bit]) union_(E[e].first,E[e].second);
if(s==e) {
ans[get<2>(qry[m])]=N-BB.size();
restore(bsz);
return;
}
solve(2*bit,s,m);
solve(2*bit+1,m+1,e);
restore(bsz);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int C, Q, w, p;
cin>>N>>C>>Q;
for(int i=0;i<C;i++) {
int t, a, b;
cin>>t>>a>>b;
if(a>b) swap(a,b);
if(idx.count({a,b})==0) {
idx[{a,b}]=E.size();
E.emplace_back(a,b);
}
B[i]=idx[{a,b}];
adj[a].push_back(i);
adj[b].push_back(i);
}
for(int i=0;i<Q;i++) {
int w, p;
cin>>w>>p;
qry.emplace_back(w,p,i);
}
sort(qry.begin(),qry.end(),[&](tuple<int,int,int> a, tuple<int,int,int> b) {
if(get<0>(a)/BC!=get<0>(b)/BC) return get<0>(a)/BC<get<0>(b)/BC;
return get<1>(a)<get<1>(b);
});
memset(LL,w=p=-1,sizeof(LL));
for(int i=0;i<Q;i++) {
auto[cw,cp,j]=qry[i];
while(w<cw) {
int c=B[++w];
auto[a,b]=E[c];
if(a<=p && p<b) continue;
flip_edge(c,i);
}
while(w>cw) {
int c=B[w--];
auto[a,b]=E[c];
if(a<=p && p<b) continue;
flip_edge(c,i);
}
while(p<cp) {
int c=++p;
for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
}
while(p>cp) {
int c=p--;
for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
}
}
for(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,i);
for(int i=0;i<N;i++) cnt[color[i]=i]=1;
solve(1,0,SZ-1);
for(int i=0;i<Q;i++) cout<<ans[i]<<'\n';
return 0;
}
Compilation message
collapse.cpp: In function 'void restore(int)':
collapse.cpp:53:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | while(BB.size()>sz) {
| ~~~~~~~~~^~~
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:63:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
63 | if(qry.size()<=s) return;
| ~~~~~~~~~~^~~
collapse.cpp: In function 'int main()':
collapse.cpp:129:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,i);
| ~^~~~~~~~~
/tmp/ccGz0o10.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccBG34IR.o:collapse.cpp:(.text.startup+0x0): first defined here
/tmp/ccGz0o10.o: In function `main':
grader.cpp:(.text.startup+0x1fc): undefined reference to `simulateCollapse(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
