题目链接：Codeforces 387E George and Cards
题目大意：给出一个长度为n的序列，然后在给出一个长度为k的条件序列，要求将原先的删除n-k个后得到的序列满足条件序列，条件序列b[i]，表示序列的前i个元素中必须包含有b[i]这个数。删除操作，选取一个区间，删除中间的最小值，并且获得相应的区间长度的什么奖励，问说最多可以获得多少奖励（奖励啥看不懂）。
解题思路：二分+树状数组。首先，可以分析的出结论，b数组即为原先数组删除n-k个后的目标数组（想一下就知道的b[1]的位置肯定是放值为b[1]的卡片，那么值为b[2]的卡片就只能放在2上，以次类推）；其次，为了得到尽量多的奖励，在删除元素时选取的区间就要尽量长，不仅如此，在删除元素时也要从小的开始删除，因为删除大的会导致删除小的时候区间长度的缩短；这样的话就可以通过将序列每个数按照从小到大的顺序将位置放入set中，碰到需要删除的元素就去二分上下限。知道上下限就可以通过BIT求得中间存在元素的个数。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <set>
using namespace std;
const int N = 1000005;
typedef long long ll;
int n, k, p[N], b[N];
ll v[N];
void add(int x, ll val) {
while (x <= n) {
v[x] += val;
x += (x & (-x));
}
}
ll sum(int x) {
ll ans = 0;
while (x > 0) {
ans += v[x];
x -= (x & (-x));
}
return ans;
}
void init() {
int a;
memset(b, 0, sizeof(b));
memset(v, 0, sizeof(v));
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
p[a] = i;
add(i, 1);
}
for (int i = 1; i <= k; i++) {
scanf("%d", &a);
b[a] = 1;
}
}
ll solve() {
set<int> s;
set<int>::iterator iter;
ll ans = 0;
s.insert(0); s.insert(n+1);
for (int i = 1; i <= n; i++) {
if (b[i]) {
s.insert(p[i]);
continue;
}
iter = s.upper_bound(p[i]);
int r = *iter - 1;
int l = *(--iter);
ans += sum(r) - sum(l);
add(p[i], -1);
}
return ans;
}
int main() {
init();
cout << solve() << endl;
return 0;
}