Chaos Slover 补档计划 - 整体二分

2015.12.07 19:15 Mon| 3 visits oi_2016| ChaosSlover补档计划| Text

整体二分

和 CDQ 分治一样,利用离线操作的性质,将询问和查询分组递归,从而减少一维树状结构。

BZOJ2527 [Poi2011]Meteors

 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
#include <bits/stdc++.h>
using namespace std;

#define N 300005
#define inf 0x3f3f3f3f
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, m, k, c[N], ans[N], p[N], temp[N];
vector<int> v[N];
long long tag[N * 4];

struct data
{
    int l, r, a;
    data() {}
    data(int _l, int _r, int _a) : l(_l), r(_r), a(_a) {}
} d[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void modify(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y) { tag[pos] += z; return; }
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y, z);
    if (y > mid) modify(rson, mid + 1, r, x, y, z);
}

long long query(int pos, int l, int r, int x)
{
    if (l == r) return tag[pos];
    int mid = (l + r) >> 1;
    if (x <= mid) return tag[pos] + query(lson, l, mid, x);
    else return tag[pos] + query(rson, mid + 1, r, x);
}

void change(int x, int y)
{
    if (d[x].l <= d[x].r)
        modify(1, 1, m, d[x].l, d[x].r, y * d[x].a);
    else
        modify(1, 1, m, d[x].l, m, y * d[x].a),
        modify(1, 1, m, 1, d[x].r, y * d[x].a);
}

void solve(int sl, int sr, int l, int r)
{
    static int now = 0;
    if (sl > sr) return;
    if (l == r) { for (int i = sl; i <= sr; ++i) ans[p[i]] = l; return; }
    int mid = (l + r) >> 1;
    while (now < mid) change(++now, 1);
    while (now > mid) change(now--, -1);
    int tl = sl, tr = sr;
    for (int i = sl; i <= sr; ++i)
    {
        long long tot = 0;
        for (int j = 0; j < (int)v[p[i]].size() && tot < c[p[i]]; ++j)
            tot += query(1, 1, m, v[p[i]][j]);
        (tot >= c[p[i]] ? temp[tl++] : temp[tr--]) = p[i];
    }
    for (int i = sl; i <= sr; ++i)
        p[i] = temp[i];
    solve(sl, tr, l, mid); solve(tl, sr, mid + 1, r);
}

int main()
{
    cin >> n >> m;
    for (int x, i = 1; i <= m; ++i)
        x = read(), v[x].push_back(i);
    for (int i = 1; i <= n; ++i)
        c[i] = read(), p[i] = i;
    cin >> k;
    for (int x, y, z, i = 1; i <= k; ++i)
        x = read(), y = read(), z = read(), d[i] = data(x, y, z);
    d[k + 1] = data(1, n, inf);
    solve(1, n, 1, k + 1);
    for (int i = 1; i <= n; ++i)
        if (ans[i] <= k) printf("%d\n", ans[i]);
        else puts("NIE");
    return 0;
}

BZOJ2738 矩阵乘法

从小到大将所有元素依次加入矩阵。当一个询问的矩阵中的元素个数达到 k 时,当前加入的元素即为这个询问的解。

话说我感觉忘记看数据范围的我可以自裁了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 60005
#define M 250005

int n, q, x_1[N], y_1[N], x_2[N], y_2[N], c[N], ans[N], p[N], temp[N];
int bit[505][505];

struct data
{
    int a, x, y;
    data() {}
    data(int _a, int _x, int _y) : a(_a), x(_x), y(_y) {}
    bool operator <(const data &d) const { return a < d.a; }
} d[M];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void insert(int x, int y, int z)
{
    for (int i = x; i <= n; i += i & -i)
        for (int j = y; j <= n; j += j & -j)
            bit[i][j] += z;
}

int query(int x, int y)
{
    int re = 0;
    for (int i = x; i; i -= i & -i)
        for (int j = y; j; j -= j & -j)
            re += bit[i][j];
    return re;
}

void change(int x, int y)
{
    insert(d[x].x, d[x].y, y);
}

int getsum(int x)
{
    return query(x_2[x], y_2[x]) - query(x_2[x], y_1[x] - 1)
         - query(x_1[x] - 1, y_2[x]) + query(x_1[x] - 1, y_1[x] - 1);
}

void solve(int sl, int sr, int l, int r)
{
    static int now = 0;
    if (sl > sr) return;
    if (l == r) { for (int i = sl; i <= sr; ++i) ans[p[i]] = d[l].a; return; }
    int mid = (l + r) >> 1;
    while (now < mid) change(++now, 1);
    while (now > mid) change(now--, -1);
    int tl = sl, tr = sr;
    for (int i = sl; i <= sr; ++i)
        if (getsum(p[i]) >= c[p[i]]) temp[tl++] = p[i];
        else temp[tr--] = p[i];
    for (int i = sl; i <= sr; ++i)
        p[i] = temp[i];
    solve(sl, tr, l, mid); solve(tl, sr, mid + 1, r);
}

int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            d[(i - 1) * n + j] = data(read(), i, j);
    sort(d + 1, d + n * n + 1);
    for (int i = 1; i <= q; ++i)
        x_1[i] = read(), y_1[i] = read(),
        x_2[i] = read(), y_2[i] = read(), c[i] = read(), p[i] = i;
    solve(1, q, 1, n * n);
    for (int i = 1; i <= q; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

BZOJ3110 [Zjoi2013]K大数查询

考虑整体二分,在每一个二分区间内,保证时间有序。保证时间有序!保证时间有序……然后用线段树维护一下就做完了。

为什么网上看到那么多神犇写区间修改区间查询的树状数组……

 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
#include <bits/stdc++.h>
using namespace std;

#define N 50005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, m, opt[N], p[N], temp[N], ans[N], tag[N * 4], sum[N * 4];

struct data
{
    int x, y, z;
    data() {}
    data(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
} d[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void lazy(int pos, int l, int r)
{
    int mid = (l + r) >> 1;
    tag[lson] += tag[pos]; tag[rson] += tag[pos];
    sum[lson] += tag[pos] * (mid - l + 1);
    sum[rson] += tag[pos] * (r - mid); tag[pos] = 0;
}

void modify(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    { tag[pos] += z; sum[pos] += z * (r - l + 1); return; }
    int mid = (l + r) >> 1;
    if (tag[pos]) lazy(pos, l, r);
    if (x <= mid) modify(lson, l, mid, x, y, z);
    if (y > mid) modify(rson, mid + 1, r, x, y, z);
    sum[pos] = sum[lson] + sum[rson];
}

int query(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y) { return sum[pos]; }
    int mid = (l + r) >> 1;
    if (tag[pos]) lazy(pos, l, r);
    int re = 0;
    if (x <= mid) re += query(lson, l, mid, x, y);
    if (y > mid) re += query(rson, mid + 1, r, x, y);
    return re;
}

void solve(int sl, int sr, int l, int r)
{
    if (sl > sr) return;
    if (l == r) { for (int i = sl; i <= sr; ++i) ans[p[i]] = l; return; }
    int mid = (l + r) >> 1;
    int tl = sl, tr = sr;
    for (int i = sl; i <= sr; ++i)
    {
        if (opt[p[i]] == 1)
        {
            if (d[p[i]].z > mid)
                modify(1, 1, n, d[p[i]].x, d[p[i]].y, 1), temp[tl++] = p[i];
            else temp[tr--] = p[i];
        }
        else
        {
            int x = query(1, 1, n, d[p[i]].x, d[p[i]].y);
            if (x >= d[p[i]].z) temp[tl++] = p[i];
            else d[p[i]].z -= x, temp[tr--] = p[i];
        }
    }
    for (int i = sl; i <= sr; ++i)
        if (opt[p[i]] == 1 && d[p[i]].z > mid)
            modify(1, 1, n, d[p[i]].x, d[p[i]].y, -1);
    for (int i = sl; i <= sr; ++i)
        p[i] = temp[i];
    reverse(p + tl, p + sr + 1);
    solve(sl, tr, mid + 1, r), solve(tl, sr, l, mid);
}

int main()
{
    cin >> n >> m;
    for (int x, y, z, i = 1; i <= m; ++i)
        opt[i] = read(), x = read(), y = read(), z = read(),
        d[i] = data(x, y, z), p[i] = i;
    solve(1, m, 1, n);
    for (int i = 1; i <= m; ++i)
        if (opt[i] == 2) printf("%d\n", ans[i]);
    return 0;
}