首页 > itarticle > BZOJ3110 – [Zjoi2013]K大数查询

BZOJ3110 – [Zjoi2013]K大数查询

admin 11月 12, 2020 0

我好菜啊 _(:з」∠)_

题目描述

有 N 个位置， M 个操作。操作有两种，每次操作如果是 1 a b c 的形式表示在第a个位置到第b个位置，每个位置加入一个数 c 。
如果是 2 a b c 形式，表示询问从第 a 个位置到第 b 个位置，第 c 大的数是多少。

解法

对操作进行整体二分。

代码

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



#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define lowbit(x) ((x) & (-x))
using namespace std;
typedef long long LL;
const int SIZ = int(1E6);

int N, M;
LL c1[SIZ], c2[SIZ];

void add(int x, int ad) {
    LL bili = x * ad;
    for(;x<=N;x+=lowbit(x)) {
        c1[x] += ad;
        c2[x] += bili;
    }
}

LL query(int x) {
    int bili = x+1;
    LL sum = 0LL;
    for(;x;x-=lowbit(x)) {
        sum += bili * c1[x] - c2[x];
    }
    return sum;
}

void tAdd(int L, int R, int ad) {
    add(L, ad); add(R+1, -ad);
}

LL tSum(int L, int R) {
    return query(R) - query(L-1);
}

struct Qry {
    enum {
        INS, QRY
    } typ;
    int l, r, c, idx;
} Q[SIZ], Right[SIZ], Left[SIZ];

int Ans[SIZ];

void solve(int L, int R, int B, int E) { // Value [L, R] On [B, E]
    if(B > E) return;
    if(L > R) return;
    int Mid = (L + R + 1) >> 1;
    if(L == R) {
        for(int i=B;i<=E;i++) {
            if(Q[i].typ==Qry::QRY) Ans[Q[i].idx] = L;
        }
        return;
    }
    
    int lpos = 0, rpos = 0;
    for(int i=B;i<=E;i++) {
        if(Q[i].typ == Qry::INS) {
            //printf("$%dn", Mid);
            //printf("^%d %d %dn", Q[i].c, Mid, int(Q[i].c >= Mid));
            if(Q[i].c >= Mid) {
                tAdd(Q[i].l, Q[i].r, 1);
                Right[rpos++] = Q[i];
            } else {
                Left[lpos++] = Q[i];
            }
        } else {
            LL cur = tSum(Q[i].l, Q[i].r);
            //printf("@%d %d %lld %dn", Q[i].l, Q[i].r, cur, Q[i].c);
            if(cur >= Q[i].c) Right[rpos++] = Q[i];
            else Q[i].c -= cur, Left[lpos++] = Q[i];
        }
    }
    
    for(int i=B;i<=E;i++) {
        if(Q[i].typ == Qry::INS && Q[i].c >= Mid) {
            tAdd(Q[i].l, Q[i].r, -1);
        }
    }
    
    for(int i=0;i<lpos;i++) {
        Q[B+i] = Left[i];
    }
    for(int i=0;i<rpos;i++) {
        Q[B+lpos+i] = Right[i];
    }
    
    //printf(" %d %d %dn", Mid, lpos, rpos); system("pause");
    solve(L, Mid-1, B, B+lpos-1);
    solve(Mid  , R, B+lpos  , E);
}

int main() {
    scanf("%d %d", &N, &M);
    
    int t;
    for(int i=1;i<=M;i++) {
        scanf("%d %d %d %d", &t, &Q[i].l, &Q[i].r, &Q[i].c);
        Q[i].typ = (t&1) ? Qry::INS : Qry::QRY;
        Q[i].idx = i;
    }
    
    memset(Ans, 0x8F, sizeof(Ans));
    
    solve(-N, N, 1, M);
    
    for(int i=1;i<=M;i++) {
        if(Ans[i] != 0x8F8F8F8F)
            printf("%dn", Ans[i]);
    }
}