실시 간 검색 (otoci)

링크 없 음
실시 간 검색
[문제 설명]
n 개의 결점 과 모든 결점 에 대응 하 는 가중치 시작 을 제시 할 때 결점 과 결점 사이 에 다음 과 같은 세 가지 조작 이 없다.
(1) bridge A B: 결점 A 와 결점 B 가 연결 되 는 지 물 어보 고, 만약 그렇다면 "no" 를 출력 합 니 다.그렇지 않 으 면 "yes" 를 출력 하고 결점 A 와 결점 B 사이 에 방향 이 없 는 것 을 연결 합 니 다.
(2) penguins A X: 결점 A 에 대응 하 는 가중치 W A WA WA 를 X 로 변경
(3) excursion A B 가 결점 A 와 결점 B 가 연결 되 지 않 으 면 'impossible' 을 출력 한다.그렇지 않 으 면, 출력 결점 A 에서 결점 B 까지 의 경로 에 대응 하 는 값 의 합 을 출력 합 니 다.
모든 작업 을 처리 해 야 하 는 q 개의 동작 을 보 여 줍 니 다.
[형식 입력]
첫 번 째 줄 은 정수 n (1 ≤ n ≤ 30000) n (1 \ \ le n \ \ le 30000) n (1 ≤ n ≤ 30000) 을 포함 하고 결점 을 나타 내 는 수 B 를 포함한다.
두 번 째 줄 은 n 개의 정 수 를 포함 합 니 다. 두 번 째 정 수 는 i 개의 노드 가 초기 에 대응 하 는 가중치 를 표시 합 니 다.
세 번 째 줄 은 하나의 정수 q (1 ≤ q ≤ 300000) q (1 \ \ le q \ \ le 300000) q (1 ≤ q ≤ 300000) 를 포함 하여 작업 의 수 를 나타 낸다.
아래 q 줄 입 니 다. 줄 마다 하나의 조작 이 포함 되 어 있 습 니 다. 작업 의 유형 은 제목 설명 을 참조 하 십시오.
임의의 시간 에 모든 결점 에 대응 하 는 가중치 가 1 에서 1000 사이 의 정수 에 달한다.
[출력 형식]
모든 bridge 작업 과 excursion 작업 에 대응 하 는 출력 을 출력 합 니 다. 줄 마다.
[샘플 입력]
6 1 2 3 4 5 6 10 bridge 1 2 bridge 2 3 bridge 4 5 excursion 1 3 excursion 1 5 bridge 3 4 excursion 1 5 penguins 3 10 excursion 1 3 bridge 1 5
[출력 예시]
yes yes yes 6 impossible yes 15 13 no
[시간 과 공간 제한]
시간 은 1 초, 공간 은 256 MB 로 제한 된다.
해제
또한 매우 판 에 박 힌 L C T \ mathcal {LCT} LCT 입 니 다. 하나의 점 권 과 만 유지 하면 됩 니 다.
연결 성 을 판단 하고 집합 을 찾 을 수 있 습 니 다. 삭제 작업 이 없 기 때문에 f i n d r o t findroot findroot 를 사용 하지 않 으 면 사용 하지 않 습 니 다.
그러나 L C T \ \ mathcal {LCT} LCT 는 여전히 느 리 고 상수 최 적 화 를 해 야 A 의 마지막 점 이다.
코드

#include
#define R register int
#define I inline void
#define ls son[v][0]
#define rs son[v][1]
using namespace std;
const int M=3e4+5;
int son[M][2],dad[M],sum[M],sta[M],val[M],f[M],n,q;
bool rev[M];
inline bool notroot(int v){return son[dad[v]][0]==v||son[dad[v]][1]==v;}
I up(R v){sum[v]=val[v]+sum[ls]+sum[rs];}
I turn(R v){swap(ls,rs);rev[v]^=1;}
I push(R v){if(!rev[v])return;if(ls)turn(ls);if(rs)turn(rs);rev[v]=0;}
I spin(R v)
{
	int f=dad[v],ff=dad[f],k=son[f][1]==v,w=son[v][!k];
	if(notroot(f))son[ff][son[ff][1]==f]=v;
	son[v][!k]=f;son[f][k]=w;
	if(w)dad[w]=f;
	dad[f]=v;dad[v]=ff;
	up(f);up(v);
}
I splay(R v)
{
	int f,ff,top=0,u=v;
	sta[++top]=u;
	while(notroot(u))sta[++top]=u=dad[u];
	while(top)push(sta[top--]);
	while(notroot(v))
	{
		f=dad[v];ff=dad[f];
		if(notroot(f))spin((son[f][0]==v)^(son[ff][0]==f)?v:f);
		spin(v);
	}
}
I access(R v){for(R f=0;v;v=dad[f=v])splay(v),rs=f,up(v);}
I beroot(R v){access(v);splay(v);turn(v);}
I split(R x,R y){beroot(x);access(y);splay(y);}
I link(R x,R y){beroot(x);dad[x]=y;}
int find(R v){return f[v]==v?v:f[v]=find(f[v]);}
void in()
{
	scanf("%d",&n);
	for(R i=1;i<=n;++i)
	scanf("%d",&val[i]),sum[i]=val[i],f[i]=i;
}
void ac()
{
	int a,b,t1,t2;
	char ch[20];
	scanf("%d",&q);
	for(R i=1;i<=q;++i)
	{
		scanf("%s%d%d",ch,&a,&b);
		switch(ch[0])
		{
			case 'b':{
				t1=find(a);t2=find(b);
				if(t1==t2){printf("no
");break;}
				printf("yes
");link(a,b);f[t1]=t2;
				break;
			}
			case 'p':splay(a);val[a]=b;up(a);break;
			case 'e':{
				t1=find(a);t2=find(b);
				if(t1!=t2){printf("impossible
");break;}
				split(a,b);printf("%d
",sum[b]);
				break;
			}
		}
	}
}
int main()
{
	in();ac();
	return 0;
}