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

const ll MOD = 676767677;
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    int ans = 0;
    rep(i, 0, n - 2) {
        if (max(a[i], a[i + 1]) - min(a[i], a[i + 1]) == __gcd(a[i], a[i + 1])) ans++;
    }
    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

void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    sort(all2(a));
    int idx = 0;
    int l = 0, r = n, mid;
    int ans = 0;
    auto check = [&](int mid) -> bool {
        multiset<int> s;
        rep(i, 0, n - 1) s.insert(a[i]);
        frep(i, mid - 1, 0) {
            if (s.count(i)) {
                s.erase(s.find(i));
            } else {
                auto x = s.lower_bound(2 * i + 1);
                if (x == s.end())
                    return false;
                else
                    s.erase(x);
            }
        }
        return true;
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 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

void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl tem1;
    vl tem2;
    rep(i, 0, n - 1) {
        if (a[i] % 2 == 1)
            tem1.push_back(a[i]);
        else
            tem2.push_back(a[i]);
    }
    if (tem1.empty() || tem2.empty()) {
        bool flag = true;
        rep(i, 0, n - 2) {
            if (a[i] > a[i + 1]) {
                flag = false;
                break;
            }
        }
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        return;
    }
    int maxx1 = *max_element(all(tem1));
    int mixx1 = *min_element(all(tem1));
    int maxx2 = *max_element(all(tem2));
    int mixx2 = *min_element(all(tem2));
    multiset<int> s1;
    multiset<int> s2;
    rep(i, 0, n - 1) {
        if (a[i] % 2 == 1) s2.insert(a[i]);
    }
    rep(i, 0, n - 1) {
        if (a[i] % 2 == 0 || s2.empty()) continue;
        if (!s1.empty()) {
            int tem = *prev(s1.end());
            int tem2 = *s2.begin();
            if (tem > maxx2 && tem2 < mixx2) {
                cout << "NO" << endl;
                return;
            }
        }
        s1.insert(a[i]);
        s2.erase(s2.find(a[i]));
    }
    s1.clear();
    s2.clear();
    rep(i, 0, n - 1) {
        if (a[i] % 2 == 0) s2.insert(a[i]);
    }
    rep(i, 0, n - 1) {
        if (a[i] % 2 == 1 || s2.empty()) continue;
        if (!s1.empty()) {
            int tem = *prev(s1.end());
            int tem2 = *s2.begin();
            if (tem > maxx1 && tem2 < mixx1) {
                cout << "NO" << endl;
                return;
            }
        }
        s1.insert(a[i]);
        s2.erase(s2.find(a[i]));
    }
    cout << "YES" << 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

template <typename T, typename F>
class LazySegmentTree {
    const F TODO_INIT = 0;  // 懒标记初始值
    struct Node {
        T val;
        F todo;
    };
    int n;
    vector<Node> tree;
    T merge_val(const T& a, const T& b) const { return max(a, b); }  // 合并两个val
    F merge_todo(const F& a, const F& b) const { return a + b; }     // 合并两个懒标记
    void apply(int node, int l, int r, F todo) {
        Node& cur = tree[node];
        cur.val += todo;
        cur.todo = merge_todo(todo, cur.todo);
    }  // 把懒标记作用到node子树
    void pushdown(int node, int l, int r) {
        Node& cur = tree[node];
        F todo = cur.todo;
        if (todo == TODO_INIT) return;
        int m = (l + r) >> 1;
        apply(node << 1, l, m, todo);
        apply(node << 1 | 1, m + 1, r, todo);
        cur.todo = TODO_INIT;
    }  // 把当前节点的懒标记下传
    void maintain(int node) { tree[node].val = merge_val(tree[node << 1].val, tree[node << 1 | 1].val); }
    // 合并线段树
    void build(const vector<T>& a, int node, int l, int r) {
        Node& cur = tree[node];
        cur.todo = TODO_INIT;
        if (l == r) {
            cur.val = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(a, node << 1, l, m);
        build(a, node << 1 | 1, m + 1, r);
        maintain(node);
    }  // 建树，复杂度O(n)
    void update(int node, int l, int r, int ql, int qr, F f) {
        if (qr < ql) return;
        if (ql <= l && r <= qr) {
            apply(node, l, r, f);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (ql <= m) update(node << 1, l, m, ql, qr, f);
        if (qr > m) update(node << 1 | 1, m + 1, r, ql, qr, f);
        maintain(node);
    }  // 区间更新[ql,qr]
    T query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[node].val;
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (qr <= m) return query(node << 1, l, m, ql, qr);
        if (ql > m) return query(node << 1 | 1, m + 1, r, ql, qr);
        T l_res = query(node << 1, l, m, ql, qr);
        T r_res = query(node << 1 | 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 区间查找
    int find_first(int node, int l, int r, int ql, int qr, T val) {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        pushdown(node, l, r);
        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) {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        pushdown(node, l, r);
        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:
    LazySegmentTree(int n, T init_val = 0) : LazySegmentTree(vector<T>(n, init_val)) {}
    // 维护下标为[0,n-1],初始值为init_val的区间，或者数组a
    LazySegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }
    // 更新[ql,qr]为f
    void update(int ql, int qr, F f) { update(1, 0, n - 1, ql, qr, f); }
    // 区间查询[ql,qr]
    T query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }

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

    int find_last(int ql, int qr, T val) { return find_last(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中最后一个满足条件的下标
};
// 注：懒标记线段树无论做什么都需要pushdown
// 此时其它与线段树二分同
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    int tem = 0;
    vi cnt(n + 1);
    LazySegmentTree<ll, ll> tree(2 * n + 1);
    rep(i, 0, n - 1) {
        if (a[i] < tem && cnt[a[i]] == 0) {
            int tem2 = min(2 * a[i] + 1, 2 * n);
            tree.update(1, tem2, -1);
        } else {
            tree.update(1, a[i], -1);
        }
        if (a[i] <= n) cnt[a[i]]++;
        while (tem < i + 1) {
            bool pd = true;
            if (cnt[tem] > 0) {
                tree.update(1, tem, 1);
            } else {
                int tem2 = min(2 * tem + 1, 2 * n);
                tree.update(1, tem2, 1);
                pd = false;
            }
            if (tree.query(1, 2 * n) <= 0) {
                tem++;
            } else {
                if (pd) {
                    tree.update(1, tem, -1);
                } else {
                    int tem2 = min(2 * tem + 1, 2 * n);
                    tree.update(1, tem2, -1);
                }
                break;
            }
        }
        cout << tem << ' ';
    }
    cout << endl;
    return;
}