「2017 山东一轮集训 Day2」Pair 题解

注意：题目统计的是 ${a_i}$ 的连续子序列，必须连续。

思路

首先可以贪心得到，对于两个长度相同的数列，一个升序排列，另一个降序排列后两两配对的和的最小值最大，那么再这题中由于要所有数对的和都 $\ge h$，所以我们先将数列 ${b_i}$ 降序排列。

那么对于一个 $a_i$，可以和它匹配的 $b_i$ 一定是数列 ${b_i}$ 的一个前缀，其中所有数都 $\ge h-a_i$，所以设 $p_i$ 表示数列 ${b_j}$ 中最后的可以和 $a_i$ 匹配的 $j$，那么当 $a_i$ 和合法时，设它的位置为 $k$，有 $p_i-k\ge 0$。

那么我们可以开一颗平衡树，动态维护当前的连续子数列的 $p_i-k$，判断最小的 $p_i-k$ 是否非负即可。

一些细节

$p_i$ 可以二分求。

在平衡树中将一个数换为另一个数后相当于将这两个数之间的数的 $p_i-k\pm1$。

代码

#include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
int m,n,h,a[150010],b[150010],rt,id,p[150010],c[150010];
bool cmp(int a,int b){
	return a>b;
}
mt19937 rd(999983);
struct N{//平衡树 
	int ls,rs,v,rd,sz,k,mn,la;
	//v：节点本身的权值
	//k：节点本身的p[i]-k
	//mn：子树中最小的p[i]-k 
}tr[300010];
int nd(int v,int k){
	tr[++id]={0,0,v,rd(),1,k,k,0};
	return id;
}
void pushup(int p){
	tr[p].sz=tr[lc(p)].sz+tr[rc(p)].sz+1;
	tr[p].mn=tr[p].k;
	if(lc(p))tr[p].mn=min(tr[p].mn,tr[lc(p)].mn);
	if(rc(p))tr[p].mn=min(tr[p].mn,tr[rc(p)].mn);
}
void pushdown(int p){
	if(tr[p].la){
		tr[lc(p)].k+=tr[p].la;
		tr[lc(p)].mn+=tr[p].la;
		tr[lc(p)].la+=tr[p].la;
		tr[rc(p)].k+=tr[p].la;
		tr[rc(p)].mn+=tr[p].la;
		tr[rc(p)].la+=tr[p].la;
		tr[p].la=0;
	}
}
void split(int p,int v,int &x,int &y){
	if(!p){
		x=y=0;
		return ;
	}
	pushdown(p);
	if(tr[p].v<=v){
		x=p;
		split(rc(p),v,rc(p),y);
	}
	else{
		y=p;
		split(lc(p),v,x,lc(p));
	}
	pushup(p);
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	if(tr[x].rd<tr[y].rd){
		pushdown(x);
		rc(x)=merge(rc(x),y);
		pushup(x);
		return x;
	}
	else{
		pushdown(y);
		lc(y)=merge(x,lc(y));
		pushup(y);
		return y;
	}
}
int fdrk(int v){//有多少<=v的数 
	int x,y;
	split(rt,v,x,y);
	int ans=tr[x].sz;
	rt=merge(x,y);
	return ans;
}
void ins(int v,int k){//插入一个v（在所有v的后面） 
	int x,y;
	split(rt,v,x,y);
	rt=merge(merge(x,nd(v,k)),y);
}
void dfsd(int &p,int fl){//删除当前子树最左边/最右边的点 （p[i]-k最大/最小） 
	if(fl&&!rc(p)){
		tr[p].v=0;
		p=lc(p);
		return ;
	}
	if(!fl&&!lc(p)){
		tr[p].v=0;
		p=rc(p);
		return ;
	}
	if(fl)dfsd(rc(p),fl);
	else dfsd(lc(p),fl);
	pushup(p);
}
void del(int v,int fl){//删去最左边/最右边的v 
	int x,y,z;
	split(rt,v,x,y);
	split(x,v-1,x,z);
	dfsd(z,fl);
	rt=merge(merge(x,z),y);
}
void change(int l,int r,int v){//将l~r的数的p[i]-k+=v 
	int x,y,z;
	split(rt,r,x,y);
	split(x,l-1,x,z);
	tr[z].la+=v;tr[z].k+=v;tr[z].mn+=v;
	rt=merge(merge(x,z),y);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>m>>n>>h;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)cin>>b[i];
	sort(a+1,a+1+n,cmp);//降序排序 
	for(int i=1;i<=m;i++)c[i]=b[i];
	sort(b+1,b+1+n);//先给1~n升序排序 
	for(int i=1;i<=m;i++){
		int l=0,r=m;//计算p[i] 
		while(l<r){
			int mid=(l+r+1)>>1;
			if(b[i]+a[mid]>=h)l=mid;
			else r=mid-1;
		}
		p[i]=l;
	}
	for(int i=1;i<=n;i++){//先将1~n插入平衡树 
		ins(b[i],p[i]-i);
	}
	int ans=0;
	ans+=tr[rt].mn>=0;//记录答案 
	for(int i=n+1;i<=m;i++){
		int x=c[i-n],y=b[i];//x：被替换的数，y：新加入的数 
		if(x<y){//新加入的数比被替换的数大 
			del(x,1);change(x+1,y,1);//删去x中最右边的x，将x+1~y的p[i]-k统一+1 
			int rk=fdrk(y)+1;//把y插入y的末尾 
			ins(y,p[i]-rk);
		}
		else if(x>y){//新加入的数比被替换的数小 
			del(x,0);//删去最左边的x 
			change(y+1,x-1,-1);//将y+1~x-1的p[i]-k统一-1 
			int rk=fdrk(y)+1;//把y插入y的末尾  
			ins(y,p[i]-rk);
		}
		ans+=tr[rt].mn>=0;//累计答案 
	}
	cout<<ans;
	return 0;
}