本文共 890 字，大约阅读时间需要 2 分钟。

题意

给一个大小n的数组，有q次操作，操作有两种：

1 p x，将第p个数变成x； 2 x，将数组中小于x的数变成x，大于x的数不变

思路

用last[i]数组记录一下第i个数的最后一次1操作是总操作的第几次操作；

lastX数组记录第i个数最后一次1操作改变的的数（或者原本的数） lastAllToX数组记录第i次操作后面（包括i）的2操作最大的x lastAllToX数组的构建就是先记录每次2操作的x，从后往前用max遍历一遍即可 然后就是打印结果 max(lastX[i], lastAllToX[last[i]]) 就是结果，即在第i个数的最后一次1操作的x和最后一次1操作后面2操作最大的x中取最大值 （另外这题也可以用线段树写）

代码

#include 
   
    using namespace std;const int maxn = 200100;int last[maxn], lastX[maxn], lastAllToX[maxn];int main(){   	int n, q, op, p, x;	cin >> n;	for(int i = 1; i <= n; i++){   		cin >> lastX[i];	}	cin >> q;	for(int i = 0; i < q; i++){   		cin >> op;		if(op == 1){   			cin >> p >> x;			last[p] = i;			lastX[p] = x;		}		else{   			cin >> x;			lastAllToX[i] = x;		}	}	for(int i = q - 1; i >= 0; i--){   		lastAllToX[i] = max(lastAllToX[i], lastAllToX[i+1]);	}	for(int i = 1; i <= n; i++){   		cout << max(lastX[i], lastAllToX[last[i]]) << " ";	}	cout << endl;}
   

转载地址：http://tvio.baihongyu.com/