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

Description

Solution

显然对于每个方格上的数字都可能被多次覆盖，但是真正起作用的是最后一次覆盖的时候。
考虑一个问题：如果我知道某个点最后一次覆盖是第几次操作，那么意味着我知道最后一次覆盖的方阵初始点与边长，能不能推算当前点的值呢?
显然是可以的——这个自己手推一下吧, 应该几分钟就能推出来了。具体想法是以两行作为一个周期，相差奇数行就特殊处理一下(因为方向是反过来的)。
那么我们只需要每次操作的时候对于被操作的区域进行标记，如果当前已被标记就重新覆盖，最后查询该点的标记，通过标记使用上述的方法得到最终值即可。考虑到 , 不能暴力打标记。选择开2000个线段树，使用线段树的 实现 的区间赋值，最后每次 查询当前点的值，总体时间复杂度 。但线段树有点卡常(我的代码 )，而且比较玄学，个人觉得这题时间应该放得再宽一些。

Code

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10, M = 1e7 + 10, mod = 1e9 + 7;

struct node {
  struct point {
    int l, r, lazy;
  } t[2005 << 2];
  void push_down(int rt) {
    if (t[rt].lazy) {
      t[rt << 1].lazy = t[rt].lazy;
      t[rt << 1 | 1].lazy = t[rt].lazy;
      t[rt].lazy = 0;
    }
  }
  void build(int rt, int l, int r) {
    t[rt].l = l, t[rt].r = r;
    t[rt].lazy = 0;
    if (l == r) {
      return ;
    }
    int mid = t[rt].l + t[rt].r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
  }
  void update(int rt, int ql, int qr, int val) {
    if (ql <= t[rt].l && qr >= t[rt].r) {
      t[rt].lazy = val;
      return ;
    }
    int mid = t[rt].l + t[rt].r >> 1;
    push_down(rt);
    if (ql > mid) {
      update(rt << 1 | 1, ql, qr, val);
    } else if (qr <= mid) {
      update(rt << 1, ql, qr, val);
    } else {
      update(rt << 1, ql, mid, val);
      update(rt << 1 | 1, mid + 1, qr, val);
    }
  }
  int query(int rt, int ql) {
    if (t[rt].l == t[rt].r) {
      return t[rt].lazy;
    }
    push_down(rt);
    int mid = t[rt].l + t[rt].r >> 1;
    if (ql <= mid) {
      return query(rt << 1, ql);
    } else {
      return query(rt << 1 | 1, ql);
    }
  }
}tree[2005];

struct Query {
  int x, y, k;
}Q[3005];

int cal(int n, int x, int y, int k, int i, int j) {
  int tmpx = i - x;
  int res = 1 + tmpx * k;
  if (tmpx & 1) {
    res += (y + k - 1 - j);
  } else {
    res += (j - y);
  }
  return res;
}

void solve() {
  int n, m; scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    tree[i].build(1, 1, n);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d %d %d", &Q[i].x, &Q[i].y, &Q[i].k);
    for (int j = Q[i].x; j <= Q[i].x + Q[i].k - 1; j++) {
      tree[j].update(1, Q[i].y, Q[i].y + Q[i].k - 1, i);
    }
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int now = tree[i].query(1, j);
      if (!now) {
        printf("0 ");
      } else {
        int x = Q[now].x, y = Q[now].y, k = Q[now].k;
        printf("%d ", cal(n, x, y, k, i, j)); 
      }
    }
    puts("");
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int T = 1; //cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}