2021牛客寒假算法基础集训营4 G. 九峰与蛇形填数

发表于 分类于

链接

https://ac.nowcoder.com/acm/contest/9984/G

题意

一个$n*n$ 的初始全零的矩阵，按如下方法填数：

1 2 3

6 5 3

7 8 9

但是这样子太过简单，所以每一次操作会选择一个子矩阵，请你在其子矩阵上进行填数，并在最后输出整个矩阵。

思路

对行建立 $n$ 棵线段树，维护操作编号。

从最后一个操作开始倒序修改，在区间修改时如果碰到节点已经有权值了就不用向下更新了，因为后面的操作会覆盖前面的操作。

$m$ 个修改完成后，对每颗线段树从根节点向下 push，每个节点权值取该节点与祖先节点的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=2e3+5;
const int M=3e3+5;
int n,m,x[M],y[M],k[M],a[N],ls[N<<2],rs[N<<2],w[N][N<<2];
void build(int p,int l,int r) {
    ls[p]=l,rs[p]=r;
    if(l==r) {a[l]=p;return;}
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void pushdown(int p,int pre,int id) {
    w[id][p]=max(pre,w[id][p]);
    if(ls[p]==rs[p]) return;
    pushdown(p<<1,w[id][p],id);
    pushdown(p<<1|1,w[id][p],id);
}
void update(int p,int l,int r,int v,int id) {
    if(ls[p]>=l&&rs[p]<=r) {
        if(!w[id][p]) w[id][p]=v;
        return;
    }
    int mid=ls[p]+rs[p]>>1;
    if(l<=mid&&!w[id][p<<1]) update(p<<1,l,r,v,id);
    if(r>mid&&!w[id][p<<1|1]) update(p<<1|1,l,r,v,id);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>x[i]>>y[i]>>k[i];
    build(1,1,n);
    for(int i=m;i>=1;i--)
        for(int j=0;j<k[i];j++)
            update(1,y[i],y[i]+k[i]-1,i,x[i]+j);
    for(int i=1;i<=n;i++) pushdown(1,0,i);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            int t=w[i][a[j]];
            if(!t) cout<<0<<" \n"[j==n];
            else {
                int r=i-x[t]+1,c=j-y[t]+1;
                cout<<(r&1?(r-1)*k[t]+c:(r-1)*k[t]+k[t]-c+1)<<" \n"[j==n];
            }
        }
    }
    return 0;
}