USACO2012 Haybale stacking /// 区间表示法 oj21556

题目大意：
N个方块 标号1~N 

K个操作 操作a b 表示标号a~b区间每位多加一个方块

Input

* Line 1: Two space-separated integers, N  K.

* Lines 2..1+K: Each line contains one of FJ's instructions in the form of two space-separated integers A  B (1 ≤ A ≤ B≤ N).

Output

* Line 1: The median height of a stack after Bessie completes the instructions.

Sample Input

7 4
5 5
2 4
4 6
3 5

Sample Output

1

即 有N = 7个方块，发出K = 4个指令。第一条指令是添加方块在堆栈5，第二个是添加方块到堆栈2..4等

输出细节：

操作完成后，堆栈的高度为 0, 1, 2, 3, 3, 1, 0。

中间堆栈高度为1，因为1是排序的顺序中的0, 0, 1, 1, 2, 3, 3。

区间表示法

#include <stdio.h>

#include <string.h>

#include <algorithm>

int flag[]={};

using namespace std;

int main()

{

    int n,k;

    scanf("%d%d",&n,&k);

    while(k--)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        flag[a]++;

        flag[b+]--;

    }

    int sum=;

    for(int i=;i<=n;i++)

    {

        sum+=flag[i];

        flag[i]=sum;

    }

    sort(flag,flag+n+);

    printf("%d\n",flag[n/+]);

    return ;

}