POJ 2104

题目地址:http://poj.org/problem?id=2104

题目大意

给定数列$a_1, a_2, \cdots, a_n$和$m$个三元组表示的查询。对于每个查询$(i, j, k)$,输出$a_i, a_{i+1}, \cdots, a_j$的升序排列中第$k$个数。

这题有线段树解法:归并树

思路

平方分割+二分搜索,看代码很容易理解。

AC代码

/*************************************************************************
    > File Name: 2104.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-31 日 09:31:55 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100000 + 5;
const int B = 1000;
int N, M;
int A[MAXN]; // 数据
vector<int> bucket[MAXN/B]; // 桶
int Asort[MAXN]; // 排序后的数据

void solve() {
    for(int i=0; i<N; ++i) {
        bucket[i/B].push_back(A[i]);
        Asort[i] = A[i];
    }
    sort(Asort, Asort+N);
    for(int i=0; i<N/B; ++i) sort(bucket[i].begin(), bucket[i].end()); // 每个桶进行排序
    int l, r, k;
    for (int i = 0; i < M; ++i) {
        scanf("%d%d%d", &l, &r, &k);
        int lb = -1, ub = N - 1; // (lb, ub]
        while(ub - lb > 1) {
            int mid = (ub + lb) >> 1, x = Asort[mid];
            int tl = l-1, tr = r, c = 0; // 左右边界tl, tr,<=x的个数c
            // 以下用函数调用会超时= =
            while(tl < tr && tl % B != 0) if(A[tl++] <= x) ++c;
            while(tl < tr && tr % B != 0) if(A[--tr] <= x) ++c;
            while(tl < tr) {
                int b = tl / B;
                c += upper_bound(bucket[b].begin(), bucket[b].end(), x) - bucket[b].begin();
                tl += B;
            }
            if(c<k) lb = mid;
            else ub = mid;
        }
        printf("%d\n", Asort[ub]);
    }
}

int main() {
#ifdef Oj
    freopen("2104.in", "r", stdin);
    // freopen("2104.out", "w",stdout);
#endif
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
    solve();
    return 0;
}

POJ 3264

题目地址:http://poj.org/problem?id=3264

题目大意

给定数列$a_1, a_2, \cdots, a_N$和$Q$个查询,求出每次查询$[l, R]$的最大值和最小值之差。

思路

平方分割很容易写出来。。

将桶的大小设置为$\sqrt {50000}\approx 200$个元素,然后对每个桶排序,方便在$O(1)$的复杂度求出每个桶对应的区间的最大值和最小值。

查询的时候,

  1. 如果桶完全包含在区间内,则直接查询最值
  2. 如果不完全包含,则逐个检查。

    AC代码

/*************************************************************************
    > File Name: 3264.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-31 日 14:43:42 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN =  50000+25;
const int B = 200; // 每个桶的大小为200个元素
int height[MAXN];
vector<int> bucket[MAXN/B];
int N, Q;

void solve() {
    for (int i = 0; i < N/B; ++i) // 对每个桶进行排序
        sort(bucket[i].begin(), bucket[i].end());
    for (int i = 0; i < Q; ++i) {
        int l, r;
        int maxh = 0, minh = 1<<30;
        scanf("%d%d", &l, &r); --l;
        // [l, r),逐个求出不包含部分的最值
        while(l < r && l%B != 0) {
            maxh = max(height[l], maxh);
            minh = min(height[l], minh);
            ++l;
        }
        while(l < r && r%B != 0) {
            --r;
            maxh = max(height[r], maxh);
            minh = min(height[r], minh);
        }
        // 剩下的是完全包含部分
        while(l < r) {
            maxh = max(*(bucket[l/B].end()-1), maxh);
            minh = min(*(bucket[l/B].begin()), minh);
            l += B;
        }
        printf("%d\n", maxh - minh);
    }

}

int main() {
#ifdef Oj
    freopen("3264.in", "r", stdin);
    // freopen("3264.out", "w",stdout);
#endif
    scanf("%d%d", &N, &Q);
    for (int i = 0; i < N; ++i) {
        scanf("%d", height+i);
        bucket[i/B].push_back(height[i]);
    }
    solve();
    return 0;
}