uoj839 龙门题字 题解

题目链接

点击打开链接

题目解法

呜呜呜，我考场上只会 \(60\)，不会优化，没救了

要求字典序最大，不难想到一位一位钦定，那么我们现在的问题是判断 \(ans_1,...,ans_i\) 是否合法，记 \(ok_{i,j}\) 表示第 \(i\) 个修改在第 \(j\) 位是否可行（即 \(x_{i,j}\ge ans_j\)），同时记 \(cnt_i\) 为第 \(i\) 个修改有多少位不可行
考虑修改的过程倒过来，那么可以作为最后一个修改的条件是 \(cnt_{x}=0\)，同理我们往前推，把最后一次修改的位置全部刨去，然后继续找 \(cnt=0\) 的位置（注意是不包含刨去的位置）
这样精细维护可以做到 \(O(nL)\)
具体如何维护？用队列存当前为 \(cnt=0\) 的修改，每次取出队头，把没有刨去的位置刨去，然后看哪些修改的 \(cnt\) 会变成 \(0\)，把 \(cnt\) 变成 \(0\) 的再加入队列，就可以做到 \(O(L)\) 判断

从这个入手，我们发现每次后面只添加了一个元素 \(i\)，前 \([1,...,i-1]\) 是没有变化的
考虑先把 \(r\le i\) 的修改能做的都做完，那么现在必须做包含 \(i\) 的修改了，那么就找一个第 \(i\) 位最大的能选的修改即可
我们需要动态加入 \(r=i\) 的修改，这个可以用前文的队列维护，因为它可能连环导致之前 \(r'<i\) 的修改可行

时间复杂度 \(O(n+L)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb emplace_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=200010;
int n,m,L[N],R[N],deg[N],ans[N];
bool ok[N],tag[N];
vector<int> b[N],vec1[N],vec2[N];
queue<int> Q;
int main(){
    n=read(),m=read();
    L[0]=1,R[0]=n;
    F(i,1,n) b[0].pb(read()),vec1[i].pb(0);
    F(i,1,m){
        L[i]=read(),R[i]=read();
        F(j,L[i],R[i]) b[i].pb(read()),vec1[j].pb(i);
        vec2[R[i]].pb(i);
    }
    F(i,1,n){
        for(int id:vec1[i]) if(!deg[id]) chkmax(ans[i],b[id][i-L[id]]);
        for(int id:vec1[i]) deg[id]+=(b[id][i-L[id]]<ans[i]);
        for(int id:vec2[i]) if(!deg[id]) Q.push(id);
        while(!Q.empty()){
            int id=Q.front();Q.pop();
            tag[id]=true;
            F(j,L[id],R[id]) if(!ok[j]){
                ok[j]=true;
                for(int to:vec1[j]) if(b[to][j-L[to]]<ans[j]){
                    deg[to]--;
                    if(R[to]<=i&&!deg[to]) Q.push(to);
                }
            }
        }
    }
    F(i,1,n) printf("%d ",ans[i]);puts("");
    return 0;
}