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);
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<set> 7 using namespace std; 8 const int N=1e6+7; 9 int ct[N]; 10 bool visit[N]; 11 int n,m,temp; 12 int ps[N]; 13 long long ans; 14 int lowbit(int x){ 15 return x&(-x); 16 } 17 void add(int x){ 18 while(x<=n){ 19 ct[x]++; 20 x+=lowbit(x); 21 } 22 } 23 int sum(int x){ 24 int ans=0; 25 while(x>0){ 26 ans+=ct[x]; 27 x-=lowbit(x); 28 } 29 return ans; 30 } 31 int main(){ 32 while(~scanf("%d%d",&n,&m)){ 33 memset(ct,0,sizeof(ct)); 34 memset(ps,0,sizeof(ps)); 35 memset(visit,0,sizeof(visit)); 36 for(int i=1;i<=n;i++){ 37 scanf("%d",&temp); 38 ps[temp]=i; 39 } 40 for(int i=1;i<=m;i++){ 41 scanf("%d",&temp); 42 visit[temp]=1; 43 } 44 ans=0; 45 set<int>Q;int l,r; 46 for(int i=1;i<=n;i++){ 47 if(visit[i]==1){ 48 Q.insert(ps[i]); 49 } 50 else{ 51 set<int>::iterator it=Q.lower_bound(ps[i]); 52 if(it==Q.end()){ 53 if(Q.size()==0){ 54 r=n; 55 l=1; 56 } 57 else{ 58 r=n; 59 l=(*(--it))+1; 60 } 61 } 62 else if(it==Q.begin()){ 63 l=1; 64 r=(*it)-1; 65 } 66 else{ 67 r=(*it)-1; 68 l=(*(--it))+1; 69 } 70 // printf("%d %d %d ",i,l,r); 71 ans+=r-l+1; 72 ans-=sum(r); 73 ans+=sum(l-1); 74 add(ps[i]); 75 } 76 } 77 printf("%I64d ",ans); 78 } 79 }