Codeforces Round #227 (Div. 2) E:http://codeforces.com/contest/387/problem/E
题意：给你一个n个数的序列，然后给你一个标准序列，现在然后删除原序列的一些数，让原序列变成标准序列。其中，每次查询可以选择一个连续的序列，然后要删除的数字必须是这个序列中的最小的那个。每一次删除，你可以获得这个长度的价值，问你最多可以得到多少价值。
题解：首先，很明显，每次删除要从要删除的数中选择最小的来删除，而且每次删除就是以包含这个数为最小数的最大串。关键是怎么找到这个串。观察可以知道，举个例子，
14 6
7 6 10 9 11 8 14 3 1 13 12 4 5 2
7 10 11 12 4 5
假如说我们要删除8，那么肯定要找离8最近的并且比8小的，没有被删除的数的位子。得到这个区间之后，那么肯定是都是要删除的，要么事已经删除的，要么是没有删除的，那么真正的长度就是去掉那些删除元素的留下来长度。有了这些结论和想法之后。可以想到。每次从最小的数开始，用一个set维护不需要被删除的数的位子。如果当前的数是不要被删除的，那么就把这个数的位子放进set，然后如果这个数是要被删除的，就从set中找到比当前数位子大的位子，因为set中存的是比当前数小并且是不要被删除数的位子。所以lower_bound（ps[i]）,得到是ps[i]右边最近的比i小不用被删除的数的位子，左移一位，那么得到就是ps[i]左边最近的比i小的不用被删除的数的位子。然后得到这个区间了，至于，那么已经被删除元素的，可以用树状数组来统计，都是log(n),总的复杂度nlog(n);
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
const int N=1e6+;
int ct[N];
bool visit[N];
int n,m,temp;
int ps[N];
long long ans;
int lowbit(int x){
return x&(-x);
}
void add(int x){
while(x<=n){
ct[x]++;
x+=lowbit(x);
}
}
int sum(int x){
int ans=;
while(x>){
ans+=ct[x];
x-=lowbit(x);
}
return ans;
}
int main(){
while(~scanf("%d%d",&n,&m)){
memset(ct,,sizeof(ct));
memset(ps,,sizeof(ps));
memset(visit,,sizeof(visit));
for(int i=;i<=n;i++){
scanf("%d",&temp);
ps[temp]=i;
}
for(int i=;i<=m;i++){
scanf("%d",&temp);
visit[temp]=;
}
ans=;
set<int>Q;int l,r;
for(int i=;i<=n;i++){
if(visit[i]==){
Q.insert(ps[i]);
}
else{
set<int>::iterator it=Q.lower_bound(ps[i]);
if(it==Q.end()){
if(Q.size()==){
r=n;
l=;
}
else{
r=n;
l=(*(--it))+;
}
}
else if(it==Q.begin()){
l=;
r=(*it)-;
}
else{
r=(*it)-;
l=(*(--it))+;
}
// printf("%d %d %d\n",i,l,r);
ans+=r-l+;
ans-=sum(r);
ans+=sum(l-);
add(ps[i]);
}
}
printf("%I64d\n",ans);
}
}