夢に僕らで帆を張って
来るべき日のために夜を超え

标签 树状数组 下的文章

October 24, 2019

洛谷P4113/HEOI2012 采花

题意给出一个数列,有$m$次询问,求$[l,r]$之间有多少个出现次数$\ge 2$的数数据范围:$1 \le n,m \le 2 \cdot 10^6$题解对于每个区间,若一个数出现了$\ge 2$次,将其贡献计在第$2$个上(因为第$1$个无法产生贡献,而$\ge 2$与$=2$产生的贡献并无区别)这样,记录一个$nxt[i]$表示下一个与$i$相等的数出现的位置将询问离线,按左端点排序...
October 23, 2019

洛谷P3586/POI2015 LOG

题意维护一个长度为$n$的序列,一开始都是$0$,支持以下两种操作:$U \ k \ a$ 将序列中第$k$个数修改为$a$$Z \ c \ s$ 在这个序列上,每次选出$c$个正数,并将它们都减去$1$,询问能否进行$s$次操作每次询问独立,即每次询问不会对序列进行修改数据范围:$1 \le n,m \le 1000000$题解对于一个询问,记$\ge s$的数有$x$个,$< s$...
October 20, 2019

洛谷P4054/JSOI2009 计数问题

题意一个$n \times m$的方格,初始时每个格子有一个整数权值接下来每次有$2$种操作改变一个格子的权值求一个子矩阵中某种特定权值出现的个数数据范围:$n,m \le 300,1 \le c \le 100$题解$n,m,c$较小,对于每个$c$开一个二维树状数组维护代码:#include<iostream> #include<cstdio> using nam...
October 15, 2019

洛谷P3616 富金森林公园

题意对于一个数列,有$2$种操作:$1 \ x$ 询问$\ge x$的连续段的个数$2 \ i \ x$ 将$a_i$的值修改为$x$数据范围:$1 \le n,m \le 200000,1 \le a_i,x \le 10^9$题解首先对于一个询问考虑:将$\ge x$的数定义为$1$,$< x$的数定义为$0$;那么一个段的构成应为$$011 \dots 110$$即一个$01$+...