正文
【树状数组 思维题】luoguP3616 富金森林公园
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
树状数组、差分、前缀和、离散化
题目描述
博艾的富金森林公园里有一个长长的富金山脉，山脉是由一块块巨石并列构成的，编号从1到N。每一个巨石有一个海拔高度。而这个山脉又在一个盆地中，盆地里可能会积水，积水也有一个海拔高度，所有严格低于这个海拔高度的巨石，就会在水面下隐藏。
由于地壳运动，巨石的海拔高度可能会随时变化，每次一块的巨石会变成新的海拔高度。当然，水面的高度也会随时发生变化。
因为有这样奇妙的地质奇观，吸引了很多游客来游玩。uim作为一个游客，可以告诉你此时水位海拔，你得告诉他，能看到有几个连续露出水面的部分。（与水面持平我们也认为是露出）
输入输出格式
输入格式：
第一行两个整数N和M,分别表示N块石头，M个询问。
接下来一行，N个整数Ai表示每个巨石的初始海拔。
接下来M行，每行有两个或者三个数，每一行如果第一个数是1，那么后面跟一个Bj，表示水面海拔。如果第一个数是2，后面跟两个整数，Cj和Dj，表示编号Cj的巨石海拔变为Dj。
输出格式：
对于每个"1"询问，给出一个整数答案，也就是露出了几部分的山峰。
说明
10%的数据， N,M<=2000
另外30%的数据， 只有"1"的询问。
100%的数据， 1<=N,M<=200000,1<=Ai,Bj,Dj<=10^9，一定有"1"询问
题目分析
首先考虑暴力。每一次直接修改，查询时候$O(n)$查询，总复杂度$O(NM)$这样能拿50分。比赛做的时候有想过用树状数组维护，但是由于每次高度查询都不相同，因此没有搞出来。
后来去请教YKH，也看了看他的代码。这题用树状数组维护前缀和没有错，不过还要涉及到差分和离散化的应用。
容易发现在高度已知的情况下，对于相邻两个元素$f[i] > f[i-1]$，当且仅当$f[i-1] < query-height < f[i]$时对答案有贡献。那么可以看出，对于一组$f[i-1],f[i]$，它对任意$f[i-1] < height < f[i]$都有价值为1的贡献。显而易见的，这个特性使得我们可以用线性数据结构维护它。而差分+单点查询区间修改的树状数组是不错的选择（当然线段树也可以并且思维复杂度略小，不过比有差分的树状数组要慢不少）。
我们先将操作行为全部读入，考虑离线做法。
看到数据范围就知道直接用下标作为高度是会原地爆炸的。所以先将原始点和操作点都先存储起来，再对它们一起离散化。这样就可以避免已经离散化的一个数列例如{$1,3,5,7(原始)$}→{$1,2,3,4(离散化)$}再修改出未曾安排过离散的数例如{$1,3,5,7(原始)$}→{$1,3,5,4(修改后)$}→{$1,2,3,?(此时离散化爆炸)$}。
所有数据都读入之后，再对所有点按高度排序（不管它本身的属性是询问点还是修改点）。接下去先对点集手工离散化（不用unique的原因是这里不同类型的点离散化操作不同）。
离散化后我们拥有的数据应该是这样的：
$Q[i][0..2] i≤m$ 记录所有操作
$按照高度排序的s[]$ 记录所有点
数据既然已经预处理好了，接下去就是先对$tot$个点处理一遍了。处理也就不过是按照差分的思路单点修改。
处理操作时，对于query我们直接用树状数组对于查询点离散后的高度求前缀和；对于update我们要先考虑修改前的点是否与相邻的点产生贡献。因为这里的历史性是连续的（当前状况只从上一次操作转移过来），所以差分可以轻松完成撤销操作——只要根据原数据的逆操作即可。同理，更新过后再在左右检查一遍是否对答案有贡献，这样复杂度就是有保证的了。实测此方法540ms可过。
上YKH的代码（注释是我学习他代码过程中边看边打的）
#include <cstdio>
#include <algorithm>
using namespace std; int read()
{
char c;while(c=getchar(),c<''||c>'');
int x=c-'';while(c=getchar(),c>=''&&c<='')x=x*+c-'';
return x;
} int N,M,tot,x,y,Q[][],H[]; struct wx{
int x,y,c;//c-0原先高度 c-1询问 c-2修改操作
}S[]; int cmp(wx x,wx y){return x.x<y.x;} int ar[]; void add(int x,int y)
{
for(int i=x;i<=tot;i+=i&-i){
ar[i]+=y;
}
return ;
} int get(int x)
{
int tot=;
for(int i=x;i>;i-=i&-i){
tot+=ar[i];
}
return tot;
} int main()
{
// freopen("x.txt","r",stdin);
// freopen("w.txt","w",stdout);
N=read(),M=read();
register int i,j;
for(i=;i<=N;i++)x=read(),S[++tot]=(wx){x,i,};
for(i=;i<=M;i++){
Q[i][]=read(),y=read();
if(Q[i][]==){
Q[i][]=y;y=read();
S[++tot]=(wx){y,i,};
continue;
}
S[++tot]=(wx){y,i,};
} //Q[i][0]表示操作的类型 sort(S+,S+tot+,cmp);
S[].x=-2e9;
int col=;
for(i=;i<=tot;i++){
if(S[i].x!=S[i-].x)col++;
if(S[i].c==)Q[S[i].y][]=col;
else if(S[i].c==)Q[S[i].y][]=col;
else H[S[i].y]=col;//对H[]离散化
}
for(i=;i<=N;i++){
if(H[i]>H[i-]){
add(H[i-]+,);
add(H[i]+,-);
}
}
for(i=;i<=M;i++){
if(Q[i][]==)printf("%d\n",get(Q[i][]));
else {//离线update
if(H[Q[i][]]>H[Q[i][]-]){
add(H[Q[i][]-]+,-);
add(H[Q[i][]]+,);
}
if(Q[i][]<N && H[Q[i][]]<H[Q[i][]+]){
add(H[Q[i][]]+,-);
add(H[Q[i][]+]+,);
}
H[Q[i][]]=Q[i][];
if(H[Q[i][]]>H[Q[i][]-]){
add(H[Q[i][]-]+,);
add(H[Q[i][]]+,-);
}
if(Q[i][]<N && H[Q[i][]]<H[Q[i][]+]){
add(H[Q[i][]]+,);
add(H[Q[i][]+]+,-);
}
}
}
return ;
}
这是我的代码（自认为可读性挺高emm）
#include<bits/stdc++.h>
using namespace std;
const int N = *1e5+;
const int M = *1e5+;
struct point
{
int x,y,c;
}s[N+M];
int Q[M][],height[*N],dl[*N],n,m,tot;
inline int lowbit(int x){return x&-x;}
inline void add(int x, int c){for (; x<=tot; x+=lowbit(x))dl[x]+=c;}
inline int query(int x)
{
int ret = ;
for (; x; x-=lowbit(x))ret+=dl[x];
return ret;
}
inline int read()
{
int x = ;char c = getchar();
while (c<''||c>'')c = getchar();
while (c>=''&&c<=''){x = x*+c-;c = getchar();}
return x;
}
bool cmp(point a, point b){return a.x<b.x;}
int main()
{
n = read();m = read();
for (int i=; i<=n; i++)s[++tot] = (point){read(), i, };
for (int i=; i<=m; i++)
{
Q[i][] = read();
int y = read();
if (Q[i][]-){
Q[i][] = y;y = read();
s[++tot] = (point){y, i, };
continue;
}
s[++tot] = (point){y, i, };
}
sort(s+, s+tot+, cmp);
int col = ;
s[].x = -*1e9;
for (int i=; i<=tot; i++)
{
if (s[i].x!=s[i-].x)col++;
if (s[i].c==)Q[s[i].y][] = col;
else if (s[i].c==)Q[s[i].y][] = col;
else height[s[i].y] = col;
}
for (int i=; i<=n; i++)
{
if (height[i]>height[i-])
{
add(height[i]+, -);
add(height[i-]+, );
}
}
for (int i=; i<=m; i++)
{
if (-Q[i][]){printf("%d\n",query(Q[i][]));continue;}
int qs = Q[i][];
if (height[qs-]<height[qs])
{
add(height[qs]+, );
add(height[qs-]+, -);
}
if (qs < n&&height[qs]<height[qs+])
{
add(height[qs+]+, );
add(height[qs]+, -);
}
height[qs] = Q[i][];
if (height[qs-]<height[qs])
{
add(height[qs]+, -);
add(height[qs-]+, );
}
if (qs < n&&height[qs]<height[qs+])
{
add(height[qs+]+, -);
add(height[qs]+, );
}
}
return ;
}
