結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-03 12:25:33
言語 Go
(1.22.1)
結果
AC  
実行時間 337 ms / 2,000 ms
コード長 3,961 bytes
コンパイル時間 15,880 ms
コンパイル使用メモリ 210,172 KB
実行使用メモリ 47,440 KB
最終ジャッジ日時 2023-10-18 00:55:53
合計ジャッジ時間 25,700 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 175 ms
7,884 KB
testcase_01 AC 175 ms
7,892 KB
testcase_02 AC 174 ms
7,900 KB
testcase_03 AC 153 ms
7,740 KB
testcase_04 AC 179 ms
7,900 KB
testcase_05 AC 155 ms
14,384 KB
testcase_06 AC 97 ms
7,884 KB
testcase_07 AC 11 ms
7,728 KB
testcase_08 AC 309 ms
22,860 KB
testcase_09 AC 37 ms
9,980 KB
testcase_10 AC 139 ms
18,620 KB
testcase_11 AC 120 ms
14,288 KB
testcase_12 AC 170 ms
14,380 KB
testcase_13 AC 297 ms
27,084 KB
testcase_14 AC 123 ms
18,404 KB
testcase_15 AC 1 ms
4,372 KB
testcase_16 AC 314 ms
22,880 KB
testcase_17 AC 310 ms
22,880 KB
testcase_18 AC 307 ms
22,876 KB
testcase_19 AC 314 ms
22,880 KB
testcase_20 AC 321 ms
22,876 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 275 ms
24,856 KB
testcase_24 AC 286 ms
22,988 KB
testcase_25 AC 312 ms
24,584 KB
testcase_26 AC 337 ms
47,440 KB
testcase_27 AC 235 ms
47,344 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	// fmt.Println(BracketTree("(())()"))
	// https://yukicoder.me/problems/no/1778
	// 给定一个有效的括号序列,每次可以删除一段匹配的括号
	// 给定q个查询,每个查询形如 [start1,start2]
	// 求包含这两段括号的区间中最靠内部的一段区间

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, q int
	fmt.Fscan(in, &n, &q)
	var s string
	fmt.Fscan(in, &s)

	tree, leftRight := BracketTree(s)

	idToRoot := make([]int, n) // 每个起点/终点位置对应的树节点 [0, n)
	for i := 1; i < len(leftRight); i++ {
		left, right := leftRight[i][0], leftRight[i][1]
		idToRoot[left] = i
		idToRoot[right] = i
	}

	lca := NewLCA((n / 2) + 1)
	for i := 0; i < len(tree); i++ {
		for _, j := range tree[i] {
			lca.AddEdge(i, j)
		}
	}
	lca.Build(0)

	for i := 0; i < q; i++ {
		var start, end int // 1<=start<end<=n
		fmt.Fscan(in, &start, &end)
		start--
		end--
		root1, root2 := idToRoot[start], idToRoot[end]
		lca_ := lca.LCA(root1, root2)
		if lca_ == 0 { // 不被包含
			fmt.Fprintln(out, -1)
		} else {
			left, right := leftRight[lca_][0], leftRight[lca_][1]
			fmt.Fprintln(out, left+1, right+1)
		}
	}
}

// BracketTree :有效括号序列转换成树.
//  (())() → 得到 `(n/2)+1` 个结点,其中0号结点是虚拟根结点.
//  tree: [[1 3] [2] [] []] (有向邻接表)
//  leftRight: [[0 5] [0 3] [1 2] [4 5]] (每个顶点的括号序/欧拉序)
//
//            0 (0,5)
//           / \
//    (0,3) 1   3 (4,5)
//         /
//  (1,2) 2
func BracketTree(s string) (tree [][]int, leftRight [][2]int) {
	n := len(s) / 2
	tree = make([][]int, n+1)
	leftRight = make([][2]int, n+1)
	now, nxt := 0, 1
	leftRight[0] = [2]int{0, len(s)}
	par := make([]int, n+1)
	for i := range par {
		par[i] = -1
	}

	for i := range s {
		if s[i] == '(' {
			tree[now] = append(tree[now], nxt)
			par[nxt] = now
			leftRight[nxt][0] = i
			now = nxt
			nxt++
		}
		if s[i] == ')' {
			leftRight[now][1] = i
			now = par[now]
		}
	}

	return
}

type LCAHLD struct {
	Depth, Parent      []int
	Tree               [][]int
	dfn, top, heavySon []int
	dfnId              int
}

func NewLCA(n int) *LCAHLD {
	tree := make([][]int, n)
	dfn := make([]int, n)      // vertex => dfn
	top := make([]int, n)      // 所处轻/重链的顶点（深度最小），轻链的顶点为自身
	depth := make([]int, n)    // 深度
	parent := make([]int, n)   // 父结点
	heavySon := make([]int, n) // 重儿子
	return &LCAHLD{
		Tree:     tree,
		dfn:      dfn,
		top:      top,
		Depth:    depth,
		Parent:   parent,
		heavySon: heavySon,
	}
}

// 添加无向边 u-v.
func (hld *LCAHLD) AddEdge(u, v int) {
	hld.Tree[u] = append(hld.Tree[u], v)
	hld.Tree[v] = append(hld.Tree[v], u)
}

func (hld *LCAHLD) Build(root int) {
	hld.build(root, -1, 0)
	hld.markTop(root, root)
}

func (hld *LCAHLD) LCA(u, v int) int {
	for {
		if hld.dfn[u] > hld.dfn[v] {
			u, v = v, u
		}
		if hld.top[u] == hld.top[v] {
			return u
		}
		v = hld.Parent[hld.top[v]]
	}
}

func (hld *LCAHLD) Dist(u, v int) int {
	return hld.Depth[u] + hld.Depth[v] - 2*hld.Depth[hld.LCA(u, v)]
}

func (hld *LCAHLD) build(cur, pre, dep int) int {
	subSize, heavySize, heavySon := 1, 0, -1
	for _, next := range hld.Tree[cur] {
		if next != pre {
			nextSize := hld.build(next, cur, dep+1)
			subSize += nextSize
			if nextSize > heavySize {
				heavySize, heavySon = nextSize, next
			}
		}
	}
	hld.Depth[cur] = dep
	hld.heavySon[cur] = heavySon
	hld.Parent[cur] = pre
	return subSize
}

func (hld *LCAHLD) markTop(cur, top int) {
	hld.top[cur] = top
	hld.dfn[cur] = hld.dfnId
	hld.dfnId++
	if hld.heavySon[cur] != -1 {
		hld.markTop(hld.heavySon[cur], top)
		for _, next := range hld.Tree[cur] {
			if next != hld.heavySon[cur] && next != hld.Parent[cur] {
				hld.markTop(next, next)
			}
		}
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
0