BZOJ3110 [ZJOI2013]K大数查询

2015.02.26 15:49 Thu| 9 visits oi_2015| 2015_刷题日常| Text

Solution

这正经可谓是拖了半年的一道题啊 →_→ 昨天练手+凑数终于在 11 点多交了上去哈~

这貌似是一道和【二逼平衡树】争当树套树入门题的种子选手?

维护二维线段树,其中第一维权值线段树,维护一段权值出现的位置。第二维维护区间内出现当前线段树维护的权值的次数。由于空间的限制,第二维写法需要类似可持久化线段树一样,减少空间的消耗。最后在询问的时候,只需要判断要求的值出现在 mid 的左边还是右边从而确定递归方向就可以辣~

一个细节:由于要求的是第 K 大,可以直接在插入的时候插入相反数~

Code

#include <bits/stdc++.h>
using namespace std;

#define N 200005
#define _lson (pos << 1)
#define _rson (pos << 1 | 1)

int n, 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;
}

struct node
{
    node *lson, *rson; int sum, lazy;
    node() : lson(), rson(), sum(), lazy() {}
} *root[N];

void pushdown(node* &pos, int l, int r)
{
    if (pos->lson == NULL) pos->lson = new node();
    if (pos->rson == NULL) pos->rson = new node();
    int mid = (l + r) >> 1;
    pos->lson->lazy += pos->lazy;
    pos->rson->lazy += pos->lazy;
    pos->lson->sum += pos->lazy * (mid - l + 1);
    pos->rson->sum += pos->lazy * (r - mid);
    pos->lazy = 0;
}

void modify(node* &pos, int l, int r, int x, int y)
{
    if (pos == NULL) pos = new node();
    if (x <= l && r <= y)
    {
        pos->sum += r - l + 1;
        ++pos->lazy; return ;
    }
    if (pos->lazy) pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(pos->lson, l, mid, x, y);
    if (mid < y) modify(pos->rson, mid + 1, r, x, y);
    if (!pos->lson) pos->sum = pos->rson->sum;
    else if (!pos->rson) pos->sum = pos->lson->sum;
    else pos->sum = pos->lson->sum + pos->rson->sum;
}

void insert(int pos, int l, int r, int x, int a, int b)
{
    modify(root[pos], 1, n, a, b);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(_lson, l, mid, x, a, b);
    else insert(_rson, mid + 1, r, x, a, b);
}

int query(node *pos, int l, int r, int x, int y)
{
    if (pos == NULL) return 0;
    if (x <= l && r <= y) return pos->sum;
    if (pos->lazy) pushdown(pos, l, r);
    int mid = (l + r) >> 1, re = 0;
    if (x <= mid) re += query(pos->lson, l, mid, x, y);
    if (mid < y) re += query(pos->rson, mid + 1, r, x, y);
    return re;
}

int query(int pos, int l, int r, int x, int y, int c)
{
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int t = query(root[_lson], 1, n, x, y);
    if (t >= c) return query(_lson, l, mid, x, y, c);
    else return query(_rson, mid + 1, r, x, y, c - t);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int opt = read(), a = read(), b = read(), c = read();
        if (opt == 1) insert(1, 1, n, n - c + 1, a, b);
        else printf("%d\n", n - query(1, 1, n, a, b, c) + 1);
    }
}