PKU 3250 Bad Hair Day

問題:

3250 -- Bad Hair Day

問題概要:

牛さんが右向きで並んでる。

それぞれの牛について、自分より右方向かつ自分が見渡すことの出来る範囲(=自分より厳密に小さいやつしかいない範囲)にいる牛の数を数え、それを合計したものを出力する。アスキーアート図参照。

解法:

禿日とか呼んでごめんなさい。

スタックでも出来るらしいけど、BITでも十分速そうだし実装してから気づいたのでBITでやりました。

要するにある牛が見れる範囲ってのは、右から見ていって今までに出てきた牛の中で「自分より大きい牛のうち、自分に最も近い牛」なので、高さとかでBITしてやってよい。

座標圧縮はもちろんする。とりあえずBITのデータ構造反転させるために怪しいこととかをしている。(常套手段)

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

typedef unsigned int uint;
int in() {
    int x = 0, c;
    for (; (uint)((c = getchar()) - '0') >= 10; ) { if (c == '-') return -in(); if (!~c) throw ~0; }
    do { x = (x << 3) + (x << 1) + (c - '0'); } while ((uint)((c = getchar()) - '0') < 10);
    return x;
}

int bit[80081] , n , input[80001] , num[80001];


inline void add(int x, int val){
	x = n + 50 - x;
	
	while(x <= n + 50){
		bit[x] = max(bit[x],val);
		x += x & -x;
	}
}
inline int get(int x){
	x = n + 50 - x;
	int ans = -999;
	while(x){
		ans = max(bit[x],ans);
		x -= x & -x;
	}
	return ans;
}

int main(){
	n = in();
	for(int i = 0 ; i < n ; i++){
		input[n-i-1] = num[i] = in();
	}
	for(int i = 0 ; i <= n+50 ; i++) bit[i] = -1;
	
	long long ans = 0;
	sort(num,num+n);
	
	for(int i = 0 ; i < n ; i++){
		int value = lower_bound(num,num+n,input[i]) - num + 1;
		ans += i - get(value) - 1;
		add(value,i);
	}
	cout << ans << endl;
}