题解：AT_agc079_b [AGC079B] Range Record

· · 题解

感觉是不是没那么难。

考虑你是怎么算这个前缀最大值个数的，我刚开始想的是建笛卡尔树，然后模拟一个跳跃的过程，然后发现显然合法性只和树的形态有关对吧。

但是这样还是不好刻画，因为一个人需要一直跳祖先直到跳到右边，不妨设这个位置为 nxt_i，也就是 i 后面一个比它大的位置，那么显然这个前缀最大值个数就是从 l 开始一直跳，然后直到跳出 r 的次数，不妨令 p_{n+1}=n+1，这样我们如果连接 (i,nxt_i) 就会形成一棵以 n+1 为根的树。

那么跳跃次数自然而然的想到我们定义第 i 个点的深度为 h_i，那么我们来观察一下目前的区间询问会变成什么样，发现一件非常关键的事情，就是说你跳出区间 [l,r] 的最后一步 x 一定满足 h_x=\min_{i=l}^{r}{h_i}，换句话说，跳跃次数变成了限制：h_l-\min_{i=l}^{r}{h_i}+1=c。

但是显然 h 需要满足一些要求才能构造树，我们观察一下，你怎么造这个树，首先你得有 h_n=1 吧，然后呢，你去找这个笛卡尔树的根，你发现一定是最前面一个满足 h_x=1 的位置 x 为根。然后递归，递归需要满足啥呢，就是右边没要求，左边需要满足 h_{x-1}=h_x+1。显然这个条件等价于 h_{x-1} \leq h_x+1，然后如果满足这个同时 h_n=1 就是合法的了。

然后问题就变成了构造这个 h，你发现 so difficult 啊，无从下手，就是若干个点对之间的约束，同时还需要满足区间最小值严格等于某个数，感觉根本做不了。

考虑调整法，显然 S=\sum_{i=1}^{n}{h_i} \leq \frac{n(n+1)}{2}，我们考虑从 h_i=1 开始往上调整。每次如果至少调整了一个 h，那么 S 至少增加一，所以最多调整 O(n^2) 轮。对于每一轮，我们直接暴力扫所有的限制，如果有一个限制不满足条件，不妨设是 [l,r,c]，分类讨论：

然后每次调整完一个元素，对 i=2 \sim n，依次执行 \max(h_i,h_{i-1}-1) \to h_i。

显然这个做法调整每次一定是正确的，调整到不用调整或者 h_n \geq 2 就结束。

每次求最小值直接 O(n^2) 预处理即可。

复杂度 O(n^4)，超级小常数，跑得飞快。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353,inv2 = (MOD + 1) / 2;
char buf[1<<21],*p1,*p2;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? 0 : *p1++)
template <typename T>
inline void read(T& x){
    x = 0;
    int f = 1;
    char ch = gc();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = gc();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = gc();
    }
    x *= f;
}
template <typename T>
inline void write(T x){
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
int qpow(int a,int b,int P = MOD){
    int res = 1;
    for( ; b; b >>= 1){
        if(b & 1) res = (res * a) % P;
        a = (a * a) % P;
    }
    return res;
}
const int INF = 1e18 + 7;
int T,n,m;
int l[100010],r[100010],c[100010],h[100010];
typedef pair<int,int> pii;
pii f[110][110];
int ans[110],tot = 0;
void solve(int l,int r){
    if(l > r) return;
    if(l == r){
        ans[l] = tot--;
        return;
    }
    int mn = INF;
    for(int i = l; i <= r; i++) mn = min(mn,h[i]);
    for(int i = l; i <= r; i++){
        if(h[i] == mn){
            ans[i] = tot--;
            solve(l,i - 1),solve(i + 1,r);
            return;
        }
    }
}
signed main(){
    read(T);
    while(T--){
        read(n),read(m);
        for(int i = 1; i <= m; i++) read(l[i]),read(r[i]),read(c[i]),c[i]--;
        for(int i = 1; i <= n; i++) h[i] = 1;
        while(1){
            for(int i = 1; i <= n; i++){
                f[i][i] = {h[i],i};
                for(int j = i + 1; j <= n; j++) f[i][j] = min(f[i][j - 1],{h[j],j});
            }
            bool flag = 0;
            for(int i = 1; i <= m; i++){
                if(h[l[i]] < f[l[i]][r[i]].first + c[i]){
                    h[l[i]] = f[l[i]][r[i]].first + c[i],flag = 1;
                    break;
                }
                else if(h[l[i]] > f[l[i]][r[i]].first + c[i]){
                    flag = 1;
                    int p = f[l[i]][r[i]].second;
                    h[p] = h[l[i]] - c[i];
                    break;
                }
            }
            if(!flag) break;
            for(int i = 2; i <= n; i++){
                h[i] = max(h[i],h[i - 1] - 1);
            }
            if(h[n] >= 2) break;
        }
        if(h[n] >= 2){
            puts("No");
            continue;
        }
        for(int i = 1; i <= n; i++){
            f[i][i] = {h[i],i};
            for(int j = i + 1; j <= n; j++) f[i][j] = min(f[i][j - 1],{h[j],j});
        }
        bool flag = 1;
        for(int i = 1; i <= m; i++) flag &= (h[l[i]] == f[l[i]][r[i]].first + c[i]);
        if(!flag){
            puts("No");
            continue;
        }
        puts("Yes");
        tot = n;
        solve(1,n);
        for(int i = 1; i <= n; i++) printf("%lld ",ans[i]);
        printf("\n");
    }
    return 0;
}