pubgoso_2024

树状数组

acm(131) atcoder(1) bfs(3) cf(14) clion(2) dfs(15) dp(33) KMP(3) segement tree beats(1) wannafly(7) 主席树(2) 二分(10) 匹配(2) 单调栈(2) 大数(2) 字典树(1) 字符串(3) 思维(6) 数学(50) 暴力(2) 最小生成树(7) 最短路(8) 未归档(45) 构造(1) 树(4) 树链剖分(1) 模拟(3) 矩阵(2) 离散化(5) 线段树(16) 莫队(4) 记录(3) 贪心(20)

/ 注册

全部文章 / 树状数组（共11篇）

出题人的手环(牛客练习赛38D 离散化+树状数组)

题目链接(https://ac.nowcoder.com/acm/contest/358/D) 题目描述出题人的妹子送了出题人一个手环，这个手环上有 n 个珠子，每个珠子上有一个数。有一天，出题人和妹子分手了，想把这个手环从两个珠子间切开，并按顺时针顺序展开成一条链。可以发现，这条链一共有...

2020-05-06

0 581

洛谷P1972 【[SDOI2009]HH的项链】

这道题想了很久，发题解是为了理解的更深刻一点。。。（管理放我过好嘛qwq）步入正题：这道题应该是很多做法，我选择的是离线+树状数组。首先输入数组。用fisrt数组先记录元素最开始出现的位置，对应的每一个树状数组的位置add一下（树状数组洛谷也有模板题的了解一下就ok啦）。 rep(i,...

2020-05-06

0 797

cf gym102901K The Stream of Corning 2 离线+bit

题目链接大意：给你一系列操作 1： l , v a ...

2020-05-06

0 402

2019 计蒜之道复赛 A. 外教 Michale 变身大熊猫

题目链接题意：本题就是很显然的题意，让你求出共有多少个最长上升子序列，每个数在多少个最长上升子序列中。这题的难点在于如何求出每个数在多少最长上升子序列中，显然可以用dp，直接dp时间复杂度不允许，由于我们只在前缀上转移，于是我们可以用树状数组优化dp，考虑一个结构体数组，有两个值，一个为以当前数...

2020-05-06

0 469

hdu6609 Find Answer(树状数组+二分)

题目链接题意：给你一个长度为n的数组和一个k，让你对每个i，你可以改变 1 ∼ i −...

2020-05-06

0 445

牛客练习赛58 F.XOR TREE

题目链接思路：给的一条路径，统计所有被奇数个路径包含的点的异或和。路径上的点显然是深度连续递增的点，那么我们根据两端深度的奇偶情况就可以知道路径上的哪些点是有贡献的。把路径剖出来，用bit维护一下异或和即可。 #include <bits/stdc++.h> using name...

2020-05-06

0 443

hdu6609 Find Answer(树状数组+二分)

题目链接题意：给你一个长度为n的数组和一个k，让你对每个i，你可以改变 1 ∼ i −...

2019-07-30

0 653

2019 计蒜之道复赛 A. 外教 Michale 变身大熊猫

题目链接题意：本题就是很显然的题意，让你求出共有多少个最长上升子序列，每个数在多少个最长上升子序列中。这题的难点在于如何求出每个数在多少最长上升子序列中，显然可以用dp，直接dp时间复杂度不允许，由于我们只在前缀上转移，于是我们可以用树状数组优化dp，考虑一个结构体数组，有两个值，一个为以当前数...

2019-07-12

0 381

cf gym102901K The Stream of Corning 2 离线+bit

题目链接大意：给你一系列操作 1： l , v a ...

2019-05-03

0 386

洛谷P1972 【[SDOI2009]HH的项链】

这道题想了很久，发题解是为了理解的更深刻一点。。。（管理放我过好嘛qwq）步入正题：这道题应该是很多做法，我选择的是离线+树状数组。首先输入数组。用fisrt数组先记录元素最开始出现的位置，对应的每一个树状数组的位置add一下（树状数组洛谷也有模板题的了解一下就ok啦）。 rep(i,...

2019-01-19

0 358