南昌定制网站建设,厦门人才网597人才网,简约型网站建设,企业网站 phpcms序列操作 - 题目 - Daimayuan Online Judge
问题描述#xff1a; 思路#xff1a;首先想的是第二次操作的y可以将前面所以操作进行抵消#xff0c;只需要第二次操作的最大值即可。但是发现#xff0c;对于第一个操作#xff0c;它是单点修改#xff0c;每修改一次对于第…序列操作 - 题目 - Daimayuan Online Judge
问题描述 思路首先想的是第二次操作的y可以将前面所以操作进行抵消只需要第二次操作的最大值即可。但是发现对于第一个操作它是单点修改每修改一次对于第二次操作都是有影响的导致不能直接用第二次操作的最大值因为可能在中间的第一次操作中使其大于或小于y。
但是如果将第一次操作的影响去掉就一定可以用最大的第二操作值y来覆盖前面所有。可以知道对于下标i无论第一个操作进行了多少次它的最后结果只跟ma和最后一个y有关。因此可以将操作q离线操作倒叙处理。
如果是第二个操作则更新第二个操作的最大值如果是第一个操作由于只用操作一次第一个操作所以判断是否已经进行过第一次操作如果进行过则跳过否则则将下标i元素赋为max(ma, y)。
具体代码
void solve() {int n,m; cinnm;vectorint a(n 1);for(int i 1; i n; i) cina[i];vectorarrayint,3 ask(m); // opt x yfor(auto t: ask) {cint[0];if(t[0] 1) cint[1]t[2];else cint[1];}int ma -INF;vectorint vis(n 1), ans(n 1);for(int i m-1; i 0; --i) {auto ak ask[i];if(ak[0] 1 !vis[ak[1]]) {vis[ak[1]] 1;ans[ak[1]] max(ma, ak[2]);}if(ak[0] 2) ma max(ma, ak[1]);}for(int i 1; i n; i) if(!vis[i]) ans[i] max(a[i], ma);for(int i 1; i n; i) coutans[i] ;
}
