小红有两个长度为 的字符串 ，仅包含小写字母，下标从 开始。 她每次会进行一个操作，把 和 交换，你需要回答每一次交换后字符串 中的 子序列和 中 的子序列之差。 每次询问不独立。 子序列是指在一个序列中，通过删除某些元素（可以是零个或多个元素），而不改变其余元素的相对顺序所得到的序列。
区块链毕设网qklbishe.com为您提供问题的解答
小红有两个长度为
的字符串
，仅包含小写字母，下标从
开始。
她每次会进行一个操作，把
和
交换，你需要回答每一次交换后字符串
中的
子序列和
中
的子序列之差。
每次询问不独立。
子序列是指在一个序列中，通过删除某些元素（可以是零个或多个元素），而不改变其余元素的相对顺序所得到的序列。
输出结果和C++版一致， 但是提交不通过，也怀疑是系统问题
class Node(object): # 线段树的结点类 def __init__(self): self.ln = -1 self.rn = -1 # 左子节点和右子节点，值为字符的索引 self.r = 0 # 分别记录 r, e, d, re, ed, red 的个数 self.e = 0 self.d = 0 self.re = 0 self.ed = 0 self.red = 0 class SegTree(object): # 线段树类 def __init__(self, data): self.n = len(data) # 初始化线段树，大小为4*n（因为最坏情况下是满二叉树） self.tree = [Node() for _ in range(self.n * 4)] self.build(data, 1, 0, self.n - 1) # 树节点从1开始 def build(self, data, node, start, end): # 构建线段树 # data 表示字符串， node 表示节点下标，start 和 end 表示 字符的索引 self.tree[node].ln = start self.tree[node].rn = end if start == end: # 如果当前节点是叶子节点 self.tree[node].r = int(data[start] == 'r') self.tree[node].e = int(data[start] == 'e') self.tree[node].d = int(data[start] == 'd') return mid = (start + end) // 2 self.build(data, node * 2, start, mid) # 左子树 self.build(data, node * 2 + 1, mid + 1, end) # 右子树 self.push_up(node) def push_up(self, node): # 计算该节点的r e d re ed red 个数 left = self.tree[node * 2] # 左节点 right = self.tree[node * 2 + 1] # 右节点 self.tree[node].r = left.r + right.r self.tree[node].e = left.e + right.e self.tree[node].d = left.d + right.d self.tree[node].re = left.re + right.re + left.r * right.e self.tree[node].ed = left.ed + right.ed + left.e * right.d self.tree[node].red = left.red + right.red + left.re * right.d + left.r * right.ed def update(self, node, pos, val): # 单点更新，pos表示更新的索引，val表示更新的值 if self.tree[node].ln == self.tree[node].rn and self.tree[node].ln == pos: # 递归到叶子节点 self.tree[node].r = int(val == 'r') self.tree[node].e = int(val == 'e') self.tree[node].d = int(val == 'd') return mid = (self.tree[node].ln + self.tree[node].rn) // 2 if pos <= mid: self.update(node * 2, pos, val) else: self.update(node * 2 + 1, pos, val) self.push_up(node) n, q = map(int, input().split()) s = input() t = input() seg_s = SegTree(s) seg_t = SegTree(t) opt = [] for _ in range(q): x = int(input()) - 1 opt.append(x) for x in opt: seg_s.update(1, x, t[x]) seg_t.update(1, x, s[x]) s, t = s[:x] + t[x] + s[x + 1:], t[:x] + s[x] + t[x + 1:] print(seg_s.tree[1].red - seg_t.tree[1].red)
11:07
"""输出结果一致但是不过,C++版本可以，怀疑是系统问题"""
def lp(x)->int:
return x<<1
def rp(x)->int:
return (x<<1)|1
def mid(x:int,y:int)->int:
return (x+y)>>1
class Seg:
def __init__(self,l=-1,r=-2):
self.l = –1
self.r = –2
self.rcnt=self.ecnt=self.dcnt=self.recnt=self.edcnt=self.redcnt=0
class STree:
def __init__(self,a):
"""初始化区间数组"""
self.n = n = len(a)
self.s = [ Seg() for _ in range(n<<2)]
self.build("Z"+a,1,n,1)
def build(self,a,l,r,p):
"""构建线段树"""
sg = self.s[p]
sg.l,sg.r=l,r
if l == r:
self.sg_set(sg,a[l])
return
m = mid(l,r)
self.build(a,l,m,lp(p))
self.build(a,m+1,r,rp(p))
self.adjust(p)
def update(self,pos,ch,p):
"""单点修改"""
sg = self.s[p]
if sg.l==sg.r==pos:
self.sg_set(sg,ch)
return
m = mid(sg.l,sg.r)
if pos <= m:
self.update(pos,ch,lp(p))
else:
self.update(pos,ch,rp(p))
self.adjust(p)
def sg_set(self,sg:Seg,v:str):
"""单点设置"""
sg.rcnt=sg.ecnt=sg.dcnt = 0
if v == "r":
sg.rcnt = 1
elif v == "e":
sg.ecnt = 1
elif v =="d":
sg.dcnt = 1
def adjust(self,p):
"""自适应调整"""
sg,ln,rn = self.s[p],self.s[lp(p)],self.s[rp(p)]
sg.rcnt = ln.rcnt + rn.rcnt
sg.ecnt = ln.ecnt + rn.ecnt
sg.dcnt = ln.dcnt + rn.dcnt
sg.recnt = ln.recnt + rn.recnt + ln.rcnt*rn.ecnt
sg.edcnt = ln.edcnt+rn.edcnt+ln.ecnt*rn.dcnt
sg.redcnt = ln.redcnt+rn.redcnt+ln.recnt*rn.dcnt+ln.rcnt*rn.edcnt
nnn,q = map(int,input().split())
s,t = input(),input()
seqs = []
for _ in range(q):
seqs.append(int(input()))
tree_s = STree(s)
tree_t = STree(t)
for seq in seqs:
k = seq-1
if k<len(s) and k<len(t):
cl,cr = s[k],t[k]
tree_s.update(k+1,cr,1)
tree_t.update(k+1,cl,1)
print(tree_s.s[1].redcnt – tree_t.s[1].redcnt)
39:25
以上就是关于问题小红有两个长度为 的字符串 ，仅包含小写字母，下标从 开始。
她每次会进行一个操作，把 和 交换，你需要回答每一次交换后字符串 中的 子序列和 中 的子序列之差。
每次询问不独立。
子序列是指在一个序列中，通过删除某些元素（可以是零个或多个元素），而不改变其余元素的相对顺序所得到的序列。的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}