CF 576 div2 D-白红宇

CF 576 div2 D

阅读量：4493 次

发布时间：2019-06-08

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

传送门：

题意：给一序列，给一串操作，按顺序修改序列内容，分两种类型

类型一：1 p x ，位置p的数字改为x

类型二：2 x，序列中所有小于x的数字全改为x

刚开始想着直接线段树，单点修改和区间修改，头脑风暴了一会儿，觉着lazy标记改动容易出错，果断弃了

嘻嘻，心态放好先

开始草稿纸上乱画分析（瞎搞

对于type 2，最后改的肯定是x的最大值，一直取max就好啦

难搞的是type 1，每次改动都得看后续的type 2有没有对x有影响，就不能单纯标记了

emmmm 等等，既然只有后续的type 2对type 1有影响，而且也只有最大值会被保留，那从后往前找每个位置到末尾的最大值就好啦

一个后缀最大值数组就解决了

然后就是一些细节了，后缀最大值数组是对操作进行的，并非原序列下标，需另开个数组记录好对应关系

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;typedef pair
                  
                    P;typedef long double ld;#define mem(x) memset(x, 0, sizeof(x))#define me(x) memset(x, -1, sizeof(x))#define fo(i,n) for(i=0; i
                   
                    mp;ll v[N], mx[N], id[N];int main(){ ll i, j, k, l=1; ll n, m, t; ll x, y; sc(n); for(i=1; i<=n; i++) sc(a[i]); sc(m); ll ans=0; while(m--) { sc(k); if(k==1) sca(x,y), v[l++]=-1, id[x]=l-1, mp[x]=y+1; else sc(x), v[l++]=x, ans=max(ans,x); } l--; for(i=l; i>=1; i--) mx[i]=max(mx[i+1],v[i]); for(i=1; i<=n; i++) if(!mp[i]) pri(max(ans,a[i])); else pri(max(mp[i]-1,mx[id[i]])); printf("\n"); return 0;}