C++11(clang++ 3.9) 解法, 执行用时: 868ms, 内存消耗: 28636K, 提交时间: 2020-06-08 12:18:18

#include<bits/stdc++.h>
using namespace std;

int a[100005], segtree[400020];

void build(int l,int r,int root){
	if(l == r) segtree[root]=a[l];
	else{
		int mid = (l+r)>>1;
		build(l,mid,root<<1);
		build(mid+1,r,root<<1|1);
		segtree[root] = max(segtree[root<<1],segtree[root<<1|1]);
	}
}

int update(int l,int r,int root,int H,int h){
	if(segtree[root]<H) return 0;
	if(l==r){
		segtree[root]=h;
		return l;
	}
	int mid = (l+r)>>1, p;
	if(segtree[root<<1]>=H) p = update(l,mid,root<<1,H,h);
	else p = update(mid+1,r,root<<1|1,H,h);
	segtree[root] = max(segtree[root<<1],segtree[root<<1|1]);
	return p;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n, m;
		scanf("%d %d",&n,&m);
		for(int i = 1;i <= n;i++)
			scanf("%d",&a[i]);
		build(1,n,1);
		while(m--){
			int H, h;
			scanf("%d%d",&H,&h);
			int p = update(1,n,1,H,h);
			a[p]=h;
		}
		for(int i = 1;i < n;i++)
			printf("%d ",a[i]);
		printf("%d\n",a[n]);
	}
	return 0;
} 

C++14(g++5.4) 解法, 执行用时: 700ms, 内存消耗: 10608K, 提交时间: 2020-06-07 14:56:45

#include<bits/stdc++.h>
using namespace std;

struct book
{
	int l, r, v;
}a[4000005];

int vl[1000005];

void make(int left, int right, int num)
{
	a[num].l=left;
	a[num].r=right;
	if(a[num].l==a[num].r)
		a[num].v=vl[left];
	else
	{
		make(left,(left+right)/2,num*2);
		make((left+right)/2+1,right,num*2+1);
		a[num].v=max(a[num*2].v, a[num*2+1].v);
	}
}

void Q(int H, int h, int num)
{
	if(a[num].l == a[num].r)
	{
		a[num].v = h;
		vl[a[num].l] = h;
		return ;
	}
	if(H > a[num].v)
		return ;
	else
	{
		if(H <= a[num*2].v)
			Q(H,h,num*2);
		else
			Q(H,h,num*2+1);
	}
	a[num].v=max(a[num*2].v, a[num*2+1].v);
}

int main()
{
	int t = 1;
	scanf("%d", &t);
	while(t--)
	{
		int n, q;
		scanf("%d %d", &n, &q);
		for(int i = 1; i <= n; i++)
			scanf("%d", &vl[i]);
		make(1,n,1);
		while(q--)
		{
			int H, h;
			scanf("%d %d", &H, &h);
			Q(H,h,1);
		}
		for(int i = 1; i <= n; i++)
			printf("%d ", vl[i]);
		printf("\n");
	}
}