[HNCPC2017 D]Tian Ji's Horse Race Again
题意：田忌和国王有n匹马，马的速度互不相同。比赛规则是双方每次必须派出最快的马，并且每匹马只能被派出一次。速度高的获胜。 由于田忌马太菜了，国王允许田忌和自己换最多k匹马（这2k匹马由田忌决定） 问田忌最多赢多少次。
m组询问，\(n,m\le 10^5\)
最多200组数据,输入文件大小不超过8MB，2s。
显然每次交换一定是用自己最差的换国王最好的。
假算法：二分+主席树
对于第k强的马，在一次次交换后田忌这边这匹马的速度只会越来越快，国王那边只会越来越慢。
二分第几次之后这个第k强的马能赢。显然第x次交换后，田忌的马是田忌原来前n-x快的和国王前x快的，其它是国王的，这个第k强可以用主席树。
时间复杂度\(O(n \log ^2 n)\) 需要4.4s。
真算法 贪心+Two Pointers
输入已经按速度降序排序了...
对于田忌的每匹马，可以计算出至少后移到哪里能赢对面的马。认为对面有一匹马（第n+1匹）速度为0。
这个可以直接Two-Pointers O(n)解决。
考虑每一次交换，把自己最差一匹马放到对面，可以认为是把对面的其它马排名提高，把对面最强一匹放到自己这边，可以认为是把自己其它马排名降低。
什么？插中间怎么办？
以把自己的放对面为例，其它马显然都能赢这匹马，放对面后，这匹马都不可能赢，比它差的也一样，所以放最后面也一样。
那就相当于把每匹马位置后移两次。所以最少次数就是最少右移的位数除2上取整。
然后
什么？n+1匹是啥意思？
如果你后移到了第n+1匹，说明你碰到了本来比你差换过去的....那显然能赢。
继续移更会赢，所以就是可以直接桶排前缀和。
时间复杂度\(O(n)\)
/*
Author: CNYALI_LK
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
int read(){
int s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
int a[204847],b[204847],cnt[204847];
int main(){
#ifdef cnyali_lk
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
#endif
int n,m;
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;++i)b[i]=read();
b[n+1]=0;
for(int i=1;i<=n;++i)a[i]=read();
int j=n+1;
for(int i=0;i<=n;++i)cnt[i]=0;
for(int i=n;i;--i){
while(j>i && b[j-1]<a[i])--j;
++cnt[(j-i+1)/2];
}
for(int i=1;i<=n;++i)cnt[i]+=cnt[i-1];
for(;m;--m){
printf("%d\n",cnt[read()]);
}
}
return 0;
}