package main import . "fmt" import . "os" import bf "bufio" import "container/heap" func main() { rd:=bf.NewReader(Stdin) wr:=bf.NewWriter(Stdout) defer wr.Flush() var n int Fscan(rd,&n) var s,t string Fscan(rd,&s,&t) bS := []byte(s) bT := []byte(t) pq := make(PQ, 0, n) items := make([]*Item, n) for i := 0; i < n; i++ { item := newItem(i) items[i] = item if bS[i] != bT[i] { heap.Push(&pq, item) } } var q int Fscan(rd,&q) for ; q > 0 ; q-- { var c string var x, y int Fscan(rd,&c,&x,&y) x-- y += '0' switch c { case "S": bS[x] = byte(y) case "T": bT[x] = byte(y) } if bS[x] == bT[x] { if items[x].index >= 0 { heap.Remove(&pq, items[x].index) items[x].index = -1 } } else { if items[x].index < 0 { heap.Push(&pq, items[x]) } } if pq.Len() == 0 { Fprintln(wr, "=") } else { pos := pq.Peek().value switch { case bS[pos] > bT[pos]: Fprintln(wr, ">") case bS[pos] < bT[pos]: Fprintln(wr, "<") } } } } type Item struct { index, value int } func newItem(value int) *Item { return &Item{ index: -1, value: value } } type PQ []*Item func (pq PQ) Peek() *Item { if pq.Len() > 0 { return pq[0] } else { return nil } } func (pq PQ) Len() int { return len(pq) } func (pq PQ) Less(i, j int) bool { return pq[i].value < pq[j].value } func (pq PQ) Swap(i, j int) { pq[i],pq[j] = pq[j],pq[i] pq[i].index = i pq[j].index = j } func (pq *PQ) Push(v any) { item := v.(*Item) item.index = len(*pq) *pq = append(*pq, item) } func (pq *PQ) Pop() any { old := *pq n := len(old) item := old[n-1] item.index = -1 old[n-1] = nil *pq = old[:n-1] return item } /* 考察 書き換えて毎度数値まるごと比較では間に合わない 2つの数値S,Tの各桁のうち数字が異なる桁でもっとも上位の桁を素早く見つけて答えるが必要 SとTで数字が異なる桁をピックアップして 桁の位置をキーとして順序付きセット(平衡二分探索木など)に入れて管理すればよさそう? クエリの書き換えで桁が一致したらセットからキーを削除 クエリの書き換えで桁が異なったらセットにキーを挿入 セットの最小のキーである桁の位置の比較で大小判定はできる セットが空になった場合はSとTは同値にとなる 問題は…Go言語には順序付きセットも順序付きマップも標準ライブラリには無い… まぁ、今回の問題はcontainer/heapでも代用できるとは思う… */