链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1287
思路：二分查找大于等于b[i]的最前面的位置（想起一次错漏百出的网赛中一道没在比赛A掉的题），并更新线段树，总复杂度nlogn。
我并不是停留在舒适区，而是找回当年因为死套模板而没有去深刻理解的东西，下次再接触到这些东西的时候只能称呼你们学长学姐了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 3;
struct node
{
int l,r;
int val;
}q[N<<2];
int a[N],b[N];
void built(int l,int r,int pos)
{
q[pos].l = l;
q[pos].r = r;
if(l == r)
{
q[pos].val = a[l];
return;
}
int mid = (l + r) >> 1;
built(l,mid,2*pos);
built(mid+1,r,2*pos+1);
q[pos].val= max(q[2*pos].val,q[2*pos+1].val);
}
void update(int i,int pos)
{
if(q[pos].l == q[pos].r)
{
q[pos].val++;
return;
}
int mid = (q[pos].l + q[pos].r) >> 1;
if(i > mid)
update(i,2*pos+1);
else
update(i,2*pos);
q[pos].val= max(q[2*pos].val,q[2*pos+1].val);
}
int get_id(int val,int pos)
{
if(q[pos].l == q[pos].r)
{
if(val > q[pos].val)
return 0;
return q[pos].l;
}
if(val > q[2*pos].val)
return get_id(val,2*pos+1);
else
return get_id(val,2*pos);
}
int main()
{
int m,n;
scanf("%d %d",&m,&n);
for(int i = 1; i <= m; i++)
scanf("%d",&a[i]);
for(int i = 1; i <= n; i++)
scanf("%d",&b[i]);
built(1,m,1);
for(int i = 1; i <= n; i++)
{
int id = get_id(b[i],1);
if(id > 1)
{
a[id-1]++;
update(id-1,1);
}
}
for(int i = 1; i <= m; i++)
printf("%d\n",a[i]);
return 0;
}
原文：http://www.cnblogs.com/westwind1005/p/6481619.html