51nod 1287 – 加农炮(树状数组or线段树+优先队列+map)

一个长度为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}。

(1 <= m, n <= 50000)  (0 <= A[i]，B[i] <= 1000000)

【分析】

【方法一】：

我想到了一个比较烦的方法：首先，用线段树保存每个高度最小的位置号，然后对于一颗炮弹落到的位置直接询问线段树即可。

而对于确定炮弹掉落的位置后，那么需要更新线段树，首先需要让原来的高度变成去掉当前位置后的最左边的位置，然后在高度+1后的高度上添加当前位置更新最小值。后者很简单，直接更新即可。但是对于“让原来的高度变成去掉当前位置后的最左边的位置”这个需要用一个优先队列保存每个高度的最小位置队列，然后还需要map来判断高度i在位置j是否被删除。那么在当前高度有点队列中去掉被删除的最小值之后的就可以得到”去掉当前位置后的最左边的位置”，这样总的复杂度为O(N*log(MAX{A[i]})).

其实完全没那个必要，不需要去管“让原来的高度变成去掉当前位置后的最左边的位置”，因为每个高度只会增加，而每个高度最左边的位置只会减小，不会增加，所以只需要树状数组就可以了。

【AC CODE】500ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10;
int a[MAXN],b[MAXN];

int mi[1000000+10],mx;
inline int lowbit(int x){return x&-x;}
void update(int x, int v)
{
	while(x <= mx)
	{
		mi[x] = min(mi[x],v);
		x += lowbit(x);
	}
}
int query(int x)
{
	int ans = INF;
	while(x > 0)
	{
		ans = min(ans,mi[x]);
		x -= lowbit(x);
	}
	return ans;
}
inline int get_id(int x)
{
	return 1000002-x;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,m;
	scanf("%d%d", &n,&m);
	mx = INF;
	clc(mi,0x3f);
	repe(i,1,n)
		scanf("%d", &a[i]),mx = min(mx,a[i]);
	repe(i,1,m)
		scanf("%d", &b[i]),mx = min(mx,b[i]);
	mx = get_id(mx);
	repe(i,1,n)
		update(get_id(a[i]),i);
	repe(i,1,m)
	{
		int p = query(get_id(b[i]))-1;//找到高度>=b[i]的最小位置
		if(0 == p || INF-1 == p) continue;
		a[p]++;
		update(get_id(a[p]),p);//更新+1后的最小值
		//vis[P(a[p])]
	}
	repe(i,1,n) printf("%d\n",a[i]);
	return 0;
}

【方法二】：不难发现，对于高度的增加所掉落的位置是非递减的，那么可以O(MAX{A[i]})的预处理每个高度所掉落的位置p[]，对于每次炮弹的射击，只会让该高度掉落的位置增加，那么每个p只会变小，不会变大。这样O(m)扫一遍就可以了。

【AC CODE】468ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10;
int a[MAXN],b[MAXN],p[1000000+10];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,m,mx = 0;
	scanf("%d%d", &n,&m);
	repe(i,1,n) scanf("%d", &a[i]);
	repe(i,1,m) scanf("%d", &b[i]),mx = max(mx,b[i]);
	int s = 1;
	repe(i,1,mx)
	{
		while(s <= n && a[s] < i) s++;
		p[i] = s-1;
	}
	repe(i,1,m)
	{
		int v = p[b[i]];
		if(0 == v || n == v) continue;
		a[v]++;
		p[a[v]] = min(p[a[v]],v-1);
	}
	repe(i,1,n) printf("%d\n",a[i]);
	return 0;
}