学习文化课把
by liaoyichen @ 2023-10-28 11:23:38
@[liaoyichen](/user/486675) /fn/fn/fn
by lzyqwq @ 2023-10-28 11:24:33
@[蒟蒻·廖子阳](/user/539211) 玩原神
by liaoyichen @ 2023-10-28 11:25:47
@[liaoyichen](/user/486675) 别你妈魔怔了 lyc 赶紧帮我调
by lzyqwq @ 2023-10-28 11:26:37
我草，数组开小了
by lzyqwq @ 2023-10-28 11:32:26
#下次注释写好一点！
```python
import random
# 常量
N = 600000
M = 1919810
B1 = 780
B2 = 300
S = 50001
eps = 1e-9
# 全局变量
n = 0
a = [0] * N
ord = 26
col = [0] * N
hd = [0] * S
len = [0] * S
s = ""
q = 0
# 初始化随机数生成器
rnd = random.Random()
# 生成一个指定范围内的随机数
def range(l, r):
return rnd.randint(l, r)
# 后缀数组类
class SuffixArray:
def __init__(self):
self.rk = [0] * N
self.sa = [0] * N
self.st = [[0] * N for _ in range(20)]
self.cnt = [0] * N
self.ht = [0] * N
self.lg = [0] * N
self.p = [((0, 0), 0) for _ in range(N)]
# 初始化
def init(self):
for i in range(1, n + 1):
self.cnt[a[i]] += 1
for i in range(1, ord + 1):
self.cnt[i] += self.cnt[i - 1]
for i in range(1, n + 1):
self.rk[i] = self.cnt[a[i] - 1] + 1
# 排序
def Sort(self):
l = 1
id = 0
while l <= n:
for i in range(1, n + 1):
self.p[i] = ((self.rk[i], self.rk[i + l]) if i + l <= n else (self.rk[i], 0), i)
self.p.sort(key=lambda x: x[0])
id = 0
for i in range(1, n + 1):
if i == 1 or self.p[i][0] != self.p[i - 1][0]:
id += 1
self.rk[self.p[i][1]] = id
if id == n:
break
l <<= 1
for i in range(1, n + 1):
self.sa[self.rk[i]] = i
# 计算高度数组
def height(self):
k = 0
for i in range(1, n + 1):
if self.rk[i] == 1:
self.ht[1] = k = 0
continue
if k:
k -= 1
j = self.sa[self.rk[i] - 1]
while i + k <= n and j + k <= n and a[i + k] == a[j + k]:
k += 1
self.ht[self.rk[i]] = k
# 构建 Sparse Table
def ST(self):
for i in range(1, n + 1):
self.st[0][i] = self.ht[i]
self.lg[i] = i.bit_length()
for i in range(1, self.lg[n] + 1):
for j in range(1, n - (1 << i) + 2):
self.st[i][j] = min(self.st[i - 1][j], self.st[i - 1][j + (1 << (i - 1)))
# 计算最长公共前缀
def LCP(self, l, r):
if l == r:
return n - self.sa[l] + 1
if l > r:
l, r = r, l
l += 1
k = self.lg[r - l + 1]
return min(self.st[k][l], self.st[k][r - (1 << k) + 1])
# 执行后缀数组构建
def work(self):
self.init()
self.Sort()
self.height()
self.ST()
# 调试输出
def debug(self):
print("rk:", self.rk[1:n + 1])
print("sa:", self.sa[1:n + 1)
# 查询类
class Query:
def __init__(self, l, r, ql, qr, v, id):
self.l = l
self.r = r
self.ql = ql
self.qr = qr
self.v = v
self.id = id
# 节点类
class Node:
def __init__(self, id, cnt):
self.id = id
self.cnt = cnt
def __lt__(self, other):
return (self.cnt, self.id) < (other.cnt, other.id)
# 向列表中添加元素并更新计数
def add(lst, x, num, cnt, mx):
num[x] -= 1
cnt[x] += 1
num[x][cnt[x]] += 1
mx[x] = max(mx[x], cnt[x])
# 从列表中删除元素并更新计数
def delete(lst, x, num, cnt, mx):
if cnt[x] == mx[x] and num[x][cnt[x]] == 1:
mx[x] -= 1
num[x] -= 1
cnt[x] -= 1
num[x][cnt[x]] += 1
# 查询最大计数元素
def query(l, r):
if l == r:
return Node(1919810, 0)
if l > r:
l, r = r, l
occ = 0
for i in range(l, r):
cmax(occ, cnt[i])
for i in range(l, br[bel[l]]):
cmax(occ, cnt[i])
for i in range(bl[bel[r]], r):
cmax(occ, cnt[i])
for i in range(l, br[bel[l]]):
if cnt[i] == occ:
return Node(i, cnt[i])
for i in range(bel[l] + 1, bel[r]):
if mx[i] == occ:
for j in range(bl[i], br[i]):
if cnt[j] == occ:
return Node(j, cnt[j])
for i in range(bl[bel[r]], r):
if cnt[i] == occ:
return Node(i, cnt[i])
return Node(114514, 1919810)
# 主函数
def work(testcases):
qingkong()
s = input() # 输入字符串
m = int(input()) # 输入 m
for i in range(len(s)):
a.append(ord(s[i]) - ord('a') + 1)
for i in range(1, m + 1):
s = input() # 输入字符串
ord += 1
hd.append(n + 1)
len.append(len(s))
for j in range(len(s)):
a.append(ord(s[j]) - ord('a') + 1)
if i % B2 == 1:
tot += 1
bel.append(tot)
for i in range(1, tot + 1):
bl.append(br[i - 1] + 1)
br[i] = min(i * B2, m)
SA = SuffixArray()
SA.work()
q = int(input()) # 输入 q
Q = []
for i in range(1, q + 1):
ql, qr, ll, rr = map(int, input().split())
l = 1
r = SA.rk[ll]
Q.append(Query(0, 0, ql, qr, 0, i))
while l <= r:
mid = (l + r) // 2
if SA.LCP(mid, SA.rk[ll]) >= rr - ll + 1:
Q[i - 1].l = mid
r = mid - 1
else:
l = mid + 1
l = SA.rk[ll]
r = n
while l <= r:
mid = (l + r) // 2
if SA.LCP(mid, SA.rk[ll]) >= rr - ll + 1:
Q[i - 1].r = mid
l = mid + 1
else:
r = mid - 1
Q[i - 1].v = Q[i - 1].l // B1
Q.sort(key=lambda x: (x.v, x.r) if x.v & 1 else (-x.r, x.r))
for i in range(1, tot + 1):
num.append([0] * S)
mx.append(0)
for j in range(bl[i], br[i] + 1):
add(j)
for i in range(1, q + 1):
while l > Q[i - 1].l:
add(col[l])
l -= 1
while r < Q[i - 1].r:
add(col[r])
r += 1
while l < Q[i - 1].l:
delete(col[l])
l += 1
while r > Q[i - 1].r:
delete(col[r])
r -= 1
ans.append(query(Q[i - 1].ql, Q[i - 1].qr))
for i in range(1, q + 1):
print(ans[i - 1].id, ans[i - 1].cnt)
return 0
if __name__ == "__main__":
testcases = 1
# testcases = int(input())
for lzyqwq in range(1, testcases + 1):
work(lzyqwq)
by cloudflared @ 2023-10-28 11:53:15
你玩原神吗
by Deuteron @ 2023-10-28 11:57:59
@[cloudflared](/user/1175966) 下次回帖之前过过脑子看看 lz 的需求是什么 /qd /qd /qd
by lzyqwq @ 2023-10-28 12:01:46
@[小可爱萌萌哒](/user/397982) 呜呜呜 别骂了
by lzyqwq @ 2023-10-28 12:02:29
@[蒟蒻·廖子阳](/user/539211) rm -rf /*毁灭吧
by cloudflared @ 2023-10-28 13:49:18