Fizzmy

线段树

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章 / 线段树（共12篇）

Codeforces 899F Letters Removin-线段树

传送门题意：给一个字符串和m个操作，每次给出l,r,c，把字符串中l-r这段区间的字符为c的字符删掉，求最后的字符串。（n,m<=2e5） Solution：此题显然不能离线搞，那么有什么动态的优秀的数据结构呢？我们一定会先想到线段树，我们可以维护每个区间剩余字符的个数siz和区...

2021-08-18

0 353

hdu6039 Gear Up-线段树

题意：给出n个齿轮的半径和n个齿轮之间的关系（角速度相等或线速度相等），两种操作，第一种操作：修改一个齿轮的半径，第二种操作：给一个齿轮角速度，输出最大的角速度，答案取ln（自然对数）。 Solution：我们随意画一个图感受一下：（粗边表示角速度相等，细边表示线速度相等，图中维护...

2021-08-18

0 380

BZOJ2957 楼房重建-线段树

题意：小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段...

2021-08-18

0 394

Codeforces 343D Water Tree-线段树

传送门题意：给你一棵树，有三种操作： 1. 给一个点及其子孙赋值为1 2. 给一个点及其祖先赋值为0 3. 求一个点是1还是0 Solution：这道题显然可以用树剖做，但是复杂度不优秀（两个log），这里说一种一个log的做法：先跑出树的dfs序，对dfs序建一棵线段树，那...

2021-08-18

0 367

bzoj2951: [Poi2001]Goldmine-线段树

题意：给出n个天然金矿石的位置，选一小块长方形的矿地，此矿地长和宽为s和w且平行于坐标系统的轴线。这块地的价值是这块区域内天然金矿石的数量。计算出这块地的最大可能价值。（ 1≤s,w≤10000,1≤n≤15000 1 ≤ s , w ≤ 10000 , 1 ≤ n ≤ 15000 ） ...

2021-08-18

0 335

Codeforces 920F SUM and REPLACE-线段树+欧拉筛

传送门题意： n个数a，q个操作，两种操作类型： 1.[l,r]区间中每个数替换为这个数的因数个数 2.区间求和 q,n<=3e5,ai<=1e6 q , n <= 3 e 5 , a i <= 1 e 6 Solution: 值为1或2的数是不需要再进...

2021-08-18

0 411

Codeforces 935F. Fafa and Array-线段树

传送门题意：给出一个序列A，定义函数 f(A)=∑n−1i=1|ai−ai+1| f ( A ) = ∑ i = 1 n − 1 | a i − a i + 1 | 先给出两种操作： 1.在区间[l,r]内找一个位置，使得把这个位置的值加上x后，f(A)最大，求这个最大值 2.把区...

2021-08-18

0 345

BZOJ2124 等差子序列-线段树+hash

传送门题意：给出一个N的排列，问是否存在一个长度至少为3的等差子序列 n<=10000 Solution：注意到我们给出的是一个排列，而且我们只需要找长度为3的子序列即可那么我们可以枚举中间项x，用01串S和T来表示x前面的数中[1,x-1]和[x+1,x+x-1]是否出现...

2021-08-18

0 360

BZOJ4869: [Shoi2017]相逢是问候-线段树+数论

传送门题意：给出一个序列a，两种操作 1.将[l,r]这段区间所有的数 ai a i 换为 cai c a i 2.求[l,r]这段区间的和，对p取模 1≤n≤50000; 1≤m≤50000; 1≤p≤100000000; 0<c<p; 0≤ai<p 1 ...

2021-08-18

0 300

BZOJ5249：[2018多省省队联测]IIIDX-线段树

传送门题意：你需要给给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n首曲目，每首曲目都会有一个难度d，游戏内第i首曲目会在玩家Pass第 ⌊ik⌋ ⌊ i k ⌋ 首曲目后解锁。安排这些曲目的顺序，使得每次解锁出的子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确...

2021-08-18

0 267