首页 > 试题广场 >

研究red子序列的红

[编程题]研究red子序列的红
  • 热度指数：2881 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
\hspace{15pt}小红有两个长度为 n 的字符串 s,t ，仅包含小写字母，下标从 1 开始。
\hspace{15pt}她每次会进行一个操作，把 s_i 和 t_i 交换，你需要回答每一次交换后字符串 s 中的 \texttt{ 子序列和 t 中 \texttt{ 的子序列之差。
\hspace{15pt}每次询问不独立。

\hspace{15pt}子序列是指在一个序列中，通过删除某些元素（可以是零个或多个元素），而不改变其余元素的相对顺序所得到的序列。

输入描述:
\hspace{15pt}第一行两个整数 n,q \ (1\leqq n,q\leqq 2\times 10^5) 代表字符串长度和操作次数。
\hspace{15pt}第二行一个长度为 n 的字符串 s 。
\hspace{15pt}第三行一个长度为 n 的字符串 t 。
\hspace{15pt}此后 q 行，每行一个整数 x\ (1\leqq x\leqq n)，表示每次交换的位置。


输出描述:
\hspace{15pt}对于每一次询问，在一行上输出一个整数，表示交换后字符串 s 中的 \texttt{ 子序列和 t 中 \texttt{ 的子序列之差。
示例1

输入

5 2
redar
adade
5
4

输出

1
2
算法知识视频讲解
添加回答
Python 3
聪明的小辣鸡在加班头像 聪明的小辣鸡在加班 
n,q=map(int, input().split())
s=list(input())
t=list(input())

def findred(listf):
    res=0
    for i in range(1,len(listf)-1):
        if listf[i]=='e':
            res+=listf[:i].count('r')*listf[i:].count('d')
    return res

for i in range(q):
    c=int(input())-1
    s[c],t[c]=t[c],s[c]
    print(findred(s)-findred(t))
9敏，超时了，家人们谁懂啊，一整个无语住了，我真的会谢（
发表于 2025-03-18 19:27:07 回复(0)
Python 3
牛客388550911号头像 牛客388550911号
垃圾题目, 没说清字符串的交换是不是永续存在的, 而且输出结果在能看到的部分都一致也不给通过. 牛客网能不能走点心??? 
line = input().split(" ")
length = int(line[0])
num = int(line[1])
line1 = input()
line2 = input()


def get_dp(line):
    length = len(line)
    dp_r = [0] * length  # 当前下标前方有多少个r
    dp_d = [0] * length  # 当前下标后方有多少个d
    dp_e = []  # 所有 e 的下标
    for i in range(length - 1):
        if line[i] == "r":
            dp_r[i + 1] = dp_r[i] + 1
        else:
            dp_r[i + 1] = dp_r[i]
    for i in range(length):
        if line[i] == "e":
            dp_e.append(i)
    for i in range(length - 1, 0, -1):
        if line[i] == "d":
            dp_d[i - 1] = dp_d[i] + 1
        else:
            dp_d[i - 1] = dp_d[i]

    return dp_r, dp_e, dp_d


def get_red_num(dp_r, dp_e, dp_d):
    # print(dp_r, dp_e, dp_d)
    res = 0
    for index in dp_e:
        res += dp_r[index] * dp_d[index]
    return res
dp1_r, dp1_e, dp1_d = get_dp(line1)
dp2_r, dp2_e, dp2_d = get_dp(line2)
while 1:
    # dp1_r_temp = list(dp1_r)
    # dp1_e_temp = list(dp1_e)
    # dp1_d_temp = list(dp1_d)
    # dp2_r_temp = list(dp2_r)
    # dp2_e_temp = list(dp2_e)
    # dp2_d_temp = list(dp2_d)
    dp1_r_temp = dp1_r
    dp1_e_temp = dp1_e
    dp1_d_temp = dp1_d
    dp2_r_temp = dp2_r
    dp2_e_temp = dp2_e
    dp2_d_temp = dp2_d
    try:
        chage_index = int(input()) - 1
        cha1 = line1[chage_index]
        cha2 = line2[chage_index]
        if cha1 == "r" and cha2 != "r":
            for i in range(chage_index + 1, length):
                dp1_r_temp[i] -= 1
                dp2_r_temp[i] += 1
        if cha1 == "e" and cha2 != "e":
            dp1_e_temp.remove(chage_index)
            dp2_e_temp.append(chage_index)
        if cha1 == "d" and cha2 != "d":
            for i in range(0, chage_index):
                dp1_d_temp[i] -= 1
                dp2_d_temp[i] += 1
        if cha2 == "r" and cha1 != "r":
            for i in range(chage_index + 1, length):
                dp2_r_temp[i] -= 1
                dp1_r_temp[i] += 1
        if cha2 == "e" and cha1 != "e":
            dp2_e_temp.remove(chage_index)
            dp1_e_temp.append(chage_index)
        if cha2 == "d" and cha1 != "d":
            for i in range(0, chage_index):
                dp2_d_temp[i] -= 1
                dp1_d_temp[i] += 1
        print(get_red_num(dp1_r_temp, dp1_e_temp, dp1_d_temp) - get_red_num(dp2_r_temp, dp2_e_temp, dp2_d_temp))
    except Exception as e:
        # print(e)
        break

发表于 2025-03-06 22:59:51 回复(1)
Python 3
牛客355368210号头像 牛客355368210号
"""输出结果一致但是不过,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)
   
   
发表于 2025-03-04 14:39:25 回复(2)
提交观点

问题信息

线段树
难度：
5条回答 333浏览

热门推荐

相关试题

研究red子序列的红

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号