Codeforces 1416D — Graph and Queries

1package main2 3import (4	"bufio"5	. "fmt"6	"io"7	"math/bits"8)9 10// https://space.bilibili.com/20621411type info16 struct{ max, i int }12 13func mergeInfo16(a, b info16) info16 {14	if a.max >= b.max {15		return a16	}17	return b18}19 20type seg16 []struct {21	l, r int22	val  info1623}24 25func (t seg16) build(a []int, o, l, r int) {26	t[o].l, t[o].r = l, r27	if l == r {28		t[o].val = info16{a[l], l}29		return30	}31	m := (l + r) >> 132	t.build(a, o<<1, l, m)33	t.build(a, o<<1|1, m+1, r)34	t.maintain(o)35}36 37func (t seg16) set0(o, i int) {38	if t[o].l == t[o].r {39		t[o].val.max = 040		return41	}42	m := (t[o].l + t[o].r) >> 143	if i <= m {44		t.set0(o<<1, i)45	} else {46		t.set0(o<<1|1, i)47	}48	t.maintain(o)49}50 51func (t seg16) maintain(o int) {52	t[o].val = mergeInfo16(t[o<<1].val, t[o<<1|1].val)53}54 55func (t seg16) query(o, l, r int) info16 {56	if l <= t[o].l && t[o].r <= r {57		return t[o].val58	}59	m := (t[o].l + t[o].r) >> 160	if r <= m {61		return t.query(o<<1, l, r)62	}63	if m < l {64		return t.query(o<<1|1, l, r)65	}66	return mergeInfo16(t.query(o<<1, l, r), t.query(o<<1|1, l, r))67}68 69func cf1416D(_r io.Reader, _w io.Writer) {70	out := bufio.NewWriter(_w)71	defer out.Flush()72	_i, _n, buf := 0, 0, make([]byte, 1<<12)73	rc := func() byte {74		if _i == _n {75			_n, _ = _r.Read(buf)76			if _n == 0 {77				return 078			}79			_i = 080		}81		b := buf[_i]82		_i++83		return b84	}85	r := func() (x int) {86		b := rc()87		for ; '0' > b; b = rc() {88		}89		for ; '0' <= b; b = rc() {90			x = x*10 + int(b&15)91		}92		return93	}94 95	n, m, q := r(), r(), r()96	a := make([]int, n)97	for i := range a {98		a[i] = r()99	}100	es := make([]struct{ v, w int }, m)101	for i := range es {102		es[i].v = r() - 1103		es[i].w = r() - 1104	}105	qs := make([]struct{ tp, v int }, q)106	del := make([]bool, m)107	for i := range qs {108		qs[i].tp = r()109		qs[i].v = r() - 1110		if qs[i].tp == 2 {111			del[qs[i].v] = true112		}113	}114 115	g := make([][]int, n*2)116	fa := make([]int, n*2)117	for i := range fa {118		fa[i] = i119	}120	var find func(int) int121	find = func(x int) int {122		if fa[x] != x {123			fa[x] = find(fa[x])124		}125		return fa[x]126	}127	merge := func(v, w int) {128		v = find(v)129		w = find(w)130		if v == w {131			return132		}133		fa[v] = n134		fa[w] = n135		g[n] = append(g[n], v, w)136		n++137	}138	for i, d := range del {139		if !d {140			merge(es[i].v, es[i].w)141		}142	}143 144	for i := q - 1; i >= 0; i-- {145		p := &qs[i]146		if p.tp == 1 {147			p.v = find(p.v)148		} else {149			e := es[p.v]150			merge(e.v, e.w)151		}152	}153 154	nodes := make([]struct{ in, out int }, n)155	at := make([]int, n)156	clock := -1157	var dfs func(int)158	dfs = func(v int) {159		clock++160		if v < len(a) {161			at[clock] = a[v]162		}163		nodes[v].in = clock164		for _, w := range g[v] {165			dfs(w)166		}167		nodes[v].out = clock168	}169	for i := range nodes {170		if find(i) == i { // 根171			dfs(i)172		}173	}174 175	t := make(seg16, 2<<bits.Len(uint(n-1)))176	t.build(at, 1, 0, n-1)177	for _, p := range qs {178		if p.tp == 2 {179			continue180		}181		node := nodes[p.v]182		res := t.query(1, node.in, node.out)183		Fprintln(out, res.max)184		if res.max > 0 {185			t.set0(1, res.i)186		}187	}188}189 190//func main() { cf1416D(os.Stdin, os.Stdout) }191