CF220B Little Elephant and Array(扫描线+树状数组)

原题链接

思路：

首先，我们可以先将所有的询问进行离线，区间问题借助扫描线的思想，枚举右端点，计算左端点产生的贡献。

考虑什么时候的区间是一个合法的区间，比如当前枚举到数xxx，如果xxx前面有x−1x-1x−1个xxx都在区间里，并且这个xxx前面的第xxx个xxx不在区间里，这个区间就是合法的区间。

举一个很典型的例子，[2,2,2,2][2,2,2,2][2,2,2,2]

当右端点为111时，整个数组产生的贡献为[0,0,0,0][0,0,0,0][0,0,0,0];

当右端点为222时，整个数组产生的贡献为[1,0,0,0][1,0,0,0][1,0,0,0];

当右端点为333时，整个数组产生的贡献为[−1,1,0,0][-1,1,0,0][−1,1,0,0];

当右端点为444时，整个数组产生的贡献为[0,−1,1,0][0,-1,1,0][0,−1,1,0];

具体有什么规律呢，首先对于遍历到的右端点先将其出现的次数加111，假设此时出现的数为xxx，那么这个数前面从右往左出现的第xxx个位置+1+1+1,第x+1x+1x+1个位置−2-2−2，第x+2x+2x+2个位置+1+1+1.

观察右端点从3−>43->43−>4的过程也可以看出这点，简单说一下理由：

当右端点为444时，我们计算出来的前缀和数组应该为[0,−1,0,0][0,-1,0,0][0,−1,0,0]，此时的合法区间为[3,4][3,4][3,4]，那么sum[4]−sum[3−1]=1sum[4]-sum[3-1]=1sum[4]−sum[3−1]=1，符合题意;而[2,4][2,4][2,4]为不合法区间，sum[4]−sum[2−1]=0sum[4]-sum[2-1]=0sum[4]−sum[2−1]=0，也同样符合题意。

用理论也可以解释：

对于从左向右出现的第xxx个位置，将他的贡献从000变为111，是因为这时候已经满足xxx出现了xxx次。

对于第x+1x+1x+1个位置，由于计算上一个xxx的贡献时候，他的贡献已经被改成111了，所以要将他的贡献改成−1-1−1。

对于第x+2x+2x+2个位置，由于计算上一个合法xxx的区间的时候，他的贡献被改成−1-1−1了，但其实他的贡献应该为000。

具体做法为：

1.1.1.将所有询问离线下来，并且记录每个数出现的位置。

2.2.2.枚举右端点，按照上述规律去维护贡献。

3.3.3.求前缀和后记录答案。

还有一个问题就是，a[i]a[i]a[i]的范围是1e91e91e9,如果直接对每个数都存出现的位置的话，空间也不允许。但是因为只有出现次数大于本身的值的数才有可能产生贡献，而n<=1e5n<=1e5n<=1e5，所以a[i]>=na[i]>=na[i]>=n的数永远不会产生贡献，就可以忽略不计了。