http://codeforces.com/contest/387/problem/E
题意：给你n个数，然后在输入k个数，这k个数都在n个数中出现，进行每一次操作就是在n个数中选择长度为w的连续序列，然后删除这w个数中的最小的一个，然后你就会的到w个奖励，如何获得最多奖励？
思路：set+数状数组，数状数组用来记录在每一个连续的区间内数的个数，用来记录删除和添加数的个数，先对a数组中的数记录每一个数在序列中的位置，再对b数组进行标记，然后遍历1-n，被标记数，把它的位置放在set里面，没有被标记的，在set里面二分查找到大于等于它位置的数，可以知道下界和上界，就可以知道这次的w，就可以求出答案。
1 #include <cstdio> 2 #include <cstring> 3 #include <set> 4 #include <algorithm> 5 #define ll long long 6 #define maxn 1000010 7 using namespace std; 8 9 int n,k; 10 int p[maxn]; 11 int b[maxn]; 12 int c[maxn]; 13 int pos[maxn]; 14 bool vis[maxn]; 15 struct node 16 { 17 int x,id; 18 bool operator <(const node &a)const 19 { 20 return x<a.x; 21 } 22 } f[maxn]; 23 24 int lowbit(int x) 25 { 26 return x&-x; 27 } 28 29 void insert(int x,int d) 30 { 31 while(x<maxn) 32 { 33 c[x]+=d; 34 x+=lowbit(x); 35 } 36 } 37 38 int Getsum(int x) 39 { 40 int ans=0; 41 while(x>0) 42 { 43 ans+=c[x]; 44 x-=lowbit(x); 45 } 46 return ans; 47 } 48 49 50 int main() 51 { 52 while(scanf("%d%d",&n,&k)!=EOF) 53 { 54 set<int>q; 55 set<int>::iterator it; 56 for(int i=1; i<=n; i++) 57 { 58 scanf("%d",&p[i]); 59 insert(i,1); 60 pos[p[i]]=i; 61 } 62 for(int i=1; i<=k; i++) 63 { 64 scanf("%d",&b[i]); 65 vis[b[i]]=true; 66 } 67 ll ans=0; 68 q.insert(0); q.insert(n+1); 69 for(int i=1; i<=n; i++) 70 { 71 if(vis[i]) 72 { 73 q.insert(pos[i]); 74 } 75 else 76 { 77 it=q.lower_bound(pos[i]); 78 int r=*it-1; 79 int l=*(--it); 80 ans+=Getsum(r)-Getsum(l); 81 insert(pos[i],-1); 82 } 83 } 84 printf("%lld ",ans); 85 } 86 return 0; 87 }