优秀网站要素,汇源企业网络营销策划,北京燕郊网站建设,开发工具箱http://www.51nod.com/contest/problem.html#!problemId1685 这是这次BSG白山极客挑战赛的E题。 这题可以二分答案t。 关键在于#xff0c;对于一个t#xff0c;如何判断它是否能成为第k大。 将序列中大于t的置为1#xff0c;小于t的置为-1#xff0c;等于t的置为0。那么区…http://www.51nod.com/contest/problem.html#!problemId1685 这是这次BSG白山极客挑战赛的E题。 这题可以二分答案t。 关键在于对于一个t如何判断它是否能成为第k大。 将序列中大于t的置为1小于t的置为-1等于t的置为0。那么区间中位数大于t的和就大于0小于t的就小于0。于是就是判断区间和大于0的个数是否小于等于k。 维护前缀和sum(i)然后统计之前sum(j)小于sum(i)的有多少个就是以i为右值的区间和大于0的个数。于是就可以用树状数组维护了。 由于是奇数长度区间所以树状数组需要维护奇偶长度的前缀和个数。需要特判sum(i) 0的情况。 代码 #include iostream
#include cstdio
#include cstdlib
#include cmath
#include cstring
#include algorithm
#include set
#include map
#include queue
#include vector
#include string
#define LL long longusing namespace std;//线段树
//区间每点增值求区间和
const int maxN 100010;LL d[2][maxN*2];int lowbit(int x)
{return x(-x);
}void add(int t, int id,int pls)
{while(id maxN1)//id最大是maxN{d[t][id] pls;id lowbit(id);}
}LL sum(int t, int to)
{LL s 0;while(to 0){s s d[t][to];to - lowbit(to);}return s;
}LL query(int t, int from, int to)
{return sum(t, to) - sum(t, from-1);
}int n, a[maxN], b[maxN];
LL k;LL judge(int t)
{for (int i 0; i n; i){if (a[i] t) b[i] 1;else if (a[i] t) b[i] 0;else b[i] -1;}memset(d, 0, sizeof(d));int sum 0;LL ans 0;for (int i 0; i n; i){sum b[i];ans query(!(i%2), 100005-n, 100005sum-1);if (i%2 0 sum 0) ans;add(i%2, 100005sum, 1);}return ans;
}void work()
{int lt, rt, mid;lt rt a[0];for (int i 1; i n; i){lt min(lt, a[i]);rt max(rt, a[i]);}while ((LL)lt1 rt){mid ((LL)ltrt)1;if (judge(mid) k-1) lt mid;else rt mid;}if (judge(lt) k-1) printf(%d\n, lt);else printf(%d\n, rt);
}int main()
{//freopen(test.in, r, stdin);while (scanf(%d, n) ! EOF){cin k;for (int i 0; i n; i) scanf(%d, a[i]);work();}return 0;
} View Code 转载于:https://www.cnblogs.com/andyqsmart/p/5523820.html
