Lvat_s Blog

事实证明Lvat_s就是一个sb。。。

这题调试了2天

其实死在了一个很明显的错误上面

在倒数第二个关于q的循环里，我写道：

if(reans>e[i].v){……}

此时i明明表示q好不好……

正确的写法是：

if(reans>e[ask[i].ans].v){……}

还是贴一下代码吧，跑得很慢（19104ms）

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m,q,f[100005];

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Node{
int v,mx,rev,id;
Node *ch[2],*fa,*mxe;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root[1100005],*Null;

Node::Node(int val,Node *fat){
ch[0]=ch[1]=Null;
if(val)mxe=this;
else mxe=Null;
fa=fat;
v=mx=val;
rev=id=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
    rev=0;
}
}

void Node::Pushup(){
mx=v;
if(v)mxe=this;
else mxe=Null;
if(ch[0]!=Null && ch[0]->mx>mx){mx=ch[0]->mx;mxe=ch[0]->mxe;}
if(ch[1]!=Null && ch[1]->mx>mx){mx=ch[1]->mx;mxe=ch[1]->mxe;}
}

int Notroot(Node *p){
return (p->fa->ch[0]==p)||(p->fa->ch[1]==p);
}

void Prepare(Node *p){
if(Notroot(p))Prepare(p->fa);
p->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
swap(x->ch[0],x->ch[1]);
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}
}

int GetMx(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
return y->mx;
}

Node *MxAddress(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
return y->mxe;
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->fa=p->ch[0]=p->ch[1]=p->mxe=p;
p->v=p->mx=-2100000000;
p->rev=p->id=0;
return p;
}

Node *ToLct(int x){
return root[x];
}

struct Edge{
int a,b,v,id,del;
friend bool operator<(Edge a,Edge b){
return (a.a<b.a)||(a.a==b.a && a.b<b.b);
}
}e[1000005];

bool cmp1(Edge a,Edge b){
return a.v<b.v;
}

bool cmp2(Edge a,Edge b){
return a.id<b.id;
}

struct Ask{
int k,x,y,ans;
}ask[100005];

int Div(int x,int y){
int l=1,r=m;
while(l<=r){
	int mid=(l+r)>>1;
	if(e[mid].a==x && e[mid].b==y)return mid;
	if(e[mid].a<x || (e[mid].a==x && e[mid].b<y)){l=mid+1;}
	else r=mid-1;
}
return (l+r)>>1;
}

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int x,int y){if(x<y)f[y]=x;else f[x]=y;}

int main(){
freopen("2594.in","r",stdin);
freopen("2594.out","w",stdout);
Read(n);Read(m);Read(q);
Null=GetNull();
for(int i=1;i<=m;i++){
	Read(e[i].a);Read(e[i].b);Read(e[i].v);
	if(e[i].a>e[i].b)swap(e[i].a,e[i].b);
}
sort(e+1,e+m+1,cmp1);
for(int i=1;i<=n;i++)root[i]=new Node(0,Null);
for(int i=1;i<=m;i++){
	e[i].id=i;
	root[i+n]=new Node(e[i].v,Null);
}
sort(e+1,e+m+1);
for(int i=1;i<=q;i++){
	Read(ask[i].k);
	Read(ask[i].x);
	Read(ask[i].y);
	if(ask[i].x>ask[i].y)swap(ask[i].x,ask[i].y);
	if(ask[i].k==2){
		int sci=Div(ask[i].x,ask[i].y);
		ask[i].ans=e[sci].id;
		e[sci].del=1;
	}
}
sort(e+1,e+m+1,cmp2);
for(int i=1;i<=n;i++)f[i]=i;
int tot=0;
for(int i=1;i<=m;i++){
	root[i+n]->id=i;
	if(!e[i].del && Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		Link(ToLct(e[i].a),ToLct(i+n));
		Link(ToLct(e[i].b),ToLct(i+n));
		tot++;
		if(tot==n-1)break;
	}
}
for(int i=q;i>=1;i--){
	if(ask[i].k==1){
		ask[i].ans=GetMx(ToLct(ask[i].x),ToLct(ask[i].y));
	}
	else {
		Node *mx=MxAddress(ToLct(ask[i].x),ToLct(ask[i].y));
		int reans=mx->mx;
		if(reans>e[ask[i].ans].v){
			Cut(ToLct(e[mx->id].a),mx);
			Cut(ToLct(e[mx->id].b),mx);
			Link(ToLct(ask[i].x),ToLct(ask[i].ans+n));
			Link(ToLct(ask[i].y),ToLct(ask[i].ans+n));
		}
	}
}
for(int i=1;i<=q;i++){
	if(ask[i].k==1)printf("%d\n",ask[i].ans);
}
return 0;
}