1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析
会员专享
请先登录,登录后可使用今日免费解锁; 开通会员,或 购买 该题目所属题库(阿里系机考题库) ,可解锁完整内容。
购买题库 开通会员

解题思路

01 串的权值定义为:只由字符 '1' 构成的非空连续子串数量。

如果一段连续的 '1' 的长度为 lenlenlen,那么这段内部能产生的全 '1' 子串数量为:

1+2+⋯+len=len(len+1)21 + 2 + \cdots + len = \frac{len(len+1)}{2} 1+2+⋯+len=2len(len+1)​

P4954.第3题- 小红的01串操作

    1000ms Tried: 0 Accepted: 0 Difficulty: 7 所属公司 : 阿里
    算法与标签>有序集合

题目内容

小红定义一个仅由字符 '000' 和 '111' 组成的字符串(简称 010101 串)的权值为:

  • 仅由 '111' 构成的非空连续子串的数量。

现给定一长为 nnn 的 010101 串,小红会对其进行 qqq 次操作,每次操作选取 010101 串的一位将其反置(若原字符为 '111',反置后为 '000';若原字符为 '000',反置后为 '111')。

你需要计算每次操作后 010101 串的权值是多少。

【名词解释】 连续子串:从原字符串中,连续的选择一段字符(可以全选、可以不选)得到的新字符串。

输入描述

第一行输入两个整数 n,q (1≤n≤2×105,1≤q≤2×105)n,q\ (1 \le n \le 2 \times 10^5, 1 \le q \le 2 \times 10^5)n,q (1≤n≤2×105,1≤q≤2×105)。

第二行输入一个长为 nnn 的 010101 串。

之后 qqq 行,每行输入一个整数 k (1≤k≤n)k\ (1 \le k \le n)k (1≤k≤n) 代表一次操作,将 010101 串的第 kkk 位反置。

输出描述

输出 qqq 行,每行包含一个整数,代表此次操作后 010101 串的权值。

样例1

输入

5 2
10010
2
3

输出

4
10

登录后即可使用 AI 分析。

    模式
    倒计时时长
    :

    最长 10 小时 59 分;应用后按此时长重新开始。

    提示:点击提交记录在左侧题面区域查看详情
    题库
    AI分析设置
    留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
    会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
    升级会员,可将运行与提交冷却时间缩短至 1 秒起

    Status

    • Judging Queue
    • Service Status

    Development

    • Open Source

    Support

    • Help
    • Contact Us

    About

    • About
    • Privacy
    • Terms of Service
    • Copyright Complaint
    1. Language
      1. English
      2. 한국어
      3. 简体中文
      4. 正體中文
    2. Legacy mode
    3. Theme
      1. Light
      2. Dark
    1. 京ICP备2025123107号-1
    2. Worker 2, 36ms
    3. Powered by Hydro v5.0.0-beta.18 Community
    CLOSE


    ScanQRCodePrompt

    请使用微信扫描下方二维码完成注册

    Forgot password or username?