Codeforces 1625E2 括号树 + BIT
题意
传送门 Codeforces 1625E2 Cats on the Upgrade (hard version)
题解
首先利用栈将原始字符串转换为合法的 RBS,不能匹配的括号设为 ‘.’。根据匹配的括号序列构造树,具体而言,遇到左括号,则新建节点向下递归,遇到右括号则回溯。则对于括号树上某一结点 v v v,子节点为 c h i ch_i chi,其代表的合法括号序列 R B S v = ( R B S c h 0 ) ( R B S c h 1 ) ⋯ RBS_v = (RBS_{ch_0})(RBS_{ch_1})\cdots RBSv=(RBSch0)(RBSch1)⋯
对于某棵子树的答案,为子树的贡献,加上 k ( k + 1 ) / 2 k(k+1)/2 k(k+1)/2,其中 k k k 为子树的数量,后一项贡献代表了连续的 R B S c h RBS_{ch} RBSch 的枚举。操作 1 仅删除叶子节点与其双亲节点的连边,那么使用 BIT 维护节点的贡献和,以及每个节点的子树数量即可。总时间复杂度 O ( ( n + q ) log n ) O\Big((n + q)\log{n}\Big) O((n+q)logn)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
struct BIT {vector<T> a;BIT() {}void init(int n) {a.resize(n + 1);}void add(int i, T x) {while (i < (int)a.size()) {a[i] += x;i += i & -i;}}T get(int i) {T s = 0;while (i > 0) {s += a[i];i -= i & -i;}return s;}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, q;cin >> n >> q;string s;cin >> s;{vector<int> stk;for (int i = 0; i < n; ++i) {auto c = s[i];if (c == '(') {stk.push_back(i);} else {if (stk.empty()) {s[i] = '.';} else {stk.pop_back();}}}while (!stk.empty()) {s[stk.back()] = '.';stk.pop_back();}}vector<vector<int>> g(1);vector<int> vs(n), idx(n);{int pos = 0;auto nxt = [&]() {while (pos < n && s[pos] == '.') {pos += 1;}return pos;};function<void(int)> get = [&](int v) {while (nxt() < n && s[pos] == '(') {int u = g.size();g.push_back({});g[v].push_back(u);vs[pos] = v;idx[pos] = (int)g[v].size() - 1;pos += 1;get(u);nxt();vs[pos] = v;idx[pos] = (int)g[v].size() - 1;pos += 1;}};get(0);}int m = vs.size();BIT<ll> bit;bit.init(m);vector<BIT<int>> v_bit(m);vector<int> left(m), right(m);{int tm = 0;function<void(int)> dfs = [&](int v) {left[v] = tm;tm += 1;int k = g[v].size();v_bit[v].init(k);for (int i = 0; i < k; ++i) {v_bit[v].add(i + 1, 1);}bit.add(left[v] + 1, (ll)(k + 1) * k / 2);for (int u : g[v]) {dfs(u);}right[v] = tm;};dfs(0);}while (q--) {int op, l, r;cin >> op >> l >> r;l -= 1;r -= 1;assert(vs[l] == vs[r]);int v = vs[l];int a = idx[l], b = idx[r];if (op == 1) {bit.add(left[v] + 1, -v_bit[v].get((int)g[v].size()));v_bit[v].add(a + 1, -1);} else {ll res = bit.get(right[g[v][b]]) - bit.get(left[g[v][a]]);int k = v_bit[v].get(b + 1) - v_bit[v].get(a);res += (ll)(k + 1) * k / 2;cout << res << '\n';}}return 0;
}
相关文章:
Codeforces 1625E2 括号树 + BIT
题意 传送门 Codeforces 1625E2 Cats on the Upgrade (hard version) 题解 首先利用栈将原始字符串转换为合法的 RBS,不能匹配的括号设为 ‘.’。根据匹配的括号序列构造树,具体而言,遇到左括号,则新建节点向下递归,…...
PHP命令行CLI的使用
PHP命令行界面 PHP命令行界面(CLI)是一种使用命令行(终端)来运行PHP脚本的方式,与在Web服务器环境下运行PHP不同。CLI提供了一种与操作系统交互的方式,能够在命令行中直接执行PHP代码。 以下是一些与PHP命…...
近期嵌软线下笔试题记录
1、以下代码的输出结果是? #include <stdio.h> #include <string.h>int main() {int a,b,c,d;a 10;b a; //a先赋值给b,然后自增1c a; //a自增1后赋值给cd 10*a; //先进行运算然后a自增1printf("b,c,d:%d…...

基于MYSQL的主从同步和读写分离
目录 一.完成MySQL主从同步(一主两从) 1.主库配置 2.建立同步账号 3.锁表设置只读 4.备份数据库数据 5.主库备份数据上传到从库 6.从库上还原备份 7.解锁 8.从库上设定主从同步 9.启动从库同步开关 10.检查状态 二.基于MySQL一主两从配置&…...

java八股文面试[多线程]——合适的线程数是多少
知识来源: 【并发与线程】 合适的线程数量是多少?CPU 核心数和线程数的关系?_哔哩哔哩_bilibili 【2023年面试】程序开多少线程合适_哔哩哔哩_bilibili...

Linux系统下vim常用命令
一、基础命令: v:可视模式 i:插入模式 esc:命令模式下 :q :退出 :wq :保存并退出 ZZ:保存并退出 :q! :不保存并强制退出二、在Esc下: dd : 删除当前行 yy:复制当前行 p:复制已粘贴的文本 u:撤销上一步 U:…...
【2023】LeetCode HOT 100——链表
目录 1. 相交链表1.1 C++实现1.2 Python实现1.3 时空分析2. 反转链表2.1 C++实现2.2 Python实现2.3 时空分析3. 回文链表3.1 C++实现3.2 Python实现3.3 时空分析4. 环形链表4.1 C++实现4.2 Python实现4.3 时空分析5. 环形链表 II5.1 C++实现5.2 Python实现...

智能井盖传感器,物联网智能井盖系统
随着城市人口的不断增加和城市化进程的不断推进,城市基础设施的安全和可靠性变得愈发重要,城市窨井盖作为城市基础设施重要组成部分之一,其安全性事关城市安全有序运行和居民生产生活安全保障。 近年来,各地都在加强城市窨井盖治理…...
C语言三子棋解析
目录(标2的是我自己写的一堆问题不知道怎么改) 开始菜单1打印棋盘1玩家下棋1电脑下棋1判断输赢1开始菜单2打印棋盘2选择先后2玩家下棋2电脑下棋2判断输赢2完整代码文件else.h文件else.c文件test.c 开始菜单1 void menu()//打印菜单 {printf("*****…...

【Jenkins打包服务,Dockerfile报错:manifest for java : 8 not fourd】
1、问题描述 Jenkins打包服务运行dockerfile里的FROM java:8报错manifest for java : 8 not fourd Caused by: com.spotify. docker.client.exceptions.DockerException: manifest for java:8 not found2、解决方法 在网上查找许多方法后得出这是由于Docker官方已经弃用java…...

读SQL学习指南(第3版)笔记06_连接和集合
1. 连接 1.1. 笛卡儿积 1.1.1. 交叉连接(cross join) 1.1.2. 查询并没有指定两个数据表应该如何连接,数据库服务器就生成了笛卡儿积 1.1.2.1. 两个数据表的所有排列组合 1.1.3. 很少会用到(至少不会特意用到) 1.…...
C#学习,结构,面向对象,类
结构和类 结构是从过程化程序设计中保留下来的一种数据类型,类则是面向对象程序设计中最基本的、也是最重要的概念。 结构 结构是一种值类型,通常用来封装一组相关的变量,结构中可以包含构造函数、变量、字段、方法、属性、运算符、事件和…...

【PHP】文件操作
文章目录 文件编程的必要性目录操作其它目录操作递归遍历目录PHP5常见文件操作函数PHP4常见文件操作函数其他文件操作函数 文件编程的必要性 文件编程指利用PHP代码针对文件(文件夹)进行增删改查操作。 在实际开发项目中,会有很多内容&…...

科创板50ETF期权交易:详细规则、费用、保证金和开户攻略
科创板50ETF期权是指以科创板50ETF为标的资产的期权合约。科创板50ETF是由交易所推出的一种交易型开放式指数基金(ETF),旨在跟踪科创板50指数的表现,下文介绍科创板50ETF期权交易:详细规则、费用、保证金和开户攻略&am…...

怎么把图片放大并且清晰?有详细的方法步骤
怎么把图片放大并且清晰?数字图像处理中的图片放大是许多行业和领域中广泛应用的一项技术。常规的放大方法通过插值或复制像素的方式增加像素数,但这会导致失真和模糊。无损放大是一种特殊的放大方法,它可以通过数学算法来增加图片的尺寸&…...
C++ 构造函数、析构函数调用虚函数
C虚函数是通过虚表实现的,虚函数的地址记录在需表中,只对象完成构造完成后,虚函数的地址才最终确定。 构造函数中调用虚函数 基类先于派生类构造,所以构造时没法调用到派生类的虚函数,也就是说只能调用到自己&#x…...

工业状态监测如何选择合适的无线技术?
工业领域的状态监测在提高生产效率和产品质量方面起着关键作用。过去依赖于预防性维护和例行检查的方式已经不再能满足日益复杂的生产需求,随着工业物联网(IIoT)的兴起,设备状态监测逐渐成为一种关键策略,催生了预测性…...

Mysql45讲学习笔记
前言:这篇文章主要总结事务,锁、索引的一些知识点,然后分享一下自己学习小心得,我会从点到线在到面展开说说,对于学习任何知识,我们都应该藐其全貌,不要一开始就选入细节 基础 一、基础架构&a…...
Neither the JAVA_HOME nor the JRE_HOME environment variable is defined
报错描述 情景一 1Panel在"主机-->进程守护"通过命令"nohup /opt/tomcat/bin/startup.sh > /opt/supersivor/tomcat/nohup.log &"创建守护进程,运行日志如下: #--------------------------------------------------------…...

opencv 水果识别+UI界面识别系统,可训练自定义的水果数据集
目录 一、实现和完整UI视频效果展示 主界面: 测试图片结果界面: 自定义图片结果界面: 二、原理介绍: 图像预处理 HOG特征提取算法 数据准备 SVM支持向量机算法 预测和评估 完整演示视频: 完整代码链接 一、…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...

Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...

如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...

Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...