题目链接
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1287
题意
一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A[i] >= H），炮弹会被挡住并落在i - 1处，则A[i - 1] + 1。如果H <= A[0]，则这个炮弹无效，如果H > 所有的A[i]，这个炮弹也无效。现在给定N个整数的数组B代表炮弹高度，计算出最后地形的样子。
例如：地形高度A = {1, 2, 0, 4, 3, 2, 1, 5, 7}, 炮弹高度B = {2, 8, 0, 7, 6, 5, 3, 4, 5, 6, 5}，最终得到的地形高度为：{2, 2, 2, 4, 3, 3, 5, 6, 7}。
题解
分块这种莽夫算法解这种莽夫询问简直绝配啊。
先将n个数分成sqrt（n）块，每个维护一个最大值s[i].
求1~n第一个比H大的位置,遍历sz块，第一个s[i]比H大的块里面有所需的解。然后遍历该块的sqrt（n）个元素找出第一个比H大的位置。
建完块后，查找的时间复杂度为O（sqrt n）。修改的时间复杂度为O（1）。
建块的时间复杂度为O（n）。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+7;int belong[maxn],l[maxn],r[maxn],block,sz;
int n;
int a[maxn],s[maxn];void build()
{block=(int)sqrt(n+0.5);sz=n/block;if(n%block) sz++;for(int i=1;i<=n;i++){belong[i]=(i-1)/block+1;}for(int i=1;i<=sz;i++)l[i]=(i-1)*block+1,r[i]=i*block;r[sz]=n;for(int i=1;i<=sz;i++){for(int j=l[i];j<=r[i];j++)s[i]=max(s[i],a[j]);}
}
void add(int id,int val)
{a[id]++;s[belong[id]]=max(s[belong[id]],a[id]);
}
int query(int x)
{for(int i=1;i<=sz;i++){if(s[i]>=x){for(int j=l[i];j<=r[i];j++){if(a[j]>=x) return j;}}}return -1;
}
int main()
{int m;while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);build();int tmp=m;while(tmp--){int x;scanf("%d",&x);if(a[1]>=x) continue;int y=query(x);//第一个比x大的位置if(y==-1) continue;add(y-1,1);//第y-1号值加1}for(int i=1;i<=n;i++)printf("%d\n",a[i]);}return 0;
}