Codeforces 387(#227 Div2 only) E. George and Cards

問題

n枚のカードがあって、それぞれには1〜nの異なる整数どれかが書かれている。
何回でも次のような操作をすることができる。

  • 残っているカードのうち連続するw枚のカードを選ぶ
  • 数字が最小のカードを捨てる
  • w点をもらう


操作を終えた後のカードの状態が与えられるとき、
そのような状態を実現するカードの取り方のうち、得られる得点が最大であるような取り方の得点を求めよ。

制約条件

n≦10^6
カードの整数は全部違う

方針

操作は区間のうち最小のカードを取り除くので、大きいカードは残っていても得点が増えるだけ。
つまり小さいカードから取り除いていくのが最良。


取り除くカードを決めたら、左右どこまで区間が伸ばせるかがわかればよい。
これは、自分より小さいカードにぶつかるまで。
setとかbinary indexed treeとかを使えばO(log n)でわかる。


区間がわかったら、その区間のうちまだ取り除いてないカードの枚数を答えに足す。
これは、取り除いてないカードをbinary indexed treeなどで持つことでO(log n)でわかる。

ソースコード

const int MX = 1048576; //1 << 20
int smaller[MX], remain[MX];

inline void add(int *bit, int i, int x){
	for(++i; i < MX; i += i & -i) bit[i] += x;
}
inline int sum(int *bit, int i){
	int res = 0;
	for(++i; i; i -= i & -i) res += bit[i];
	return res;
}
//sum(x) >= kとなる最小のxを返す
//(今回はbinary indexed treeが内部で1-originなので1を引いている)
inline int find(int *bit, int k){
	int lo = 0, hi = MX, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(bit[mid] >= k) hi = mid;
		else lo = mid, k -= bit[mid];
	}
	return hi - 1;
}

ll ans;
int n, m, a[MX], b[MX];
bool isremain[MX];

int main(){
	
	scanf("%d%d", &n, &m);
	rep(i, n) scanf("%d", a + i);
	rep(i, m) scanf("%d", b + i), isremain[b[i]] = 1;
	
	priority_queue<pi> q_remain, q_notremain;
	
	rep(i, n){
		if(!isremain[a[i]]) q_notremain.push(mp(-a[i], i));
		else q_remain.push(mp(-a[i], i));
	}
	
	rep(i, n) add(remain, i, 1);
	
	while(!q_notremain.empty()){
		
		int cur = -q_notremain.top().first;
		int idx = q_notremain.top().second;
		q_notremain.pop();
		
		while(q_remain.size() && -q_remain.top().first < cur){
			
			add(smaller, q_remain.top().second, 1);
			q_remain.pop();
		}
		
		
		int cur_cnt = sum(smaller, idx);
		int left = find(smaller, cur_cnt);
		int right = min(find(smaller, cur_cnt + 1), n);
		
		if(a[left] < a[idx]) left++;
		
		ans += sum(remain, right - 1) - sum(remain, left - 1);
		
		add(remain, idx, -1);
	}
	
	cout << ans << endl;
	
	return 0;
}