DDOSvoid's Blog

2021牛客多校1 J Journey among Railway Stations

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11166/J

Solution

我们考虑 $[l,r]$ 的限制条件，即 $u_l\le v_l,max(u_l+d_l,u_{l+1})\le v_{l+1},max(u_l+d_l+d_{l+1},u_{l+1}+d_{l+1},u_{l+2})\le v_{l+2},\cdots$

我们考虑令 $u’_i=u_i+d_i+d_{i+1}+\cdots+d_{n-1},v’_i=v_i+d_{i}+d_{i+1}+\cdots+d_{n-1}$

那么原来的限制条件不变，然后我们发现这个东西可以拿线段树来维护，线段树每个区间只需要维护 $u$ 的最大值，$v$ 的最小值以及这个区间是否合法

修改都可以用线段树来维护，时间复杂度 $O(n\log n)$

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
#include <iostream>
#include <algorithm>
#define maxn 1000010
#define ll long long
#define INF 100000000000000000
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m;

ll a[maxn];

ll u[maxn], v[maxn];

ll Bit[maxn];
void add(int i, int v) { while (i) Bit[i] += v, i -= lowbit(i); }

ll get_sum(int i) {
    ll s = 0;
    while (i <= n) s += Bit[i], i += lowbit(i);
    return s;
}

#define lc (i << 1)
#define rc (i << 1 | 1) 
struct Seg {
    ll u, v, add;
    bool ok; 
} T[maxn * 4];
inline Seg maintain(const Seg &ls, const Seg &rs) {
    Seg o;
    o.u = max(ls.u, rs.u);
    o.v = min(ls.v, rs.v);
    if (ls.ok && rs.ok && ls.u <= rs.v) o.ok = 1;
    else o.ok = 0;
    o.add = 0; 
    return o;
}

inline void pushdown(int i) {
    ll &add = T[i].add;
    
    T[lc].u += add; T[rc].u += add;
    T[lc].v += add; T[rc].v += add;
    T[lc].add += add; T[rc].add += add;
    
    add = 0; 
}

void build(int i, int l, int r) {
    if (l == r) return T[i] = { u[l], v[l], 0,  1 }, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    T[i].add = 0; 
    T[i] = maintain(T[lc], T[rc]);
}

void update_d(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return T[i].u += v, T[i].v += v, T[i].add += v, void();
    int m = l + r >> 1; pushdown(i);
    update_d(lc, l, m, L, R, v); update_d(rc, m + 1, r, L, R, v);
    T[i] = maintain(T[lc], T[rc]); 
}

void update_uv(int i, int l, int r, int k, ll u, ll v) {
    if (l == r) return T[i] = { u, v, 0, 1 }, void();
    int m = l + r >> 1; pushdown(i); 
    if (k <= m) update_uv(lc, l, m, k, u, v);
    else update_uv(rc, m + 1, r, k, u, v);
    T[i] = maintain(T[lc], T[rc]); 
}

Seg query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return { 0, INF, 0, 1 };
    if (L <= l && r <= R) return T[i];
    int m = l + r >> 1; pushdown(i);
    return maintain(query(lc, l, m, L, R), query(rc, m + 1, r, L, R)); 
}

string ans[] = { "No", "Yes" };
inline void solve_1() {
    int x, y; cin >> x >> y;
    cout << ans[query(1, 1, n, x, y).ok] << "\n";
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    add(x, y - a[x]); 
    update_d(1, 1, n, 1, x, y - a[x]); 
    a[x] = y; 
}

inline void solve_3() {
    int x, u, v; cin >> x >> u >> v;
    update_uv(1, 1, n, x, u + get_sum(x), v + get_sum(x)); 
}

void work() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> u[i];
    for (int i = 1; i <= n; ++i) cin >> v[i];
    for (int i = 1; i <= n; ++i) Bit[i] = 0; 
    for (int i = 1; i < n; ++i) cin >> a[i], add(i, a[i]);
    for (int i = 1; i <= n; ++i) u[i] += get_sum(i), v[i] += get_sum(i);
    build(1, 1, n); cin >> m;
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        switch (opt) {
        case 0 : solve_1(); break;
        case 1 : solve_2(); break;
        case 2 : solve_3(); break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0; 
}