首页 > 试题广场 >

研究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}$ 子序列是指在一个序列中，通过删除某些元素（可以是零个或多个元素），而不改变其余元素的相对顺序所得到的序列。

输入描述:

第一行两个整数  代表字符串长度和操作次数。
第二行一个长度为  的字符串  。
第三行一个长度为  的字符串  。
此后  行，每行一个整数 ，表示每次交换的位置。

输出描述:

对于每一次询问，在一行上输出一个整数，表示交换后字符串  中的  子序列和  中  的子序列之差。

示例1

输入

5 2
redar
adade
5
4

输出

1
2

算法知识视频讲解

菜鸟小乔

哪位大神有python不超时的代码吗？

发表于 2025-07-28 13:22:56 回复(0)

C++

kerst_ker

#include<iostream>

#include<string>

#include<algorithm>

#include<vector>

using namespace std;

//节点

struct Node

{

int l,r;

long long r_cnt,e_cnt,d_cnt;

long long re_cnt,ed_cnt,red_cnt;

Node():l(0),r(0),r_cnt(0),e_cnt(0),d_cnt(0),re_cnt(0),ed_cnt(0),red_cnt(0){}

};

class SegmentTree//递归建树的同时维护信息

{

vector<Node> tree;//动态数组储存树

int n;//树的大小

//递归建树

void build(const string& s,int idx,int l,int r)

{

tree[idx].l = l;

tree[idx].r = r;

if(l==r)//叶子节点

{

if (s[l]=='r') tree[idx].r_cnt=1;

if (s[l]=='e') tree[idx].e_cnt=1;

if (s[l]=='d') tree[idx].d_cnt=1;

return;

}

int m = (l + r) / 2;//中点

build(s, idx * 2, l, m);//左子树

build(s, idx * 2 + 1, m + 1, r);//右子树

push_up(idx);//更新当前节点信息

}

void push_up(int idx)

{

auto &l = tree[idx * 2], &r = tree[idx * 2 + 1], &o = tree[idx];

// o 表示当前节点，l 表示左子节点，r 表示右子节点

// 当前区间的 'r' 数量 = 左区间的 'r' 数量 + 右区间的 'r' 数量

o.r_cnt = l.r_cnt + r.r_cnt;

// 当前区间的 'e' 数量 = 左区间的 'e' 数量 + 右区间的 'e' 数量

o.e_cnt = l.e_cnt + r.e_cnt;

// 当前区间的 'd' 数量 = 左区间的 'd' 数量 + 右区间的 'd' 数量

o.d_cnt = l.d_cnt + r.d_cnt;

// "re" 子序列数量 = 左"re" + 右"re" + 左'r' * 右'e'

o.re_cnt = l.re_cnt + r.re_cnt + l.r_cnt * r.e_cnt;

// "ed" 子序列数量 = 左"ed" + 右"ed" + 左'e' * 右'd'

o.ed_cnt = l.ed_cnt + r.ed_cnt + l.e_cnt * r.d_cnt;

// "red" 子序列数量 = 左"red" + 右"red" + 左'r' * 右"ed" + 左"re" * 右'd'

o.red_cnt = l.red_cnt + r.red_cnt + l.r_cnt * r.ed_cnt + l.re_cnt * r.d_cnt;

}

//递归合并树

void update(int idx, int pos, char c) {

int l = tree[idx].l, r = tree[idx].r;

if(l == r) {

tree[idx] = Node();

tree[idx].l = l; tree[idx].r = r;

if(c == 'r') tree[idx].r_cnt = 1;

if(c == 'e') tree[idx].e_cnt = 1;

if(c == 'd') tree[idx].d_cnt = 1;

return;

}

int m = (l + r) / 2;

if(pos <= m) update(idx*2, pos, c);

else update(idx*2+1, pos, c);

push_up(idx);

}

//接口

public:

SegmentTree(const string& s) {

n = s.size();

tree.resize(n * 4);

build(s, 1, 0, n-1);

}

void update(int pos, char c) {

update(1, pos, c);

}

long long query_red() {

return tree[1].red_cnt;

}

};

int main(){

int n,q;

cin>>n>>q;

string s,t;

cin>>s>>t;

SegmentTree st_s(s), st_t(t);

while (q--)

{

int x;

cin>>x;

x--;

char cs=s[x],ct=t[x];

st_s.update(x,ct);

st_t.update(x,cs);

swap(s[x],t[x]);

cout<<st_s.query_red()-st_t.query_red()<<endl;

}

return 0;

}

发表于 2025-09-07 14:51:08 回复(1)

潜在数组或指针越界

第一反应动态规划，然后超时了

发表于 2025-12-07 22:18:07 回复(0)

想要offer的啤酒肚很好奇

一直超时，时间复杂度怎么能更简单一些

from bisect import *
def func(lst):
    
    if "r" not in lst&nbs***bsp;"e" not in lst&nbs***bsp;"d" not in lst:
        return 0
    d1 = {"r":[],"e":[],"d":[]}
    for i,v in enumerate(lst):
        if v in d1:
            d1[v].append(i) 
    res = 0
    for r in d1["r"]:
        m = bisect(d1["e"],r)
        if len(d1["e"])-m:
            for e in d1["e"][m:]:
                d =  len(d1["d"]) - bisect(d1["d"],e)
                res += d
    return res
n,q = map(int,input().split())
s = list(input())
t = list(input())

for _ in range(q):
    x = int(input()) - 1
    s[x],t[x] = t[x],s[x]
    print(func(s) - func(t))

发表于 2025-07-15 18:13:37 回复(0)

Python3

请叫我牛柳

燃尽了

import sys

def cal_red(word: str):
    nr = 0
    nre = 0
    nred = 0
    for l in word:
        if l == 'r':
            nr += 1
        elif l == 'e':
            nre += nr
        elif l == 'd':
            nred += nre
    return nred


n, q = input().split(' ')
n, q = int(n), int(q)

s = input()
t = input()
n_s, n_t = 0, 0
for _ in range(q):
    x = int(input())

    tmpt, tmps = t[x-1], s[x-1]
    s = s[:x-1] + tmpt + s[x:]
    t = t[:x-1] + tmps + t[x:]

    if tmpt in 'red'&nbs***bsp;tmps in 'red'&nbs***bsp;_ == 0:
        n_s = cal_red(s)
        n_t = cal_red(t)

    print(n_s - n_t)

发表于 2025-07-03 22:21:27 回复(1)

super_newcoder

这是什么题？看都看不懂什么意思是

发表于 2025-05-18 20:40:59 回复(1)

Python3

不会哈气学哈气

自认为时间复杂度已经最优了，但是还是超时。不知道有没有什么取巧的办法

def sub_count(s, sub):

n = len(sub)
dp = [0] * (n+1)
dp[0] = 1
for e in s:
for j in range(n, 0, -1):
if e == sub[j-1]:
dp[j] += dp[j-1]

return dp[n]

n, q = map(int, input().split())
s, t = list(input()), list(input())
for _ in range(q):
pos = int(input())-1
s[pos], t[pos] = t[pos], s[pos]

print(sub_count(s,'red')-sub_count(t,'red'))

发表于 2025-05-17 13:13:58 回复(0)

Python3

zzlh

感觉算法Segment Tree实现的没问题，但是局限于 python 语言太慢了所以这道题没法通过了。

import sys
import re
n,q=map(int,input().split())
s=list(input())
t=list(input())

class SegmentTree:
    def __init__(self,s):
        #
        self.n=len(s)
        N=1
        while N<self.n:
            N<<=1
        #叶子节点的位置
        self.N=N
        size=2*N
        self.r=[0]*size
        self.e=[0]*size
        self.d=[0]*size
        self.re=[0]*size
        self.ed=[0]*size
        self.red=[0]*size
        #叶子节点赋值
        for i in range(self.n):
            if s[i]=='r':
                self.r[N+i]=1
            elif s[i]=='e':
                self.e[N+i]=1
            elif s[i]=='d':
                self.d[N+i]=1
        for i in range(N-1,0,-1):
            self.merge(i)
    #把Id节点的左右节点合并到自身
    def merge(self,id):
        l=id*2
        r=id*2+1
        self.r[id]=self.r[l]+self.r[r]
        self.e[id]=self.e[l]+self.e[r]
        self.d[id]=self.d[l]+self.d[r]
        self.re[id]=self.re[l]+self.re[r]+self.r[l]*self.e[r]
        self.ed[id]=self.ed[l]+self.ed[r]+self.e[l]*self.d[r]
        self.red[id]=self.red[l]+self.red[r]+self.r[l]*self.ed[r]+self.re[l]*self.d[r]
    #修改节点
    def update(self,pos,ch):
        N=self.N
        self.r[pos+N]=0
        self.e[pos+N]=0
        self.d[pos+N]=0
        if ch=='r':
            self.r[pos+N]=1
        elif ch=='e':
            self.e[pos+N]=1
        elif ch=='d':
            self.d[pos+N]=1
        x=(pos+N)//2
        while x>=1:
            self.merge(x)
            x//=2
segtree1=SegmentTree(s)
segtree2=SegmentTree(t)       
for _ in range(q):
    pos=int(input())-1
    t[pos],s[pos]=s[pos],t[pos]
    segtree1.update(pos,s[pos])
    segtree2.update(pos,t[pos])
    print(segtree1.red[1]-segtree2.red[1])

发表于 2025-05-16 22:34:38 回复(0)

emdnauoy

ls = list(map(int,input().split()))

s_num = ls[0]

t = ls[1]

s1 = input()

s2 = input()

def switch_str(s1, s2, k):

k1 = s1[k-1]

k2 = s2[k-1]

if k == len(s1):

s_out_1 = s1[:k-1] + k2

s_out_2 = s2[:k-1] + k1

else:

s_out_1 = s1[:k-1] + k2 + s1[k:]

s_out_2 = s2[:k-1] + k1 + s2[k:]

return s_out_1,s_out_2

def get_red(s):

r_c = 0

re_c = 0

red_c = 0

for char in s:

if char == 'r':

r_c += 1

elif char == 'e':

re_c += r_c

elif char == 'd':

red_c += re_c

return red_c

for i in range(t):

num = int(input())

s_switch1, s_switch2 = switch_str(s1,s2,num)

n1 = get_red(s_switch1)

n2 = get_red(s_switch2)

print( n1-n2 if n1>=n2 else n2-n1)

发表于 2025-04-19 10:23:51 回复(0)

珂樂芙

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 20e5;

class Redstring {
  private:
    struct Node {
        ll l, r;
        ll rcnt, ecnt, dcnt, recnt, edcnt, redcnt;
    };
    Node tr[N];

    void pushup(ll u) {
        tr[u].rcnt = tr[u << 1].rcnt + tr[u << 1 | 1].rcnt;
        tr[u].ecnt = tr[u << 1].ecnt + tr[u << 1 | 1].ecnt;
        tr[u].dcnt = tr[u << 1].dcnt + tr[u << 1 | 1].dcnt;
        tr[u].recnt = tr[u << 1].recnt + tr[u << 1 | 1].recnt + tr[u << 1].rcnt * tr[u
                      << 1 | 1].ecnt;
        tr[u].edcnt = tr[u << 1].edcnt + tr[u << 1 | 1].edcnt + tr[u << 1].ecnt * tr[u
                      << 1 | 1].dcnt;
        tr[u].redcnt = tr[u << 1].redcnt + tr[u << 1 | 1].redcnt + tr[u << 1].rcnt *
                       tr[u << 1 | 1].edcnt + tr[u << 1].recnt * tr[u << 1 | 1].dcnt;
    }
  public:
    void build(ll u, ll l, ll r, const string& s) {
        tr[u].l = l;
        tr[u].r = r;
        if (l == r) {
            tr[u].rcnt = tr[u].ecnt = tr[u].dcnt = 0;
            tr[u].recnt = tr[u].edcnt = tr[u].redcnt = 0;
            if (s[l] == 'r') tr[u].rcnt = 1;
            else if (s[l] == 'e') tr[u].ecnt = 1;
            else if (s[l] == 'd') tr[u].dcnt = 1;
        } else {
            ll mid = (l + r) >> 1;
            build(u << 1, l, mid, s);
            build(u << 1 | 1, mid + 1, r, s);
            pushup(u);
        }
    }

    void modify(ll u, ll x, char v) {
        if (tr[u].l == tr[u].r) {
            tr[u].rcnt = tr[u].ecnt = tr[u].dcnt = 0;
            tr[u].recnt = tr[u].edcnt = tr[u].redcnt = 0;
            if (v == 'r') tr[u].rcnt = 1;
            else if (v == 'e') tr[u].ecnt = 1;
            else if (v == 'd') tr[u].dcnt = 1;
        } else {
            ll mid = (tr[u].l + tr[u].r) >> 1;
            if (x <= mid) modify(u << 1, x, v);
            else modify(u << 1 | 1, x, v);
            pushup(u);
        }
    }

    ll get_redcnt(int u) {
        return tr[u].redcnt;
    }
};

int main() {
    ll n, q, pos;
    string s, t;
    cin >> n >> q;
    cin >> s >> t;
    s = " " + s; // 1-based
    t = " " + t; // 1-based

    Redstring s1, t1;
    s1.build(1, 1, n, s);
    t1.build(1, 1, n, t);

    while (q--) {
        cin >> pos;
        swap(s[pos], t[pos]);
        s1.modify(1, pos, s[pos]);
        t1.modify(1, pos, t[pos]);
        cout << s1.get_redcnt(1) - t1.get_redcnt(1) << endl;
    }

    return 0;
}

发表于 2025-03-31 17:16:28 回复(0)

Java

dhu_wch

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        char[]s1 = in.next().toCharArray();
        char[]s2 = in.next().toCharArray();
        SegTree t1=SegTree.build(s1,0,n-1);
        SegTree t2=SegTree.build(s2,0,n-1);
        for (int i = 0; i < q; i++) {
            int x = in.nextInt();
            char c=s1[x-1];
            s1[x-1]=s2[x-1];
            s2[x-1]=c;
            t1.update(x-1,s1[x-1]);
            t2.update(x-1,s2[x-1]);
            System.out.println(t1.redcnt-t2.redcnt);
        }
    }
}
class SegTree{
    int l;
    int r;
    int rcnt;//r
    int ecnt;//e
    int dcnt;//d
    long recnt;//re
    long edcnt;//ed
    long redcnt;//red
    SegTree left;
    SegTree right;
    public void update(int k,char c){
        if(k<l||k>r)
            return;
        if(l==r&&l==k){
            rcnt=c=='r'?1:0;
            ecnt=c=='e'?1:0;
            dcnt=c=='d'?1:0;
            return;
        }
        int mid=(l+r)/2;
        if(k<=mid){
            left.update(k,c);
        }else{
            right.update(k,c);
        }
        mergeSub();
    }
    public void mergeSub(){
        rcnt=left.rcnt+right.rcnt;
        ecnt=left.ecnt+right.ecnt;
        dcnt=left.dcnt+right.dcnt;
        recnt=left.recnt+right.recnt+left.rcnt*right.ecnt;
        edcnt=left.edcnt+right.edcnt+left.ecnt*right.dcnt;
        redcnt=left.redcnt+right.redcnt+left.rcnt*right.edcnt+left.recnt*right.dcnt;
    }

    public static SegTree build(char[]s,int l,int r)
    {
        SegTree t=new SegTree();
        t.l=l;
        t.r=r;
        if(l==r)
        {
            t.rcnt=s[l]=='r'?1:0;
            t.ecnt=s[l]=='e'?1:0;
            t.dcnt=s[l]=='d'?1:0;
            t.recnt=t.edcnt=t.redcnt=0;
            return t;
        }
        int mid=(l+r)/2;
        t.left=build(s,l,mid);
        t.right=build(s,mid+1,r);
        t.mergeSub();
        return t;
    }


}

看了一眼，没有人用Java写写线段树，我在这里写一个，希望对大家有帮助

本题注意点：

1）下次交换是再前一个交换的基础上交换的

2）结果可能大于int，要用long

发表于 2025-03-26 21:14:04 回复(0)

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)

软弱的我

m,n=list(map(int,input().split()))
s1=input()
s2=input()
l=[]
for i in range(n):
    l.append(int(input()))
def countRed(s):
    if not ("r" in s and "e" in s and "d" in s):
        return 0
    r,e,d=[],[],[]
    sum=0
    for i in range(len(s)):
        if s[i]=="r":
            r.append(i)
            continue
        if s[i]=="e":
            e.append(i)
            continue
        if s[i]=="d":
            d.append(i)
    tmpe=0
    for i in range(len(r)):
        tmpd=0
        for j in range(tmpe,len(e)):
            if r[i]>e[j]:
                tmpe=j
                continue
            for k in range(tmpd,len(d)):
                if e[j]<d[k]:
                    sum+=len(d)-k
                    tmpd=k
                    break
    return sum
for i in l:
    tmp1,tmp2=list(s1),list(s2)
    tmp1[i-1],tmp2[i-1]=tmp2[i-1],tmp1[i-1]
    tmps1="".join(tmp1)
    tmps2="".join(tmp2)
    print(countRed(tmps1)-countRed(tmps2))

运行超时，结果也不对哈哈

发表于 2025-03-15 21:35:09 回复(0)

Python3

吃不饱的卷王很害怕一个人

#输出一样为啥也过不了，奇奇怪怪的

import sys

list_change = list()

formore = list(input().split())

str_length = int(formore[0])

trans_num = int(formore[1])

list_str1 = list()

list_str2 = list()

str1 = str(input())

str2 = str(input())

for i in range(len(str1)):

list_str1.append(str1[i])

list_str2.append(str2[i])

list_change = [0 for _ in range(trans_num)]

for i in range(trans_num):

list_change[i] = int(input())

def find_count(num: list):

e_i = [[0,0] for _ in range(len(num))]

num_r = 0

num_d = 0

count = 0

for i in range(len(num)):

if num[i] == 'r':

num_r += 1

elif num[i] == 'e':

e_i[i][0] = num_r

for i in range(len(num)-1,-1,-1):

if num[i] == 'd':

num_d += 1

elif num[i] == 'e':

e_i[i][1] = num_d

for i in e_i:

count += int(i[0]) * int(i[1])

return count

result = list()

for i in range(trans_num):

num = list_change[i]

str_copy1 = list_str1

str_copy2 = list_str2

str_copy1[num-1] = str2[num-1]

str_copy2[num-1] = str1[num-1]

count1 = find_count(str_copy1)

count2 = find_count(str_copy2)

res = count1-count2

result.append(res)

for i in range(len(result)):

print(result[i])

发表于 2025-03-11 12:51:49 回复(0)

Python 3

牛客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号

"""输出结果一致但是不过,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)

提交观点

问题信息

线段树

难度：

16条回答 94收藏 335浏览

研究red子序列的红

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题