CODE

#include <cctype>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

    char ch; int flg = 1; for(;!isdigit(ch=getchar());)if(ch=='-')flg=-flg;

    for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 30005;

int n, q, w[MAXN];

namespace LCT {

	#define ls ch[x][0]

	#define rs ch[x][1]

	int ch[MAXN][2], fa[MAXN], sum[MAXN];

	bool rev[MAXN];

	inline bool isr(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

	inline bool get(int x) { return ch[fa[x]][1] == x; }

	inline void upd(int x) { sum[x] = w[x] + sum[ls] + sum[rs]; }

	inline void mt(int x) { if(rev[x]) rev[x]^=1, rev[ls]^=1, rev[rs]^=1, swap(ls, rs); }

	void mtpath(int x) { if(!isr(x)) mtpath(fa[x]); mt(x); }

	inline void rot(int x) {

		int y = fa[x], z = fa[y];

		bool l = get(x), r = l^1;

		if(!isr(y)) ch[z][get(y)] = x;

		fa[ch[x][r]] = y, fa[y] = x, fa[x] = z;

		ch[y][l] = ch[x][r], ch[x][r] = y;

		upd(y), upd(x);

	}

	inline void splay(int x) { mtpath(x);

		for(; !isr(x); rot(x))

			if(!isr(fa[x])) rot(get(x) == get(fa[x]) ? fa[x] : x);

	}

	inline void access(int x) { int y = 0;

		for(; x; x=fa[y=x]) splay(x), ch[x][1] = y, upd(x);

	}

	inline void bert(int x) { access(x), splay(x), rev[x]^=1; }

	inline int sert(int x) {

		access(x), splay(x);

		while(ch[x][0]) x=ch[x][0];

		return x;

	}

	inline bool judge(int x, int y) { bert(x); return sert(y) == x; }

	inline bool link(int x, int y) { if(judge(x, y)) return 0; fa[x] = y; return 1; }

	inline int querysum(int x, int y) { if(x == y) return w[x]; if(!judge(x, y)) return -1; return sum[y]; }

	inline void modify(int x, int val) {

		bert(x); w[x] = val; upd(x);

	}

}

int main () {

	read(n);

	for(int i = 1; i <= n; ++i)

		read(w[i]), LCT::sum[i] = w[i];

	read(q);

	int x, y; char s[2];

	while(q--) {

		while(!isalpha(s[0]=getchar()));

		while(isalpha(s[1]=getchar()));

		read(x), read(y);

		if(s[0] == 'b') puts(LCT::link(x, y) ? "yes" : "no");

		else if(s[0] == 'p') LCT::modify(x, y);

		else {

			int ans = LCT::querysum(x, y);

			if(~ans) printf("%d\n", ans);

			else puts("impossible");

		}

	}

}
巴特西

BZOJ 1180 [CROATIAN 2009]OTOCI // BZOJ 2843 极地旅行社 // Luogu P4321 [COCI 2009] OTOCI / 极地旅行社 (LCA板题)

CODE

最新文章

热门文章
