zkx06111's Blog

SPOJ KQUERYO

| Comments

辣鸡出题人,毁我青春系列。数据范围与实际描述不符合wa惨系列。

看到cicada的线段树博文想自己写一篇发现爆炸了系列。

题意是给一个序列,有q次询问,每次询问在区间[l,r]中比k大的数字有几个,强制在线。

做法非常清真。只要用一棵线段树,每个节点是一个有序储存该区间内数字的vector。询问时,如果询问的区间包含了当前的区间,那么直接在当前区间上二分,如果没有包含则分到两个子区间处理。

建树的时候只需要像归并排序一样就可以。

复杂度是O(log n)的,相对于普通的线段树来说这个log要满。因为普通线段树的复杂度取决于查询的深度。而这种线段树如果区间大,查询深度小的话二分的复杂度就大,而如果区间小查询深度大的话二分的复杂度小。所以对于不同的询问复杂度较为接近。

前面是在扯淡。

单次操作最坏访问层,自上到下每层的大小减半,所以单次最坏复杂度可以表示为:

但是出题人他妈的数据不会造啊,连样例都是错的啊。说好的1 <= L <= R <= n的情况呢?!

存在L < 1, L > n, R > n, R < 1, L > R等各种坑爹情况,傻逼出题人毁我青春!

KQUERYO.cpp
#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define PER(i, a, b) for (int i = a; i >= b; --i)
#define RVC(i, S) for (int i = 0; i < S.size(); ++i)
using namespace std;

inline int read(){
    int x = 0, f = 1, ch = getchar();
    while (!isdigit(ch)){if (f == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return f * x;
}

typedef vector<int> vi;
const int N = 30005;
int n, q, last_ans;
vi val[N * 15];

#define lc (x << 1)
#define rc (x << 1 | 1)

void merge(vi&x, const vi&a, const vi&b){
    x.clear();
    int i = 0, j = 0;
    for (; i < a.size() && j < b.size();)
        if (a[i] < b[j]) x.push_back(a[i]), ++i;
        else x.push_back(b[j]), ++j;
    for (; i < a.size(); ++i) x.push_back(a[i]);
    for (; j < b.size(); ++j) x.push_back(b[j]);
}

void build(int x, int l, int r){
    if (l == r){
        val[x].push_back(read());
        return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    merge(val[x], val[lc], val[rc]);
}

int query(int x, int l, int r, int ql, int qr, int qk){
    if (ql <= l && r <= qr){
        int bl = 0, br = r - l, res = -1;
        while (bl <= br){
            int bm = (bl + br) >> 1;
            if (val[x][bm] <= qk){
                res = bm;
                bl = bm + 1;
            }
            else br = bm - 1;
        }
        return res + 1;
    }
    int res = 0, mid = (l + r) >> 1;
    if (ql <= mid) res += query(lc, l, mid, ql, qr, qk);
    if (qr > mid) res += query(rc, mid + 1, r, ql, qr, qk);
    return res;
}

int main(){
    n = read();
    build(1, 1, n);
    q = read();
    REP(i, 1, q){
        int ql = read(), qr = read(), qk = read();
#ifdef DEBUG
#else
     ql ^= last_ans; qr ^= last_ans; qk ^= last_ans;
#endif
     if (qr < 1) last_ans = 0;
        else if (ql > n) last_ans = 0;
        else if (ql > qr) last_ans = 0;
        else{
            ql = max(ql, 1);
            qr = min(qr, n);
            last_ans = qr - ql + 1 - query(1, 1, n, ql, qr, qk);
        }
        printf("%d\n", last_ans);
    }
    return 0;
}

Comments

comments powered by Disqus