传送门:https://nanti.jisuanke.com/t/41356

题目大意:给你一个序列。两种操作.1.单点修改 2.区间查询值域在[a,b]之间的连续段个数 (n , m <= 2e5 , TimeLimit = 3.5s)

思路：

方法一:分块套树状数组

对原序列分块。对每一个块维护一个值域树状数组。

单点修改时，分两步走修改贡献：第一步计算删除原来的点所造成的贡献,第二步计算增加新的点所造成的贡献.

区间查询：分别求[a,b]的个数和。对于段与段之间的连接处，判断相同，容斥掉多算的贡献.

重点：分块大小分析（余块的和整块的计算复杂度尽量均摊）

1.单点修改这个部分复杂度远小于区间查询，可忽略。

2.区间查询:设分块大小为B，整块的查询复杂度为C2,余块的查询的复杂度是C1.

对分块大小B以及复杂度简单分析如下所示：

理论上来讲比 B = sqrt(n) 要快4倍左右.

那么分块做法就需要分析以上关键部分了.

方法二：三维偏序-CDQ分治套树状数组

这样的动态问题我们可以利用CDQ分治将其转变成静态问题.

那么首先第一步就是找偏序点对关系。 大致三个维度(Time , Pos , Value) 代表读入顺序，序列位置，值域。

然后对于连续的段，我们将贡献计算到某点上。这样贡献独立了

然后查询的答案在位置上可以差分，在值域上也能差分。那么我们可以将查询根据区间拆分成两个部分。 但是注意特判两段接口处的值是否符合答案，符合就答案++.

对于单点修改，存在问题：当前修改所造成的影响依赖于数组之前的样子。

这里我们提出一个解决技巧：随时间模拟修改数组  ---就是边读入，边模拟，这样就解决了修改不独立的情况。

然后还是 注意，对于修改。我们先算删除的贡献，在算新增的贡献。记得数组开大几倍.

 最后，对于CDQ分治中的三个维度：

第一维自然有序，第二维序列位置用CDQ维护，第三维值域利用值域树状数组进行维护。查询答案时，查询值域树状数组的区间和即可。