CPTH/tests/BIT/BIT.cpp at master · ouuan/CPTH · GitHub

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
// https://ouuan.github.io/post/parallel-binary-search/#zjoi2013k%E5%A4%A7%E6%95%B0%E6%9F%A5%E8%AF%A2httpswwwluogucomcnproblemp3332

#include "../../headers/BIT.h"

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

struct Operation
{
    int l, r, id;
    ll target, current, tmp;
    Operation(int _l, int _r, int _id, ll _target)
        : l(_l), r(_r), id(_id), target(_target), current(0), tmp(0)
    {}
};

CPTH::BIT<ll> bitk, bitb;

void add(int p, int x)
{
    bitk.add(p, x);
    bitb.add(p, (1 - p) * x);
}

ll query(int p)
{
    return bitk.query(p) * p + bitb.query(p);
}

void clear()
{
    bitk.clear();
    bitb.clear();
}

vector<int> ans;

#define mid ((l + r) >> 1)

void solve(int l, int r, vector<Operation> &ops)
{
    if (l == r - 1)
    {
        for (auto op : ops)
        {
            if (~op.id)
                ans[op.id] = l;
        }
        return;
    }
    clear();
    for (auto &op : ops)
    {
        if (~op.id)
            op.tmp = query(op.r) - query(op.l - 1);
        else if (op.target < mid)
        {
            add(op.l, 1);
            add(op.r + 1, -1);
        }
    }
    vector<Operation> lop, rop;
    for (auto op : ops)
    {
        if (op.id == -1)
        {
            if (op.target < mid)
                lop.push_back(op);
            else
                rop.push_back(op);
        }
        else
        {
            if (op.current + op.tmp >= op.target)
                lop.push_back(op);
            else
            {
                op.current += op.tmp;
                rop.push_back(op);
            }
        }
    }
    vector<Operation>().swap(ops);
    solve(l, mid, lop);
    solve(mid, r, rop);
}

int main()
{
    int n, m;

    scanf("%d%d", &n, &m);

    int qid = 0;
    vector<Operation> ops;

    for (int i = 0; i < m; ++i)
    {
        int op, l, r;
        ll x;
        scanf("%d%d%d%lld", &op, &l, &r, &x);
        if (op == 1)
            ops.emplace_back(l, r, -1, -x);
        else
            ops.emplace_back(l, r, qid++, x);
    }

    ans.resize(qid);
    bitk.init(n, plus<ll>());
    bitb = CPTH::BIT<ll>(n, plus<ll>());
    solve(-n, n + 1, ops);

    for (auto x : ans)
        printf("%d\n", -x);

    return 0;
}