## BSOJ3686 -- 【USACO 2011 November Gold】Above the Median【树状数组统计】

### Description

Farmer John has lined up his N (1 <= N <= 100,000) cows in a row to measure their heights; cow i has height H_i (1 <= H_i <= 1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair.

The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 <= X <= 1,000,000,000).

For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.

Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.

### Input

* Line 1: Two space-separated integers: N and X.
* Lines 2..N+1: Line i+1 contains the single integer H_i.

### Output

* Line 1: The number of subsequences of FJ's cows that have median at least X. Note this may not fit into a 32-bit integer.

### Sample Input

4 6
10
5
6
2

INPUT DETAILS:

FJ's four cows have heights 10, 5, 6, 2. We want to know how many contiguous subsequences have median at least 6.

### Sample Output

7

OUTPUT DETAILS:

There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.

（新本本好好用。呵呵呵。）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210000,d=100010;
int n,m,a[100010],bit[maxn+10];
void modify(int x){
for(;x<=maxn;x+=x&-x)	bit[x]++;
}
int r=0;
for(;x;x-=x&-x)	r+=bit[x];
return r;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>=m)	a[i]=1;	else a[i]=-1;
}
int sum=0;
long long An=0;
modify(d);
for(int i=1;i<=n;i++){
sum+=a[i];
modify(sum+d);
}
cout << An << endl;
return 0;
}

## BSOJ3411-【USACO 2009 January Gold】Safe Path【dijkstra+左偏树】

Safe Travel
Time Limit: 20000 ms Memory Limit: 65536 KB

Description
Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最短路经的长度.

Input
* 第一行: 两个空格分开的数, N和M
* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output
* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

Sample Output
3
3
6

dijkstra+heap跑一遍。处理出dist数组。建好SPT。树根当然是1。

①先沿着SPT的边从1走到v。然后通过一条不是SPT的边，走到u本身。

②先沿着SPT的边从1走到v。然后通过一条不是SPT的边，走到u在SPT中的子孙，再沿着SPT上的边就可以走到u了。



#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 110000,maxm = 510000,inf = 1061109657;
struct node{
int x,dis;
node(){};
node(int _x,int _d):x(_x),dis(_d){};
inline bool operator < (node b)const{
return dis < b.dis;
}
}H[maxn];
int pos[maxn]={0},rt[maxm],An[maxn],dfn[maxn],path[maxn],size = 0,ee = 0,cnt = 0;
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn],D[maxn],tot = 0,n,m;
struct lt{
int l,r,d,id;
}L[maxm];
inline void sw(int a,int b){
pos[H[a].x] = b;
pos[H[b].x] = a;
swap(H[a],H[b]);
}
#define pt (x >> 1)
#define ls (x << 1)
#define rs (x << 1 | 1)
void up(int x){
if(x == 1)  return;
if(H[x] < H[pt])    sw(x,pt),up(pt);
}
void down(int x){
int s = x;
if(ls <= size && H[ls] < H[x])  s = ls;
if(rs <= size && H[rs] < H[s])  s = rs;
if(s != x)  sw(x,s),down(s);
}
void del(int x){
sw(x,size);
size --;
up(x);
down(x);
}
void ins(node a){
H[++ size] = a;
pos[a.x] = size;
up(size);
}
void dijkstra(int s){
size = d[s] = 0;
ins(node(s,0));
while(size){
node u = H[1];
pos[H[1].x] = 0;
del(1);
if(vis[u.x])    continue;
vis[u.x] = 1;
for(int i = h[u.x];~i;i = n1[i])    if(!vis[p[i]])
if(u.dis + w[i] < d[p[i]]){
d[p[i]] = u.dis + w[i];
path[p[i]] = u.x;
if(pos[p[i]]){
H[pos[p[i]]].dis = d[p[i]];
up(pos[p[i]]);
}else   ins(node(p[i],d[p[i]]));
}
}
}
inline void ae(int a,int b,int c){
p[ee] = b;  w[ee] = c;  n1[ee] = h[a];  h[a] = ee ++;
p[ee] = a;  w[ee] = c;  n1[ee] = h[b];  h[b] = ee ++;
}
int merge(int a,int b){
if(!a || !b)    return max(a,b);
if(L[a].d > L[b].d) swap(a,b);
L[a].r = merge(L[a].r,b);
if(D[L[a].r] > D[L[a].l])   swap(L[a].l,L[a].r);
if(L[a].r == 0) D[a] = 0;
else     D[a] = D[L[a].r] + 1;
return a;
}
void dfs(int u,int fa){
dfn[u] = ++ tot;
for(int i = h[u]; ~i;i = n1[i]){
if(p[i] == fa)  continue;
if(path[p[i]] == u){
dfs(p[i],u);
rt[u] = merge(rt[u],rt[p[i]]);
}
}
for(int i = h[u]; ~i;i = n1[i]){
if(p[i] == fa)  continue;
if(path[p[i]] != u){
L[++ cnt] = (lt){0,0,d[u]+w[i]+d[p[i]],p[i]};
rt[u] = merge(rt[u],cnt);
}
}
while(rt[u] && dfn[L[rt[u]].id] >= dfn[u])
rt[u] = merge(L[rt[u]].l,L[rt[u]].r);
An[u] = rt[u] ? L[rt[u]].d - d[u] : -1;
}

int main(){
memset(h,0xff,sizeof(h));
scanf("%d%d",&n,&m);
int u,v,w;
for(int i = 1;i <= m;i ++){
scanf("%d%d%d",&u,&v,&w);
ae(u,v,w);
}
memset(d,63,sizeof(d));
dijkstra(1);
dfs(1,0);
for(int i = 2;i <= n;i ++)  printf("%d\n",An[i]);
return 0;
}

## BSOJ3701--【USACO 2012 Open】Bookshelf

Description
When Farmer John isn't milking cows, stacking haybales, lining up his cows, or building fences, he enjoys sitting down with a good book. Over the years, he has collected N books (1 <= N <= 2,000), and he wants to build a new set of bookshelves to hold them all.

Each book i has a width W(i) and height H(i). The books need to be added to a set of shelves in order; for example, the first shelf should contain books 1...k for some k, the second shelf should start with book k+1, and so on. Each shelf can have a total width of at most L (1 <= L <= 1,000,000,000). The height of a shelf is equal to the height of the tallest book on that shelf, and the height of the entire set of bookshelves is the sum of the heights of all the individual shelves, since they are all stacked vertically.

Input
* Line 1: Two space-separated integers: N and L.

* Lines 2..1+N: Line i+1 contains two space-separated integers: H(i) and W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Output
* Line 1: The minimum possible total height for the set of bookshelves.
Sample Input
5 10
5 7
9 2
8 5
13 2
3 8

INPUT DETAILS:

There are 5 books. Each shelf can have total width at most 10.
Sample Output
21

OUTPUT DETAILS:

There are 3 shelves, the first containing just book 1 (height 5, width 7), the second containing books 2..4 (height 13, width 9), and the third containing book 5 (height 3, width 8).

【Silver难度】：N<=2000

【Gold难度】：N<=100000