G - Welfare State(逻辑思维题+相当有难度)

G - Welfare State(逻辑思维题+相当有难度)
G - Welfare State(逻辑思维题+相当有难度)
这道题很有意思;我只能佩服那些大佬的思维能力了QAQ;
题意:如果是1操作,就改点;如果是2操作就是在整个数组里面改小于x的值成为x;我一看,枚举。。。。。再一看,爆表QAQ;
但是我看了大佬的解题思路感觉很是NB,他们能把操作的逻辑给控制住,只要仔细想一下就可以知道这个:
对于一个数,它的最终的值为max(当前修改的值,在这次修改之后的值);这里就需要一个很巧妙的控制操作逻辑了,因为一个数,它只和它当前的操作和后面的操作有关;所以可以利用对操作次数for循环+记录下标+回跑;
AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
ll a[maxn],post[maxn],modify[maxn];
	ll n;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	ll Q,op,p,x;
	scanf("%lld",&Q);
	for(int i=1;i<=Q;i++){//这里利用操作数来for
		   scanf("%lld",&op);
		   if(op==1){
		   	scanf("%lld %lld",&p,&x);
		   	a[p]=x;//改变这一点的值为x
		   	post[p]=i;//表明这个p点是第几次修改的 //post[i]=i和modify就很好的对应了操作逻辑顺序
		   }else{
		   	  scanf("%lld",&modify[i]);//这里这里表示整个区间在第i次操作时需要改变的值
		   }
	}
	modify[Q+1]=-1;
	for(int i=Q;i>=1;i--){
		modify[i]=max(modify[i],modify[i+1]);//因为操作只与后面的最大值有关(如果后面的不是当前的最大值也可以讨论出来)
	}
	for(int i=1;i<=n;i++){
		  printf("%lld%c",max(a[i],modify[post[i]+1]),i==n?'\n':' ');//输出这个点对于的操作的下一个操作所需要改的值和a[i]的大小比较
	}
	return 0;
}
上一篇:【JZOJ5431】序列操作


下一篇:Warning: Cannot modify header information - headers already sent by