（线段树字符串的处理）codeforces570C

作者：pingyuki | 来源：互联网 | 2024-10-10 16:13

链接：http:acm.hust.edu.cnvjudgecontestview.action?cid87813#problemJDescriptionDanielh

链接&＃xff1a;

http://acm.hust.edu.cn/vjudge/contest/view.action?cid&＃61;87813#problem/J

Description

Daniel has a string s, consisting of lowercase English letters and period signs (characters &＃39;.&＃39;). Let&＃39;s define the operation of replacement as the following sequence of steps: find a substring ".." (two consecutive periods) in string s, of all occurrences of the substring let&＃39;s choose the first one, and replace this substring with string ".". In other words, during the replacement operation, the first two consecutive periods are replaced by one. If string s contains no two consecutive periods, then nothing happens.

Let&＃39;s define f(s) as the minimum number of operations of replacement to perform, so that the string does not have any two consecutive periods left.

You need to process m queries, the i-th results in that the character at position x_i (1 ≤ x_i ≤ n) of string s is assigned value c_i. After each operation you have to calculate and output the value of f(s).

Help Daniel to process all queries.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 300 000) the length of the string and the number of queries.

The second line contains string s, consisting of n lowercase English letters and period signs.

The following m lines contain the descriptions of queries. The i-th line contains integer x_i and c_i (1 ≤ x_i ≤ n, c_i — a lowercas English letter or a period sign), describing the query of assigning symbol c_i to position x_i.

Output

Print m numbers, one per line, the i-th of these numbers must be equal to the value of f(s) after performing the i-th assignment.

Sample Input

Input

10 3
.b..bz....
1 h
3 c
9 f

Output

4
3
1

Input

4 4
.cc.
2 .
3 .
2 a
1 a

Output

1
3
1
1

Hint

Note to the first sample test (replaced periods are enclosed in square brackets).

The original string is ".b..bz....".

after the first query f(hb..bz....) &＃61; 4 ("hb[..]bz...." → "hb.bz[..].." → "hb.bz[..]." → "hb.bz[..]" → "hb.bz.")
after the second query f(hbс.bz....) &＃61; 3 ("hbс.bz[..].." → "hbс.bz[..]." → "hbс.bz[..]" → "hbс.bz.")
after the third query f(hbс.bz..f.) &＃61; 1 ("hbс.bz[..]f." → "hbс.bz.f.")

Note to the second sample test.

The original string is ".cc.".

after the first query: f(..c.) &＃61; 1 ("[..]c." → ".c.")
after the second query: f(....) &＃61; 3 ("[..].." → "[..]." → "[..]" → ".")
after the third query: f(.a..) &＃61; 1 (".a[..]" → ".a.")
after the fourth query: f(aa..) &＃61; 1 ("aa[..]" → "aa.")

找到了规律很水的AC了&＃xff0c;但看了题解后知道原来这是个线段树&＃xff0c; 两个代码都粘一下

水的代码&＃xff1a;

#include
#include<string.h>#define N 301100char s[N];int main()
{int n, m, sum, z;while(scanf("%d%d", &n, &m)!&＃61;EOF){char ch;int k, i;scanf("%s", s);sum&＃61;0;for(i&＃61;0; i){z &＃61; 0;while(s[i]&＃61;&＃61;&＃39;.&＃39; && i<n){z&＃43;&＃43;;i&＃43;&＃43;;}if(z)sum&＃43;&＃61;z-1;}for(i&＃61;1; i<&＃61;m; i&＃43;&＃43;){scanf("%d %c", &k, &ch);if((s[k-1]!&＃61;&＃39;.&＃39;&&ch!&＃61;&＃39;.&＃39;) || (s[k-1]&＃61;&＃61;&＃39;.&＃39;&&ch&＃61;&＃61;&＃39;.&＃39;) ){printf("%d\n", sum);continue;}if(ch&＃61;&＃61;&＃39;.&＃39; && s[k-1]!&＃61;&＃39;.&＃39;){if(s[k]!&＃61;&＃39;.&＃39; && s[k-2]!&＃61;&＃39;.&＃39;)sum &＃61; sum;else if(s[k]&＃61;&＃61;&＃39;.&＃39; && s[k-2]&＃61;&＃61;&＃39;.&＃39;)sum &＃43;&＃61; 2;else if(s[k]&＃61;&＃61;&＃39;.&＃39; || s[k-2]&＃61;&＃61;&＃39;.&＃39;)sum &＃43;&＃61; 1;}if(ch!&＃61;&＃39;.&＃39; && s[k-1]&＃61;&＃61;&＃39;.&＃39;){if(s[k]&＃61;&＃61;&＃39;.&＃39; && s[k-2]&＃61;&＃61;&＃39;.&＃39;)sum &＃61; sum-2;else if(s[k]!&＃61;&＃39;.&＃39; && s[k-2]!&＃61;&＃39;.&＃39;)sum &＃61; sum;else if(s[k]!&＃61;&＃39;.&＃39; || s[k-2]!&＃61;&＃39;.&＃39;)sum &＃61; sum-1;}s[k-1] &＃61; ch;printf("%d\n", sum);}}return 0;
}

线段树&＃xff1a;

/*************************************************************************> File Name: C.cpp> Author: ALex> Mail: zchao1995&＃64;gmail.com > Created Time: 2015年08月14日星期五 01时09分43秒************************************************************************/#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include <set>
#include
#include
#include
#include <string>
#include
#include
#include
#include
#include using namespace std;const double pi &＃61; acos(-1.0);
const int inf &＃61; 0x3f3f3f3f;
const double eps &＃61; 1e-15;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> PLL;
const LL INF &＃61; (1LL <<60);const int N &＃61; 300010;
struct SegTree {int l, r;int lenl, lenr;int len;int cnt;
}tree[N <<2];
char str[N];void pushup(int p){tree[p].lenl &＃61; tree[p <<1].lenl;if (tree[p].lenl &＃61;&＃61; tree[p <<1].r - tree[p <<1].l &＃43; 1) {tree[p].lenl &＃43;&＃61; tree[p <<1 | 1].lenl;}tree[p].lenr &＃61; tree[p <<1 | 1].lenr;if (tree[p].lenr &＃61;&＃61; tree[p <<1 | 1].r - tree[p <<1 | 1].l &＃43; 1) {tree[p].lenr &＃43;&＃61; tree[p <<1].lenr;}tree[p].cnt &＃61; tree[p <<1].cnt &＃43; tree[p <<1 | 1].cnt;if (tree[p <<1].lenr && tree[p <<1 | 1].lenl){--tree[p].cnt;}tree[p].len &＃61; tree[p <<1].len &＃43; tree[p <<1 | 1].len;
}void build(int p, int l, int r)
{tree[p].l &＃61; l;tree[p].r &＃61; r;if (l &＃61;&＃61; r) {tree[p].cnt &＃61; tree[p].lenl &＃61; tree[p].lenr &＃61; tree[p].len &＃61; (str[l - 1] &＃61;&＃61; &＃39;.&＃39;);return;}int mid &＃61; (l &＃43; r) >> 1;build(p <<1, l, mid);build(p <<1 | 1, mid &＃43; 1, r);pushup(p);
}void update(int p, int pos)
{if (tree[p].l &＃61;&＃61; tree[p].r) {tree[p].cnt &＃61; tree[p].lenl &＃61; tree[p].lenr &＃61; tree[p].len &＃61; (str[tree[p].l - 1] &＃61;&＃61; &＃39;.&＃39;);return;}int mid &＃61; (tree[p].l &＃43; tree[p].r) >> 1;if (pos <&＃61; mid) {update(p <<1, pos);}else {update(p <<1 | 1, pos);}pushup(p);
}char v[4];
int main()
{int n, m;scanf("%d%d", &n, &m);scanf("%s", str);build(1, 1, n);int x;while (m--){scanf("%d%s", &x, v);str[x - 1] &＃61; v[0];update(1, x);printf("%d\n", tree[1].len - tree[1].cnt);}return 0;
}

转:https://www.cnblogs.com/YY56/p/4731853.html

推荐阅读

range
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
go
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
go
XNA 3.0 游戏编程：从 XML 文件加载数据

本文介绍如何在 XNA 3.0 游戏项目中从 XML 文件加载数据。我们将探讨如何将 XML 数据序列化为二进制文件，并通过内容管道加载到游戏中。此外，还会涉及自定义类型读取器和写入器的实现。 ... [详细]

蜡笔小新 2024-12-27 11:39:44
match
Java 序列化接口详解

本文深入探讨了 Java 中的 Serializable 接口，解释了其实现机制、用途及注意事项，帮助开发者更好地理解和使用序列化功能。 ... [详细]

蜡笔小新 2024-12-27 15:06:12
split
深入解析 MVC 源码：ParameterDescriptor 与 Action 方法参数绑定

在前两篇文章中，我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象，分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor，即用于描述 Action 方法参数的对象，并详细介绍其工作原理。 ... [详细]

蜡笔小新 2024-12-27 15:26:10
range
Akka BackoffSupervisor的深入解析与实践

本文详细介绍了Akka中的BackoffSupervisor机制，探讨其在处理持久化失败和Actor重启时的应用。通过具体示例，展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]

蜡笔小新 2024-12-27 15:04:09
split
Unity 客户端框架设计：UI管理系统的构建

本文详细介绍了如何构建一个高效的UI管理系统，集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑，实现功能逻辑分散化和代码复用，支持多人协作开发。 ... [详细]

蜡笔小新 2024-12-27 10:28:40
byte
从 .NET 转 Java 的自学之路：IO 流基础篇

本文详细介绍了 Java 中的 IO 流，包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据，并结合编码机制确保字符数据的正确读写。同时，文中还涵盖了装饰设计模式的应用，以及多种常见的 IO 操作实例。 ... [详细]

蜡笔小新 2024-12-26 17:37:25
byte
React 表单验证：构建无第三方库的表单处理机制

本文将深入探讨如何在不依赖第三方库的情况下，使用 React 处理表单输入和验证。我们将介绍一种高效且灵活的方法，涵盖表单提交、输入验证及错误处理等关键功能。 ... [详细]

蜡笔小新 2024-12-24 15:48:48
main
Winter-1-C A + B II 问题解析与代码实现

本文介绍了 Winter-1-C A + B II 问题的详细解题思路和测试数据。该问题要求计算两个大整数的和，并输出结果。我们将深入探讨如何处理大整数运算，确保在给定的时间和内存限制下正确求解。 ... [详细]

蜡笔小新 2024-12-24 12:26:05
select
新浪笔试题

1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]

蜡笔小新 2024-12-27 19:32:17
main
java编写的简易计算器

主要用了2个类来实现的，话不多说，直接看运行结果，然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]

蜡笔小新 2024-12-27 18:18:10
go
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
split
深入解析JDBC源码

本文详细探讨了JDBC（Java数据库连接）的内部机制，重点分析其作为服务提供者接口（SPI）框架的应用。通过类图和代码示例，展示了JDBC如何注册驱动程序、建立数据库连接以及执行SQL查询的过程。 ... [详细]

蜡笔小新 2024-12-25 19:59:15
split
使用Node.js调用Powershell脚本的方法

本文介绍如何在Node.js环境中执行Powershell脚本，并详细说明了通过子进程处理命令输出和错误信息的具体步骤。 ... [详细]

蜡笔小新 2024-12-24 20:29:37

pingyuki

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章