NOI2009重庆代表队选拔赛简易题解
中位数：
记录下从1到i的，比给定数大的数字的个数big[i]，比给定数小的数字的个数small[i]。我们即要求这样的i、j组数，即big[ j ] - big[ i - 1] == small[ j ] - small[ i - 1 ]，同时i小于等于给定数所在的位置，j大于等于给定数所在的位置。上式变形得big[ j ] - small[ j ] == big[ i - 1 ] - small[ i - 1 ]。令t[ i ] = big[ i ] - small[ i ]，枚举i作为目标序列的结尾（一定要在给定数的后面），那么所有在给定数之前出现的t[ k ]的个数就是以i为结尾的符合题意的序列数。记录下从1到i的，比
