Haybale Stacking（差分数组 + 求中位数的一些方法 + nth_element）

题意：

给定N个初始值为0的数， 然后给定K个区间修改（区间[l,r] 每个元素加一）， 求修改后序列的中位数。

分析：

K个离线的区间修改可以使用差分数组（http://www.cnblogs.com/Jadon97/p/8053946.html）实现。

关于对一个无序的序列找出中位数

方法一：

 第一时间想到的方法是快排然后之间取中位数， 排序复杂度为O（NlogN），取第k大的数复杂度O（1）。

用时：124ms

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 7;
int N, K;
int a[maxn], d[maxn];
int main(){
    cin >> N >> K;
    d[1] = a[1];
    for(int i = 0; i < K; i++){
        int a, b;
        cin >> a >> b;
        d[a]++, d[b+1]--;
    }
    for(int i = 1; i <= N; i++){
        a[i] = a[i-1] + d[i];
    }
    sort(a+1,a+1+N);
    cout << a[N/2+1] << "
";
    return 0;
}

方法二：

但其实还有有一个O（n）的算法，是利用快排的思想，详情可查看partiton算法（http://blog.jobbole.com/105219/），这个算法可以延伸到求第k大的数

• pos == k，则找到第 K 小的值，arr[pos]；
• pos > k，则第 K 小的值在左边部分的数组。
• pos < k，则第 K 大的值在右边部分的数组。

而在最好情况下，每次将数组均分为长度相同的两半，运行时间 T(N) = N + T(N/2)，时间复杂度是 O(N)， 但是这个算法最坏情况是O（N²）,暂时没想到很好的优化方法。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 7;
int N, K;
int a[maxn], d[maxn];
int partition(int begin, int end) //[begin,end]左闭右闭区域
{
    int pivot = a[begin];//选取第一个数为枢轴
    while(begin < end)
    {
        while(begin < end && a[end] >= pivot) end--; //在后面选取一个小于枢轴的数
        a[begin] = a[end]; //将那个数放到前面
        while(begin < end && a[begin] <= pivot) begin++; //在前面选取一个大于枢轴的数
        a[end] = a[begin];//将那个数放到后面
    }
    a[begin] = pivot;//最后将枢轴放回
    return begin;//返回枢轴的下标
}

int find_kth_number(int k){
    int begin = 1, end = N;
    int target_num = 0;
    while (begin <= end){
        int pos = partition(begin, end);//查看枢轴的位置
        if(pos == k){//如果枢轴 == k， 那么枢轴就是第k小的数
            target_num = a[pos];
            break;
        }
        else if(pos > k){//否则从左边找
            end = pos - 1;
        }
        else{//否则从右边找
            begin = pos + 1;
        }
    }
    return target_num;
}
int main(){
    scanf("%d %d", &N, &K);
    d[1] = a[1];
    for(int i = 0; i < K; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        d[a]++, d[b+1]--;
    }
    for(int i = 1; i <= N; i++){
        a[i] = a[i-1] + d[i];
    }
    printf("%d
", find_kth_number(N/2+1));
    return 0;
}

但是有一个STL库函数eth_element（http://zh.cppreference.com/w/cpp/algorithm/nth_element）， 思想应该是差不多的， 但因为优化原因运行时间可以过这题， 所以可以使用这个库函数快速求出第k大的数。

用时：74ms

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 7;
int N, K;
int a[maxn], d[maxn];
int main(){
    scanf("%d %d", &N, &K);
    d[1] = a[1];
    for(int i = 0; i < K; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        d[a]++, d[b+1]--;
    }
    for(int i = 1; i <= N; i++){
        a[i] = a[i-1] + d[i];
    }
    nth_element(a+1,a+N/2+1,a+1+N);
    printf("%d
", a[N/2+1]);
    return 0;
}

方法三：

对于这题特殊的区间修改， 因为N多达1e6， 而K只有25000， 所以最大的数也只有K， 所以我们求出区间修改的值的时候，可以把每个数的出现次数记录下来， 然后循环K次，把出现次数累计起来。加上某个数累计次数大于等于N/2时， 那个数就是中位数，复杂度是（N+K），应该是最快的方法了。

用时：49ms

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1234567;
int N, K;
int a[maxn], d[maxn];
int cnt_num[25000 + 7];
int main(){
    scanf("%d %d", &N, &K);
    d[1] = a[1];
    for(int i = 0; i < K; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        d[a]++, d[b+1]--;
    }
    for(int i = 1; i <= N; i++){
        a[i] = a[i-1] + d[i];
        cnt_num[a[i]]++;//统计每个数字出现了多少次
    }
    int sum = 0, mid_num;
    for(mid_num = 0; mid_num <= K; mid_num++){
        sum += cnt_num[mid_num];
        if(sum > N/2) break;
    }
    printf("%d
", mid_num);
    return 0;
}