1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vi tem;
    rep(i, 1, n - 1) tem.push_back(abs(a[i]));
    ranges::sort(tem);
    int tem2 = ranges::lower_bound(tem, abs(a[0])) - tem.begin();
    cout << (tem2 <= n / 2 ? "YES" : "NO") << endl;
    return;
}

 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

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
void solve() {
    int n;
    cin >> n;
    vvi ma(n, vi(n, -1));
    int l, r;
    if (n % 2 == 1)
        l = r = n / 2;
    else
        l = r = n / 2 - 1;
    ma[l][r] = 0;
    int val = 1;
    int tem = 1;
    while (val < n * n) {
        rep(i, 0, 3) {
            rep(j, 1, tem) {
                l += dx[i], r += dy[i];
                if (l >= 0 && l <= n - 1 && r >= 0 && r <= n - 1 && ma[l][r] == -1) ma[l][r] = val++;
                if (val >= n * n) break;
            }
            if (val >= n * n) break;
            if (i % 2 == 1) tem++;
        }
    }
    rep(i, 0, n - 1) {
        rep(j, 0, n - 1) { cout << ma[i][j] << ' '; }
        cout << endl;
    }
    return;
}

  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

template <typename T = long long>
class Tree {
    vector<T> tree;

public:
    // 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
    Tree(int n, T val = 0) : tree(n + 1) {
        for (int i = 1; i <= n; i++) {
            tree[i] += val;
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
    Tree(const vector<T>& data) {
        int n = data.size();
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            tree[i] += data[i - 1];  // data是 0-based
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 单点修改：将 0-based 下标 i 处的元素增加 val
    void add(int i, T val = 1) {
        for (++i; i < tree.size(); i += i & (-i)) {
            tree[i] += val;
        }
    }

    // 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
    T pre(int i) const {
        T res = 0;
        for (++i; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
    T query(int l, int r) const {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);  // 当 l=0 时, pre(-1) 会合理地返回 0
    }

    // 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
    int lower_bound(T val) const {
        int w = bit_width(tree.size() - 1);
        int res = 0;
        T s = 0;
        for (int i = w - 1; i >= 0; i--) {
            int nxt = res + (1 << i);
            if (nxt < tree.size() && tree[nxt] + s < val) {
                res += (1 << i);
                s += tree[nxt];
            }
        }
        return res;  // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
    }
};
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vi tem;
    vi tem2;
    rep(i, 0, n - 1) {
        if (i % 2 == 0)
            tem.push_back(a[i]);
        else
            tem2.push_back(a[i]);
    }
    ll tot = 0, tot2 = 0;
    int m1 = sz(tem), m2 = sz(tem2);
    int cnt = 0, cnt2 = 0;
    Tree tree1(2 * n), tree2(2 * n);
    auto sorted1 = tem, sorted2 = tem2;
    frep(i, m1 - 1, 0) {
        ll tem3 = tree1.query(0, tem[i] - 1);
        tot += tem3;
        tree1.add(tem[i], 1);
    }
    frep(i, m2 - 1, 0) {
        ll tem4 = tree2.query(0, tem2[i] - 1);
        tot2 += tem4;
        tree2.add(tem2[i], 1);
    }
    if (tot % 2 == tot2 % 2) {
        ranges::sort(tem);
        ranges::sort(tem2);
        rep(i, 0, n - 1) {
            if (i % 2 == 0)
                a[i] = tem[cnt++];
            else
                a[i] = tem2[cnt2++];
        }
    } else {
        ranges::sort(tem);
        ranges::sort(tem2);
        rep(i, 0, n - 1) {
            if (i % 2 == 0)
                a[i] = tem[cnt++];
            else
                a[i] = tem2[cnt2++];
        }
        swap(a[n - 1], a[n - 3]);
    }
    rep(i, 0, n - 1) cout << a[i] << ' ';
    cout << endl;
    return;
}

 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

void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl pre(n);
    vl suf(n + 1);
    set<int> s;
    rep(i, 1, n) s.insert(i);
    int cnt = 0;
    rep(i, 0, n - 1) {
        auto it = s.upper_bound(a[i]);
        if (it != s.begin()) {
            it--;
            s.erase(s.find(*it));
            cnt++;
        }
        pre[i] = cnt;
    }
    s.clear();
    cnt = 0;
    rep(i, 1, n) s.insert(i);
    frep(i, n - 1, 0) {
        auto it = s.upper_bound(a[i]);
        if (it != s.begin()) {
            it--;
            s.erase(s.find(*it));
            cnt++;
        }
        suf[i] = cnt;
    }
    ll ans = 0;
    rep(i, 0, n - 1) ans += min(pre[i], suf[i + 1]);
    cout << ans << endl;
    return;
}

  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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

struct Info {
    ll x;
    Info(ll x = -2) : x(x) {}
};
Info operator+(const Info& a, const Info& b) {
    Info c;
    c.x = max(a.x, b.x);
    return c;
}
template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return a + b; }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node].val < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    }
    // 若固定左端点，需要记录前缀分段最大值，并加被待求区间完全覆盖的剪枝

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node].val < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    // 传入一个数组维护
    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    // 查询[ql,qr]中第一个满足条件的下标
    int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); }

    // 查询[ql,qr]中最后一个满足条件的下标
    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }
};
class LazySegmentTree {
private:
    struct Node {
        int l, r;
        int min_cover_len = 0;  // 区间内被覆盖的最小次数
        int min_cover = 0;      // 区间内为最小次数的区间长度
        int todo = 0;           // 懒标记
    };

    vector<Node> seg;

    void maintain(int o) {
        Node& lo = seg[o << 1];
        Node& ro = seg[(o << 1) | 1];
        int mn = min(lo.min_cover, ro.min_cover);
        seg[o].min_cover = mn;
        seg[o].min_cover_len = (lo.min_cover == mn ? lo.min_cover_len : 0) + (ro.min_cover == mn ? ro.min_cover_len : 0);
    }  // 根据左右儿子的信息，更新当前节点的信息

    void do_(int o, int v) {
        seg[o].min_cover += v;
        seg[o].todo += v;
    }  // 仅更新节点信息，不下传懒标记

    void pushdown(int o) {
        int& v = seg[o].todo;
        if (v) {
            do_(o << 1, v);
            do_(o << 1 | 1, v);
            v = 0;
        }
    }  // 下传懒标记

    void build(vi& xs, int o, int l, int r) {
        seg[o].l = l;
        seg[o].r = r;
        if (l == r) {
            seg[o].min_cover_len = xs[l + 1] - xs[l];
            return;
        }
        int m = (l + r) >> 1;
        build(xs, o << 1, l, m);
        build(xs, o << 1 | 1, m + 1, r);
        maintain(o);
        return;
    }

    void update(int o, int l, int r, int v) {
        if (l <= seg[o].l && seg[o].r <= r) {
            do_(o, v);
            return;
        }
        pushdown(o);
        int m = (seg[o].l + seg[o].r) >> 1;
        if (l <= m) update(o << 1, l, r, v);
        if (m < r) update(o << 1 | 1, l, r, v);
        maintain(o);
    }

public:
    LazySegmentTree(vi& xs) {
        unsigned n = sz(xs) - 1;  // 有这么多个差值
        seg.resize(2 << bit_width(n - 1));
        build(xs, 1, 0, n - 1);  // 根节点是1
    }

    void update(int l, int r, int v) { update(1, l, r, v); }

    int get_uncovered_length() { return seg[1].min_cover ? 0 : seg[1].min_cover_len; }
};
void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    SegmentTree<Info> tree(n + 1, Info(-1));
    vl l(n);
    vl r(n);
    rep(i, 1, n - 1) {
        l[i] = l[i - 1];
        if (i >= 2) tree.update(a[i - 2], Info(i - 2));
        int tem = min(a[i], a[i - 1]) + 1;
        int tem2 = max(a[i], a[i - 1]) - 1;
        if (tem > tem2) continue;
        int tem3 = tree.query(tem, tem2).x;
        l[i] = max(1LL * tem3 + 1, l[i]);
    }
    SegmentTree<Info> tree2(n + 1, Info(-INT_MAX));
    r[n - 1] = n - 1;
    frep(i, n - 2, 0) {
        r[i] = r[i + 1];
        if (i <= n - 3) tree2.update(a[i + 2], Info(-(i + 2)));
        int tem = min(a[i], a[i + 1]) + 1;
        int tem2 = max(a[i], a[i + 1]) - 1;
        if (tem > tem2) continue;
        int tem3 = -tree2.query(tem, tem2).x;
        r[i] = min(1LL * tem3 - 1, r[i]);
    }
    struct Event {
        int y, lx, rx, d;
    };
    vector<Event> events;
    vi xs;
    rep(i, 0, n - 1) {
        xs.push_back(l[i]);
        xs.push_back(i + 1);
        events.emplace_back(i, l[i], i + 1, 1);
        events.emplace_back(r[i] + 1, l[i], i + 1, -1);
    }
    ranges::sort(xs);
    xs.erase(unique(all(xs)), xs.end());
    sort(all(events), [&](const Event& a, const Event& b) { return a.y < b.y; });
    LazySegmentTree tree3(xs);
    ll ans = 0;
    rep(i, 0, sz(events) - 2) {
        auto [y, lx, rx, d] = events[i];
        int L = ranges::lower_bound(xs, lx) - xs.begin();
        int R = ranges::lower_bound(xs, rx) - xs.begin() - 1;
        tree3.update(L, R, d);
        int height = events[i + 1].y - y;
        int width = xs.back() - xs[0] - tree3.get_uncovered_length();
        ans += 1LL * height * width;
    }
    cout << ans << endl;
    return;
}