BZOJ 2959 长跑

2019-11-10 18:57:09

字体：大中小

来源：转载

供稿：网友

LCT+缩边双＋并查集

　显然如果进入一个边双联通分量，那一定能取遍所有点再出来．于是只要维护边双即可．对于加边，需要缩点，用LCT即可，判断是不是在一个边双里用个并查集就行．

　此题时限比较紧．注意到在缩点之后，LCT上的操基本只有 access需要查询真实父亲（因为缩点之后的点单独属于一个分量），其他操作并不需要查并查集．把这个优化掉就能过了．．．？

#include<cstdio>#include<algorithm>#define N 150005#define IL inlineusing namespace std;namespace IO { char _B[1 << 26], *_S = _B; #define Begin() fread(_B, 1, 1 << 26, stdin) #define inline __inline__ __attribute__((always_inline)) inline int read() { register int x, b; for ( ; *_S < '-'; ++ _S); for (*_S != '-' ? x = *_S ++ - '0', b = 1 : (_S ++, x = b = 0); *_S >= '0'; x = (x << 3) + (x << 1) + *_S ++ - '0'); return b ? x : -x; }}namespace runzhe2000{ using namespace IO; int n, m, val[N]; struct UFS { int f[N]; int find(int x){return x == f[x] ? x : f[x] = find(f[x]);} inline void unio(int x, int y){f[find(x)] = find(y);} }s, st; struct node *tot, *null, *pos[N], *fir; struct node { node *ch[2], *fa; int sum, val, rev; IL node* F(){return pos[s.find(this - fir)];} IL node* Fa(){return fa->F() == F() ? null : fa->F();} }mem[N], *_t; node *newnode(int v) { node *p = ++tot; *p = *null; p->val = p->sum = v; return p; } void init() { pos[0] = null = tot = fir = mem; null->ch[0] = null->ch[1] = null->fa = null; null->sum = null->val = null->rev = 0; } int type(node *p){return p->fa->ch[1]==p;} bool isroot(node *p){return p != p->fa->ch[type(p)];} void pushup(node *p){p->sum = p->val + p->ch[0]->sum + p->ch[1]->sum;} void pushdown(node *p) { if(p->rev) { _t = p->ch[0], p->ch[0] = p->ch[1], p->ch[1] = _t; p->ch[0] = p->ch[0], p->ch[1] = p->ch[1]; p->ch[0]->rev ^= 1, p->ch[1]->rev ^= 1, p->rev = 0; } } void PRe(node *p){if(!isroot(p)) pre(p->Fa()); pushdown(p);} void rotate(node *p) { node *f = p->fa; int d = type(p); (p->fa = f->fa), !isroot(f) ? p->fa->ch[type(f)] = p : 0; (f->ch[d] = p->ch[!d]) != null ? p->ch[!d]->fa = f : 0; p->ch[!d] = f, f->fa = p; pushup(f); } IL void splay(node *p) { for(pre(p); !isroot(p);) { node *f = p->fa; if(isroot(f)) rotate(p); else {if(type(p) == type(f)) rotate(f); else rotate(p); rotate(p);} } pushup(p); } IL void access(node *p) { node *tmp = null; for(; p != null; p = (tmp = p)->fa) { splay(p); p->ch[1] = tmp; p->fa = p->Fa(); pushup(p); } } IL void makeroot(node *p) { access(p); splay(p); p->rev ^= 1; } IL void link(node *a, node *b) { makeroot(a); a->fa = b; } void reduc(node *a, node *b) { if(a == null) return; s.unio(a - mem, b - mem); b->val += a->val; reduc(a->ch[0], b); reduc(a->ch[1], b); a->ch[0] = a->ch[1] = null; } IL void main() { int happy = Begin(); n = read(); m = read(); init(); for(int i = 1, v; i <= n; i++) { s.f[i] = i, st.f[i] = i; pos[i] = newnode(val[i] = read()); } int op, A, B; node *pA, *pB; for(int i = 1; i <= m; i++) { op = read(), A = read(), B = read(); pA = pos[A]->F(), pB = pos[B]->F(); if(op == 1) { if(st.find(A) != st.find(B))link(pA, pB), st.unio(A, B); else { int fA = s.find(A), fB = s.find(B); if(fA != fB) { makeroot(pA); access(pB); splay(pB); reduc(pB->ch[0]->F(), pB); pushup(pB); } } } else if(op == 2) { splay(pA); pA->val += B - val[A]; pushup(pA); val[A] = B; } else { if(st.find(A) != st.find(B)) puts("-1"); else { makeroot(pA); access(pB); splay(pB); printf("%d/n",pB->sum); } } } }}int main(){ runzhe2000::main();}

上一篇：XDebug基本配置项说明

下一篇：Database,Uva1592