Codeforces 101628K

1package _016282 3import (4	"bufio"5	. "fmt"6	"io"7)8 9// github.com/EndlessCheng/codeforces-go10type node struct {11	lr       [2]*node12	priority uint13	key      int14}15 16func (o *node) cmp(b int) int {17	switch {18	case b < o.key:19		return 020	case b > o.key:21		return 122	default:23		return -124	}25}26 27func (o *node) rotate(d int) *node {28	x := o.lr[d^1]29	o.lr[d^1] = x.lr[d]30	x.lr[d] = o31	return x32}33 34type treap struct {35	rd   uint36	root *node37}38 39func (t *treap) fastRand() uint {40	t.rd ^= t.rd << 1341	t.rd ^= t.rd >> 1742	t.rd ^= t.rd << 543	return t.rd44}45 46func (t *treap) _put(o *node, key int) *node {47	if o == nil {48		return &node{priority: t.fastRand(), key: key}49	}50	d := o.cmp(key)51	o.lr[d] = t._put(o.lr[d], key)52	if o.lr[d].priority > o.priority {53		o = o.rotate(d ^ 1)54	}55	return o56}57 58func (t *treap) put(key int) { t.root = t._put(t.root, key) }59 60func (t *treap) _delete(o *node, key int) *node {61	if o == nil {62		return nil63	}64	if d := o.cmp(key); d >= 0 {65		o.lr[d] = t._delete(o.lr[d], key)66	} else {67		if o.lr[1] == nil {68			return o.lr[0]69		}70		if o.lr[0] == nil {71			return o.lr[1]72		}73		d = 074		if o.lr[0].priority > o.lr[1].priority {75			d = 176		}77		o = o.rotate(d)78		o.lr[d] = t._delete(o.lr[d], key)79	}80	return o81}82 83func (t *treap) delete(key int) { t.root = t._delete(t.root, key) }84 85func (t *treap) lowerBound(key int) (lb *node) {86	for o := t.root; o != nil; {87		switch c := o.cmp(key); {88		case c == 0:89			lb = o90			o = o.lr[0]91		case c > 0:92			o = o.lr[1]93		default:94			return o95		}96	}97	return98}99 100type trieNode struct {101	son          [26]*trieNode102	allID, curID *treap103}104 105type trie struct{ root *trieNode }106 107func (trie) ord(c byte) byte { return c - 'a' }108 109func (t *trie) put(s []byte, id int) {110	o := t.root111	for _, b := range s {112		b = t.ord(b)113		if o.son[b] == nil {114			o.son[b] = &trieNode{allID: &treap{rd: 1}, curID: &treap{rd: 1}}115		}116		o = o.son[b]117		o.allID.put(id)118	}119	o.curID.put(id)120}121 122func (t *trie) delete(s []byte, id int) {123	os := []*trieNode{}124	o := t.root125	for _, b := range s {126		o = o.son[t.ord(b)]127		if o == nil {128			return129		}130		os = append(os, o)131	}132	o.curID.delete(id)133	for _, o := range os {134		o.allID.delete(id)135	}136}137 138func (t *trie) hasPrefixOfString(s []byte, l, r int) bool {139	o := t.root140	for _, b := range s {141		o = o.son[t.ord(b)]142		if o == nil {143			return false144		}145		if to := o.curID.lowerBound(l); to != nil && to.key <= r {146			return true147		}148	}149	return false150}151 152func (t *trie) hasStringOfPrefix(p []byte, l, r int) bool {153	o := t.root154	for _, b := range p {155		o = o.son[t.ord(b)]156		if o == nil {157			return false158		}159	}160	to := o.allID.lowerBound(l)161	return to != nil && to.key <= r162}163 164func CF101628K(_r io.Reader, _w io.Writer) {165	in := bufio.NewReader(_r)166	out := bufio.NewWriter(_w)167	defer out.Flush()168 169	t := &trie{&trieNode{}}170	var n, q, op, i, l, r int171	var s []byte172	Fscan(in, &n)173	a := make([][]byte, n)174	for i := range a {175		Fscan(in, &a[i])176		t.put(a[i], i+1)177	}178	for Fscan(in, &q); q > 0; q-- {179		switch Fscan(in, &op); op {180		case 1:181			Fscan(in, &i, &s)182			t.delete(a[i-1], i)183			t.put(s, i)184			a[i-1] = s185		case 2:186			Fscan(in, &l, &r, &s)187			if t.hasPrefixOfString(s, l, r) {188				Fprintln(out, "Y")189			} else {190				Fprintln(out, "N")191			}192		default:193			Fscan(in, &l, &r, &s)194			if t.hasStringOfPrefix(s, l, r) {195				Fprintln(out, "Y")196			} else {197				Fprintln(out, "N")198			}199		}200	}201}202 203//func main() { CF101628K(os.Stdin, os.Stdout) }204