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支持向量机算法 预测和评估 完整演示视频: 完整代码链接 一、…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...

论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
32单片机——基本定时器
STM32F103有众多的定时器,其中包括2个基本定时器(TIM6和TIM7)、4个通用定时器(TIM2~TIM5)、2个高级控制定时器(TIM1和TIM8),这些定时器彼此完全独立,不共享任何资源 1、定…...
【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解
一、前言 在HarmonyOS 5的应用开发模型中,featureAbility是旧版FA模型(Feature Ability)的用法,Stage模型已采用全新的应用架构,推荐使用组件化的上下文获取方式,而非依赖featureAbility。 FA大概是API7之…...
深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙
WebGL:在浏览器中解锁3D世界的魔法钥匙 引言:网页的边界正在消失 在数字化浪潮的推动下,网页早已不再是静态信息的展示窗口。如今,我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室,甚至沉浸式的V…...

负载均衡器》》LVS、Nginx、HAproxy 区别
虚拟主机 先4,后7...

高效的后台管理系统——可进行二次开发
随着互联网技术的迅猛发展,企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心,成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统,它不仅支持跨平台应用,还能提供丰富…...

leetcode_69.x的平方根
题目如下 : 看到题 ,我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历,我们是整数的平方根,所以我们分两…...
C#最佳实践:为何优先使用as或is而非强制转换
C#最佳实践:为何优先使用as或is而非强制转换 在 C# 的编程世界里,类型转换是我们经常会遇到的操作。就像在现实生活中,我们可能需要把不同形状的物品重新整理归类一样,在代码里,我们也常常需要将一个数据类型转换为另…...