BZOJ3110 - [Zjoi2013]K大数查询

2017/04/10

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

题目描述

有 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("$%d\n", Mid);
            //printf("^%d %d %d\n", 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 %d\n", 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 %d\n", 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("%d\n", Ans[i]);
    }
}