可算是给我来道水题了。

我这里有一个很玄学的思路，但是这题的思路应该都很玄学吧。

首先给 $b$ 数组排个序。然后我们建立一个 $c$ 数组，$c[i]$ 表示最小的满足 $b[x]+a[i] \ge h$ 的 $x$。

对于每一个连续子序列的匹配，最优的匹配情况肯定是将 $a$ 对应的区间倒序排序，$b$ 数组正序排序后一一匹配。如果这个都没法匹配那就肯定没有匹配方案了。

先记 $d[i]$ 为 $i$ 在这个区间内出现的次数，由刚刚那个匹配方案得：

不然就无法匹配。

那么我们就考虑开棵线段树记录目前区间每个数的出现次数的前缀和就行了，一开始每个位置先减去对应的值即可。很明显这是一道区间修改维护区间最小值的题目，甚至我们只需要查询 $1$ 节点的权值就行。

哦还有无法和 $b$ 数组中的任意一个数匹配的数，这种直接记录这类数的个数，有的话就无法匹配。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10; 
int a[N],b[N],n,m,p,d[N],s[N];
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
struct SMTree
{
	struct node{int l,r,mn,tag;}tr[N<<2];
	void pushup(int p){tr[p].mn=min(tr[lc(p)].mn,tr[rc(p)].mn);}
	void pushdown(int p)
	{
		if(tr[p].tag)
		{
			tr[lc(p)].mn+=tr[p].tag;
			tr[rc(p)].mn+=tr[p].tag;
			tr[lc(p)].tag+=tr[p].tag;
			tr[rc(p)].tag+=tr[p].tag;
			tr[p].tag=0;
		}
	}
	void bt(int p,int l,int r)
	{
		tr[p]={l,r,0,0};
		if(l==r){tr[p].mn=s[l]-l;return;}
		int mid=(l+r)>>1;
		bt(lc(p),l,mid);bt(rc(p),mid+1,r);
		pushup(p);
	}
	void add(int p,int l,int r,int k)
	{
		if(tr[p].l>r||tr[p].r<l)return ;
		if(l<=tr[p].l&&tr[p].r<=r)
		{
			tr[p].mn+=k;
			tr[p].tag+=k;
			return;
		}
		pushdown(p);
		add(lc(p),l,r,k);add(rc(p),l,r,k);
		pushup(p);
	}
}tr;
signed main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=m;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	sort(a+1,a+m+1);
	for(int i=1;i<=n;i++)b[i]=lower_bound(a+1,a+m+1,p-b[i])-a;
	for(int i=1;i<=m;i++)d[b[i]]++;
	for(int i=1;i<=m;i++)s[i]=s[i-1]+d[i];
	int vsum=d[m+1];
	tr.bt(1,1,m);
	int ans=(!vsum&&tr.tr[1].mn>=0);
	for(int i=m+1;i<=n;i++)
	{
		if(b[i-m]==m+1)vsum--;
		else tr.add(1,b[i-m],m,-1);
		if(b[i]==m+1)vsum++;
		else tr.add(1,b[i],m,1);
		ans+=(!vsum&&tr.tr[1].mn>=0);
	}
	cout<<ans;
	return 0;
}

「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;
}