（线段树字符串的处理）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

推荐阅读

copy
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
object
Java 序列化接口详解

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

蜡笔小新 2024-12-27 15:06:12
range
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

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

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

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

蜡笔小新 2024-12-25 17:47:23
case
哈密顿回路检测问题【25分】

哈密顿回路问题旨在寻找一个简单回路，该回路包含图中的每个顶点。本文将介绍如何判断给定的路径是否构成哈密顿回路。 ... [详细]

蜡笔小新 2024-12-23 21:02:53
case
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
case
Winter-1-C A + B II 问题解析与代码实现

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

蜡笔小新 2024-12-24 12:26:05
object
Handling Null Object Encoding in OAuth 1.0a API Implementation

Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]

蜡笔小新 2024-12-28 08:54:34
range
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
web
技术分享：从动态网站提取站点密钥的解决方案

本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]

蜡笔小新 2024-12-28 04:11:47
go
分页插件3指定到某一页

前言--页数多了以后需要指定到某一页（只做了功能，样式没有细调）html ... [详细]

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

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

蜡笔小新 2024-12-27 15:04:09
object
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14
spring
深入解析 org.apache.xmlbeans.SchemaType.getBaseEnumType() 方法及其应用

本文详细介绍了 Java 中 org.apache.xmlbeans.SchemaType 类的 getBaseEnumType() 方法，提供了多个代码示例，并解释了其在不同场景下的使用方法。 ... [详细]

蜡笔小新 2024-12-26 11:46:55
jar
深入解析JDBC源码

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

蜡笔小新 2024-12-25 19:59:15

pingyuki

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

Tags | 热门标签

RankList | 热门文章