Kinetic Tournament

(Updated: )
(9 mins to read)

又是一个凸壳问题现在有n条直线，第i条的斜率为$k_i$​，截距为$b_i$​，当前x坐标的值为$x_i$​，要求支持以下操作1.修改第i条直线的斜率、截距2.让$[l, r]$范围内所有直线的x坐标的值增加delta3.询问$[l, r]$范围内所有直线的y坐标的最大值https://codeforces.com/blog/entry/82094第二个操作必须是增加，不能减少其实就是用普通的线段树来做，如果不带修改，就是一棵胜者树(tournament)，自底向上进行pushup操作，p结点存储的是子树内所有直线中y坐标最大的那条，第一个操作和第三个操作就是普通的线段树了。对于第二个操作，我们在每个结点额外维护一个叫wait的变量，表示如果子树内胜者发生变化，最少要让整个子树的x坐标增加wait，这个东西可以pushup来维护，而区间增加delta，用一个lazytag即可。但是当且仅当当前区间的wait值大于这个增量delta时我们才直接整个子树修改，否则由于胜者会发生变化，所以我们继续递归下去（类似于segment beats，也是用摊还分析(不会)），复杂度大概是$\lt O(n\log^3n) \ or \approx O(n\log^2n)$那么问题来了，这玩意有啥用第一个操作可以当成插入和删除直线，第二个操作相当于修改询问的值，如果询问非增我们可以离线下来，第三个操作就是区间凸壳询问，而且斜率是否单调无关紧要。如果用一般的CHT，要实现区间查询，还要在外面套一个fenwicktree或者是segtree，复杂度上并没有优势，此外这个东西还能支持删除操作，似乎有点用。考虑一个树上的斜率优化，斜率单调我们可以用可回退的队列来维护凸壳，但是有了这个我们直接无脑树剖，管他斜率单不单调。以上纯属猜想，未经实践。。

cf1178 G. The Awesomest Vertex

这个问题相当于上面的支持2和3操作的版本，同时是子树问题（dfs序即可）这边要维护的是$|b_ix + a_ib_i|$的最大值，由于带绝对值，要同时维护最大值和最小值，我们考虑维护$-b_ix - a_ib_i$​的最大值即可。似乎要建两棵线段树，不过这边用一个技巧。我们开一个2*n的线段树，把这两棵树合起来，一颗放在$2i-1$的位置，一颗放在$2i$的位置，然后就可以当成一棵来操作了

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
const ll inf = LLONG_MAX;
int n, q, a[N], b[N];
vector<int> G[N];
int in[N], out[N], num[N], id;
void dfs(int u, int fa)
{
  in[u] = ++id;
  num[id] = u;
  for(auto v : G[u])
  {
    if(v==fa) continue;
    a[v] += a[u]; b[v] += b[u];
    dfs(v, u);
  }
  out[u] = id;
}
struct Line
{
  ll k, b, x;
  ll eval() const { return k*x + b; }
  bool cmp(const Line& oth) const
  {
    ll x1 = eval(), x2 = oth.eval();
    if(x1!=x2) return x1 > x2;
    return k > oth.k;
  }
  ll isect(const Line& oth) { return (eval()-oth.eval())/(oth.k-k) + 1; }
};
struct seg
{
  int l, r;
  Line L;
  ll wait, tag;
}t[N<<3];
void setv(int p, ll add)
{
  t[p].L.x += add;
  t[p].tag += add;
  t[p].wait -= add;
}
void pushup(int p)
{
  auto l1 = t[p<<1].L, l2 = t[p<<1|1].L;
  if(!l1.cmp(l2)) swap(l1, l2);
  t[p].L = l1;
  t[p].wait = min(t[p<<1].wait, t[p<<1|1].wait);
  if(l1.k<l2.k) t[p].wait = min(t[p].wait, l1.isect(l2));
}
void pushdown(int p)
{
  setv(p<<1, t[p].tag), setv(p<<1|1, t[p].tag);
  t[p].tag = 0;
}
void build(int p, int l, int r)
{
  t[p].l = l, t[p].r = r, t[p].wait = 0;
  if(l==r)
  {
    int x = num[(l+1)/2];
    if(l&1) t[p].L = {b[x], 1ll*a[x]*b[x], 0};
    else t[p].L = {-b[x], -1ll*a[x]*b[x], 0};
    t[p].wait = inf;
    return;
  }
  int mid = (l+r)>>1;
  build(p<<1, l, mid); build(p<<1|1, mid+1, r);
  pushup(p);
}
void upd(int p, int x, int y, ll add)
{
  int l = t[p].l, r = t[p].r;
  if(l>=x && r<=y && t[p].wait>add)
  {
    setv(p, add);
    return;
  }
  if(t[p].tag) pushdown(p);
  int mid = (l+r)>>1;
  if(x<=mid) upd(p<<1, x, y, add);
  if(y>mid) upd(p<<1|1, x, y, add);
  pushup(p);
}
ll qry(int p, int x, int y)
{
  int l = t[p].l, r = t[p].r;
  if(l>=x && r<=y) return t[p].L.eval();
  if(t[p].tag) pushdown(p);
  int mid = (l+r)>>1; ll ans = 0;
  if(x<=mid) ans = max(ans, qry(p<<1, x, y));
  if(y>mid) ans = max(ans, qry(p<<1|1, x, y));
  return ans;
}
int main()
{
  scanf("%d%d", &n, &q);
  for(int i=2; i<=n; i++)
  {
    int fa; scanf("%d", &fa);
    G[fa].push_back(i);
  }
  for(int i=1; i<=n; i++) scanf("%d", a+i);
  for(int i=1; i<=n; i++) scanf("%d", b+i);
  dfs(1, 0);
  build(1, 1, 2*n);
  while(q--)
  {
    int op, v;
    scanf("%d%d", &op, &v);
    if(op==1)
    {
      ll x; scanf("%lld", &x);
      upd(1, in[v]*2-1, out[v]*2, x);
    }
    else printf("%lld\n", qry(1, in[v]*2-1, out[v]*2));
  }
  return 0;
}