例如测试点19有些人的代码就出现了把9算成8的情况(比如说我),为什么会出现这种情况?
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct Point{
int x,y;
bool operator <(const Point &a)const{
return x==a.x?y<a.y:x<a.x;
}
};
struct edge{
int x,y,val;
};
vector <edge> e[N<<1];
map <Point,int> mp;
struct ques{
int op,x,y,val;
}wt[N];
int n,m,f[N],siz[N],s[N<<4],top,ans[N],op,tlhdl;
void insert(int x,int l,int r,int s,int t,Point k,int tag){
if(l>=s&&r<=t){
edge tmp=(edge){k.x,k.y,tag};
e[x].push_back(tmp);
return;
}
int mid=(l+r)>>1;
if(s<=mid)insert(x<<1,l,mid,s,t,k,tag);
if(t>mid)insert(x<<1|1,mid+1,r,s,t,k,tag);
}
int getf(int u){
if(f[u]==u)return u;
return getf(f[u]);
}
void merge(int x,int y){
x=getf(x),y=getf(y);
if(siz[x]<siz[y])swap(x,y);
s[++top]=y;
if(x!=y)siz[x]+=siz[y];
f[y]=x;
}
void del(){
int x=s[top];
// if(top==0)return;
if(x!=f[x])siz[f[x]]-=siz[x];
f[x]=x;
top--;
}
int ans1[N];
void dfs(int x,int l,int r,int val){
int last=top;
for(int i = 0;i < e[x].size();i++)
if(e[x][i].val<=val)
merge(e[x][i].x,e[x][i].y);
if(l==r){
if(ans1[l]==-1&&getf(wt[l].x)==getf(wt[l].y)&&wt[l].op==2)
ans1[l]=val;
}
else{
int mid=(l+r)>>1;
dfs(x<<1,l,mid,val);
dfs(x<<1|1,mid+1,r,val);
}
while(last<top)del();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= m;i++){
cin >> wt[i].op >> wt[i].x >> wt[i].y;
if(wt[i].x>wt[i].y)swap(wt[i].x,wt[i].y);
if(wt[i].op==0)cin >> wt[i].val;
}
memset(ans1,-1,sizeof(ans1));
for(int i = 1;i <= m;i++){
Point tmp=(Point){wt[i].x,wt[i].y};
if(wt[i].op==0)mp[tmp]=i;
else if(wt[i].op==1){
insert(1,1,m,mp[tmp],i-1,tmp,wt[mp[tmp]].val);
mp[tmp]=-1;
}
}
for(int i = 1;i <= m;i++){
Point tmp=(Point){wt[i].x,wt[i].y};
if(mp[tmp]!=-1&&wt[i].op==0)insert(1,1,m,mp[tmp],m,tmp,wt[i].val);
}
for(int j = 0;j <= 10;j++){
for(int i = 1;i <= n;i++)siz[i]=1,f[i]=i;
dfs(1,1,m,j);
}
for(int i = 1;i <= m;i++)
if(wt[i].op==2)
cout << ans1[i] << "\n";
return 0;
}