1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void solve() {
    ll n;
    cin >> n;
    vl res(1 << n);
    vi vis(1 << n);
    int idx = 1;
    res[0] = (1 << n) - 1;
    vis[(1 << n) - 1] = 1;
    frep(i, n - 1, 0) {
        rep(j, 0, (1 << (n - i)) - 1) {
            if (vis[(j << i) | ((1 << i) - 1)]) continue;
            vis[(j << i) | ((1 << i) - 1)] = 1;
            res[idx++] = ((j << i) | ((1 << i) - 1));
        }
    }
    rep(i, 0, (1 << n) - 1) {
        if (!vis[i]) res[idx++] = i;
    }
    rep(i, 0, (1 << n) - 1) cout << res[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
37
38
39
40
41

void solve() {
    ll n, x, y;
    cin >> n >> x >> y;
    string s;
    cin >> s;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    rep(i, 0, n - 1) ans += a[i];
    if (ans > x + y) {
        cout << "NO" << endl;
        return;
    }
    vl b(n), c(n);
    rep(i, 0, n - 1) {
        if (s[i] == '0') {
            b[i] = a[i] / 2 + 1;
        } else {
            c[i] = a[i] / 2 + 1;
        }
    }
    ll tem1 = 0, tem2 = 0;
    rep(i, 0, n - 1) { tem1 += b[i], tem2 += c[i]; }
    if (tem1 != 0 && tem2 != 0) {
        if (tem1 > x || tem2 > y)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    } else if (tem1 == 0) {
        if (tem2 <= y && y >= x + n)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    } else if (tem2 == 0) {
        if (tem1 <= x && x >= y + n)
            cout << "YES" << endl;
        else
            cout << "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
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

void solve1() {
    int n, m, x, y;
    cin >> n >> m;
    vvi ma(n);
    rep(i, 0, m - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    vi dis(n, -1);
    queue<int> q;
    rep(st, 0, n - 1) {
        if (dis[st] != -1) continue;
        while (!q.empty()) q.pop();
        dis[st] = 0;
        q.push(st);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int p : ma[node]) {
                if (dis[p] == -1) {
                    dis[p] = dis[node] + 1;
                    q.push(p);
                }
            }
        }
    }
    string res = "";
    rep(i, 0, n - 1) {
        if (dis[i] % 3 == 0)
            res.push_back('r');
        else if (dis[i] % 3 == 1)
            res.push_back('g');
        else
            res.push_back('b');
    }
    cout << res << endl;
    return;
}
void solve2() {
    ll q, n;
    string s;
    cin >> q;
    rep(i, 0, q - 1) {
        cin >> n >> s;
        int cnt0 = 0, cnt1 = 0, cnt2 = 0;
        int idx0 = -1, idx1 = -1, idx2 = -1;
        rep(j, 0, n - 1) {
            if (s[j] == 'r') {
                cnt0++;
                idx0 = j + 1;
            } else if (s[j] == 'g') {
                cnt1++;
                idx1 = j + 1;
            } else {
                cnt2++;
                idx2 = j + 1;
            }
        }
        if (cnt0 == 0 && cnt1 == 0)
            cout << idx2 << endl;
        else if (cnt0 == 0 && cnt2 == 0)
            cout << idx1 << endl;
        else if (cnt1 == 0 && cnt2 == 0)
            cout << idx0 << endl;
        else if (cnt0 == 0)
            cout << idx2 << endl;
        else if (cnt1 == 0)
            cout << idx0 << endl;
        else if (cnt2 == 0)
            cout << idx1 << endl;
    }
    return;
}
void solve(string x) {
    int t;
    cin >> t;
    while (t--) {
        if (x == "first")
            solve1();
        else
            solve2();
    }
}

 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

ll ask(ll l, ll r) {
    cout << "? " << l << ' ' << r << '\n';
    cout.flush();
    ll op;
    cin >> op;
    return op;
}
void report(vvl& res) {
    cout << "! ";
    ll n = sz(res);
    rep(i, 0, n - 1) {
        rep(j, 0, n - 1) cout << res[i][j] << ' ';
        cout << '\n';
    }
    cout.flush();
    return;
}
void solve() {
    ll n;
    cin >> n;
    vvl ma(2 * n + 1);
    vvl ma2(2 * n + 1);
    ll maxx = LLONG_MIN;
    rep(i, 2, n * n) {
        ll op = ask(1, i);
        maxx = max(maxx, op);
        ma[op].push_back(i);
    }
    ll l1 = ma[maxx][0];
    vl dis(n * n + 1);
    rep(i, 1, n * n) {
        if (i == l1) continue;
        ll op = ask(i, l1);
        ma2[op].push_back(i);
        dis[i] = op;
    }
    ll l2 = ma2[2 * n - 2][0];
    ll tem = ma2[n - 1][0];
    ll maxx2 = LLONG_MIN;
    ll l3 = -1;
    for (auto& p : ma2[n - 1]) {
        ll op = ask(tem, p);
        if (op > maxx2) {
            maxx2 = op;
            l3 = p;
        }
    }
    vl dis2(n * n + 1);
    rep(i, 1, n * n) dis2[i] = ask(i, l3);
    vvl res(n, vl(n));
    rep(i, 1, n * n) {
        ll x = (dis[i] + dis2[i] - n + 1) / 2;
        ll y = dis[i] - x;
        res[x][y] = i;
    }
    report(res);
    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

struct Tag {
    ll a = 0;  // 懒标记初始值
    ll b = 0;

    Tag(ll a = 0, ll b = 0) : a(a), b(b) {}

    bool empty() const { return a == 0 && b == 0; }

    void apply(const Tag& t) {
        a += t.a;
        b += t.b;
    }  // 合并懒标记：先已有操作，再做t
};

struct Info {
    ll sum = 0;
    ll cnt = 0;
    ll cnt2 = 0;
    Info(ll sum = 0, ll cnt = 0, ll cnt2 = 0) : sum(sum), cnt(cnt), cnt2(cnt2) {}

    void apply(const Tag& t, int l, int r) { sum += t.a * cnt + t.b * cnt2; }  // 把懒标记作用到当前节点
};

Info operator+(const Info& a, const Info& b) { return {a.sum + b.sum, a.cnt + b.cnt, a.cnt2 + b.cnt2}; }  // 合并两个Info

bool operator<(const Info& a, const Info& b) { return a.sum < b.sum; }  // 线段树二分用，不需要时可删

template <typename Info, typename Tag>
class LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;

    void apply(int node, int l, int r, const Tag& v) {
        info[node].apply(v, l, r);
        tag[node].apply(v);
    }

    void pushdown(int node, int l, int r) {
        if (tag[node].empty()) return;
        int m = (l + r) >> 1;
        apply(node << 1, l, m, tag[node]);
        apply(node << 1 | 1, m + 1, r, tag[node]);
        tag[node] = Tag();
    }  // 把当前节点的懒标记下传

    void maintain(int node) { info[node] = info[node << 1] + info[node << 1 | 1]; }

    void build(const vector<Info>& a, int node, int l, int r) {
        if (l == r) {
            info[node] = 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, const Tag& v) {
        if (ql <= l && r <= qr) {
            apply(node, l, r, v);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (ql <= m) update(node << 1, l, m, ql, qr, v);
        if (qr > m) update(node << 1 | 1, m + 1, r, ql, qr, v);
        maintain(node);
    }  // 区间更新[ql,qr]

    void assign(int node, int l, int r, int p, const Info& v) {
        if (l == r) {
            info[node] = v;
            tag[node] = Tag();
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (p <= m)
            assign(node << 1, l, m, p, v);
        else
            assign(node << 1 | 1, m + 1, r, p, v);
        maintain(node);
    }  // 单点赋值

    Info query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return info[node];
        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);
        return query(node << 1, l, m, ql, qr) + query(node << 1 | 1, m + 1, r, ql, qr);
    }  // 区间查找

    template <typename F>
    int find_first(int node, int l, int r, int ql, int qr, F&& check) {
        if (r < ql || l > qr || !check(info[node])) 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, check);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, check);
    }  // 若遇到固定左端点的情况，需要使用全局变量（或者传入引用）记录前缀分段最大值，加一个被待求区间完全覆盖的剪枝

    template <typename F>
    int find_last(int node, int l, int r, int ql, int qr, F&& check) {
        if (r < ql || l > qr || !check(info[node])) 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, check);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, check);
    }

    void collect(int node, int l, int r, vector<Info>& res) {
        if (l == r) {
            res[l] = info[node];
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        collect(node << 1, l, m, res);
        collect(node << 1 | 1, m + 1, r, res);
    }

public:
    LazySegmentTree(int n, Info init_val = Info()) : LazySegmentTree(vector<Info>(n, init_val)) {}
    // 维护下标为[0,n-1],初始值为init_val的区间，或者数组a
    LazySegmentTree(const vector<Info>& a) : n(sz(a)), info(2 << bit_width((unsigned)sz(a) - 1)), tag(2 << bit_width((unsigned)sz(a) - 1)) {
        build(a, 1, 0, n - 1);
    }
    // 更新[ql,qr]为f
    void update(int ql, int qr, const Tag& v) { update(1, 0, n - 1, ql, qr, v); }
    // 单点赋值a[p]=v
    void assign(int p, const Info& v) { assign(1, 0, n - 1, p, v); }
    // 区间查询[ql,qr]
    Info query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }

    template <typename F>
    int find_first(int ql, int qr, F&& check) {
        return find_first(1, 0, n - 1, ql, qr, check);
    }  // 查询[ql,qr]中第一个满足条件的下标

    template <typename F>
    int find_last(int ql, int qr, F&& check) {
        return find_last(1, 0, n - 1, ql, qr, check);
    }  // 查询[ql,qr]中最后一个满足条件的下标

    int find_first(int ql, int qr, const Info& val) {
        return find_first(ql, qr, [&](const Info& x) { return !(x < val); });
    }

    int find_last(int ql, int qr, const Info& val) {
        return find_last(ql, qr, [&](const Info& x) { return !(x < val); });
    }

    vector<Info> collect() {
        vector<Info> res(n);
        collect(1, 0, n - 1, res);
        return res;
    }
};
// 注：懒标记线段树无论做什么都需要pushdown
// 此时其它与线段树二分同
void solve() {
    ll n, q;
    cin >> n >> q;
    vector<pll> queries(q);
    rep(i, 0, q - 1) {
        cin >> queries[i].first >> queries[i].second;
        queries[i].first--, queries[i].second--;
    }
    vl ans(n);
    for (ll i = 1; i <= n; i <<= 1) {
        vl tem(2 * i);
        vl id(n);
        int cnt = 0;
        rep(j, 0, 2 * i - 1) {
            tem[j] = cnt;
            for (int v = j; v <= n - 1; v += 2 * i) {
                id[cnt++] = v;
            }
        }
        vl diff1(n + 1), diff2(n + 1);
        for (auto& [l, r] : queries) {
            if (i > (r - l + 1)) continue;
            int tem2 = l + i - 1;
            int tem3 = tem2 + (r - tem2) / (2 * i) * (2 * i);
            ll l1 = tem[tem2 % (2 * i)] + (tem2 - (tem2 % (2 * i))) / (2 * i);
            ll r1 = tem[tem3 % (2 * i)] + (tem3 - (tem3 % (2 * i))) / (2 * i);
            diff1[l1] += i, diff1[r1 + 1] -= i;
            diff2[l1] += i * (1 - l), diff2[r1 + 1] -= i * (1 - l);
        }
        ll cur1 = 0, cur2 = 0;
        rep(j, 0, n - 1) {
            cur1 += diff1[j], cur2 += diff2[j];
            ans[id[j]] += cur1 * id[j] + cur2;
        }
    }
    rep(i, 0, n - 1) cout << ans[i] << ' ';
    cout << endl;
    return;
}