Educational Codeforces Round 124

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
F(线段树,持久化线段树,区间维护)

CF tracker

Edu List

https://codeforces.com/contest/1651

F. Tower Defense

塔防游戏, i位置上 塔 能量上限c[i] 每秒充能r[i], 初始满能量

一关卡 生成 q 个怪, 第j个怪, 在point 1位置, tj时刻, 生成, 血量hj, 移动速度1格子/s

当怪经过 塔时, 塔对它 造成 min(怪血量,塔能量) 的伤害, 并且消耗同样多能量

但是还是会有的怪 活着经过所有塔

求 或者的怪的血量和

范围

n 2e5

ci,ri [1,1e9]

q 2e5

tj [0,2e5] 保证严格单调递增

hj [1,1e12]

我的思路

假设 每个怪都不死, 而且每个塔充能无上限

那么除了第一个怪, 第i个怪 受到的伤害 = (i与i-1的时间差) * (sum r)

但似乎没有什么帮助

再看 既然 伤害唯一来源是塔, 那么 伤害 + 剩余血量 = 总血量

如果能计算出塔实际造成的伤害, 那么 剩余血量也可以算出

第一个塔

min(c[1],h[1]): c[1] -> c[1] - min(c[1],h[1]) = p[1]

min(c[1],p[1]+r[1](t[2]-t[1]),h[2])

.. 感觉就是关联很紧, 如何消除这种 强关联

第一个 假设在 塔i倒下 或 塔j倒下, 有啥不同

i倒下, 说明i-1都是完全能量, j 倒下,说明j-1塔都是完全能量, min(i,j) -1 都是完全能量

所以看起来需要一个前缀能量和

而第二个 如果 在 p2 倒下, 第一个在p1 倒下

那么 如果哦 p2 < p1 对于 前 p2-1 对 第二个造成的伤害 就是 = sum min((t[2]-t[1])r[i],c[i])

一个与t,i 相关的 函数, 对于给定t, 随i严格单调递增, 但是问题是 难以?快速求点值, 不然可以二分

另一个问题, 如果 p2 > p1, 那么超出的部分还要和 更前面的相关

想拆一个单独x, 或者调整血量, 似乎都没啥能和原题方案一致的办法

感觉很卡在一个 无法快速计算一轮的结果

换个视角, 不按怪来看, 按塔来看

第一个塔接受的是 (t0,h0) (t1,h1) …

输出的内容被第塔接受, 而可以通过时间偏移让时间不变 (t0,h0_1) (t1,h1_1) (t2,h2_1)...

那么问题变成

有一堆点 (t0,h0) (t1, h1)

依次 n个操作 (ri,ci), 对每个点的高度进行修改, 问最后的高度和

看起来 每个h变化在允许小于0时, 下降要么是 ci, 要么是间隔 * ri ?

但实际上并不是, 可能是击倒了上一个 有残余

但是每个单位最多被击倒一次!

n次 残余情况, 剩下的都是 ci, 间隔 * ri

如果 h > ci 一定不被击倒, 如果 h < min(间隔 * ri, ci), 一定被击倒

还剩 间隔 * ri < h < ci 的情况

感觉上需要 实现一定的区间操作, 而且可能需要先排序什么的?

题解

先考虑简单的情况

如果 塔始终都是满能量, 那么能量前缀和ci, 二分找血量就行

如果 前一秒 塔都是空的, 同样是 前缀和ri

What if we drop the condition about the towers not being fully restored? 有什么数据结构能回答前缀和, 需要记录已经满的ci的和, 和没有满 的 塔的ri和(? 下一秒会超过满呢?) 然后给时间变化, 做乘法即可

通过计算每个塔到满需要的时间 $\lceil \frac{c}{r} \rceil$, 来判断哪些塔到满

不幸的是, 实际问题, 并不是所有的会同时 空, 但可以归约成这样, 记录区间同时变空, 但有一个位置会 不完全的drain, 不过长度为1

当一个怪来了, 耗尽一个前缀, 然后1个 部分, 每个怪 创建O(1)条区间, 删除不超过前面创造的区间

O(q * 单个区间操作代价)

如何做区间查询

给一个 经过的时间, 如果知道上一次的查询, 会相对简单. 初始线段树 所有塔都是满能量. 然后做两种操作, 塔with restore time ⌈c/r⌉ 和 一个时间t的query. 按照 降序 排序, 然后逐个处理. 当一个 塔事件发生, 在线段树中单点更新, 从capacity 变为regeneration rate. 当查询发生 计算和

但是查询不能提前知道, 需要持久化 和 版本, 如果一个段在t[lst] 耗尽, 查询时间为t , 那么需要查询 t-t[lst] 版本的树

你不需要存所有版本的树, 只需要 有tower更新的, 然后你需要查询 lower_bound, sort ⌈c/r⌉ 来查版本号

从维护角度讲, 就是下面两种线段, 每次增加 常数个, O(总删除) <= O(总增加)

1
[ 下标区间,t时刻耗尽] [ 单点下标, 上次时刻, 上次能量]

对于 单点的处理, 就暴力

对于区间, 就是在询问 耗尽的区间, 经过t时刻, 后遇到血量h的会怎样, 而它会变成 [耗尽][单点][处理前的状态]

这里一点就是处理前的状态只用切割[l,r] 而不用更新内部的高度, 因为其内部的具体值对于当前询问没有用处

那么 这个问题就是 问 [l..r] 中 充满 <= t的 r的和sumr, 和 充满耗时 > t的 c的和sumc

sumc + sumr * t, 就是这段区间 能造成的最大伤害

这个就是可持久化线段树的活了,

一个根 标签为 T 的线段树 表示 时间 (T..] 的sumr, 和[0..T] 的sumc

代码

https://codeforces.com/contest/1651/submission/189765546

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

ll read(){ll r;scanf("%lld",&r);return r;}

int nidx=0;
struct node{ // 下标是塔的位置
  node *l, *r; // 持久化的左右节点
  ll sumc, sumr; // c满容量的容量和, r非满容量的增速和
  node() : l(NULL), r(NULL), sumc(0), sumr(0) {}
  node(node* l, node* r, ll sumc, ll sumr) : l(l), r(r), sumc(sumc), sumr(sumr) {}
} nodelist[(19+4)*200000+10]; // (log(2e5)+2)*2e5

node *newnode(node*l,node*r,ll sumc,ll sumr){
  nodelist[nidx]={l,r,sumc,sumr};
  return &nodelist[nidx++];
}

node * up(node *o){
  o->sumc = o->l->sumc + o->r->sumc;
  o->sumr = o->l->sumr + o->r->sumr;
  return o;
}

node* build(int l, int r, vector<int> &c){ // [l,r)
  if (l == r - 1) return newnode(NULL, NULL, c[l], 0);
  int m = (l + r) / 2;
  node* nw = newnode(
      build(l, m, c),
      build(m, r, c),
      0,0);
  return up(nw);
}

node* upd(node* v, int l, int r, int pos, int val){ // [l,r) [pos] = val
  if (l == r - 1) return newnode(NULL, NULL, 0, val); // 在 pos 未满时的增量
  int m = (l + r) / 2;
  node* nw = newnode(v->l, v->r, 0, 0);
  if (pos < m) nw->l = upd(v->l, l, m, pos, val);
  else         nw->r = upd(v->r, m, r, pos, val);
  return up(nw);
}

ll getsum(node *v, int dt){ return v->sumc + v->sumr * dt; } // 区间 可以造成的最高伤害

// 耗尽的区间[ql,qr) 经过时间dt后 攻击血量h 的耗尽个数
int trav(node *v, int l, int r, int ql, int qr, ll &h, int dt){
  if (ql <= l and r <= qr and h - getsum(v, dt) >= 0){
    h -= getsum(v, dt);
    return r - l; // 耗尽区间长度
  }
  if (l == r - 1) return 0; // 叶子
  int m = (l + r) / 2;
  int cnt = ql<=m?trav(v->l, l, m, ql, qr, h, dt):0;
  if(cnt == max(0, min(m, qr) - max(ql,l))) // h 不一定为0, 如果最后一个位置没有完全消耗h, 则会保留剩余的h, 整个递归只处理 完全消耗的区间, 不关心有残余的
    cnt +=  qr> m?trav(v->r, m, r, ql, qr, h, dt):0; // 有血量剩余说明 左侧区间全部耗尽
  return cnt;
}

struct seg{ int l, r, lst, cur; };

int main() {
  int n=read();
  vector<int> c(n), R(n); // 1e9
  rep(i, 0, n) {
    c[i]=read();
    R[i]=read();
  }

  vector<int> ord(n); // index, dec order 从空充满的时间
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int x, int y){ return c[x] / R[x] > c[y] / R[y]; });

  vector<int> vals;
  for (int i : ord) vals.push_back(c[i] / R[i]);

  // vector<int> vals; // 充满时间
  // per(i,0,size(ord)) vals.push_back(c[ord[i]]/R[ord[i]]);

  vector<node*> root = {build(0, n, c)}; // root[时间序号t idx]=线段树的根,记录更大>=t点的sum r, < t的点的sum c
  for (int i : ord) root.push_back(upd(root.back(), 0, n, i, R[i]));

  vector<seg> st;
  per(i,0,n) st.push_back({i, i + 1, 0, c[i]}); // [l,r) 上次时间lst, 当前充能cur, 倒序插入

  ll ans = 0;
  int q=read();
  while(q--){
    int t=read();
    ll h=read();
    while (!st.empty()){
      auto [l,r,lst,cur] = st.back(); // 上一次
      st.pop_back();
      ll dt=t-lst;
      if (r - l == 1){ // 单点
        cur = min((ll)c[l], cur + dt*R[l]);
        if (cur <= h){ // 消耗塔
          h -= cur;
        } else { // dead
          st.push_back({l, r, t, int(cur - h)});
          h = 0;
        }
      } else { // 一定是从空开始的
               // int mx = end(vals)-lower_bound(vals.begin(),vals.end(),dt); // >= 时间间隔的个数
        int mx = vals.rend() - lower_bound(vals.rbegin(), vals.rend(), t - lst);
        int res = l + trav(root[mx], 0, n, l, r, h, dt); // [l,r) 区间, 血量h(传引用会修改,变为残余血量), 间隔时间
        assert(res <= r);
        if (res != r){ // [l...res) 消耗完 [res] 单点, [res+1..r) 保持原来的
          if (r - res > 1) st.push_back({res + 1, r, lst, 0}); // 截断剩余的
          int nw = min((ll)c[res], R[res] * dt);
          assert(nw - h > 0);
          st.push_back({res, res + 1, t, int(nw - h)});
          h = 0;
        } // else res == r 整段被消耗完(因为是左开右闭)
      }
      if (h == 0) break;
    }
    if (st.empty()){ // 所有防御塔消耗完, t时刻全部耗尽
      st.push_back({0, n, t, 0});
    } else if (st.back().l != 0){ // [0,st.back().l) 在t时刻消耗完
      st.push_back({0, st.back().l, t, 0});
    }
    ans += h;
  }

  printf("%lld\n", ans);
  return 0;
}

总结

算了 div2 别看评分了, 各种虚高

F

感觉一个是区间表示, 这样保证区间个数是O(n+q)的, 都发现每次是 耗尽一段加一个部分消耗的点, 没有往这个方向思考真的很不应该

另一个就是 并不需要转换到中间区间的状态! 只有满和空, 我总在想, 会有 连续的一段空了以后, 因为容量和充能速度不同, 导致 出现一段满一段未满的情况, 而题解教我, 这部需要关心, 因为发生这种情况, 也就是说明 这段经过了时间以后, 并没有被使用

那么从表示上, 用它被清空的时刻就可以表示了, 去更新状态 并没有任何需要, 反而更复杂, 相当于 区间[l,r] 在t时刻被清空后就没有再次操作了, 并不需要在t1一个未操作时刻更新 具体信息

第一次见持久化线段树, 看起来好像也就那样, 这题里 初始建立好了 就静态了, 只是查询, 建立时就是两个状态之间的修改单点 引起的节点变化就是 log个

参考

官方