Skip to main content

双指针

参考资料​

例题​

洛谷 P1102 A-B 数对​

洛谷 P1102 A-B 数对

给出一串正整数数列以及一个正整数 CC，要求计算出所有满足 A−B=CA - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

Code (1)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,c;
	cin>>n>>c;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	ll ans=0;
	int l=1,r=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=a[i-1])
		{
			l=r;
			while(l<=n&&a[l]<a[i]+c)l++;
			r=l;
			while(r<=n&&a[r]==a[i]+c)r++;
		}
		ans+=r-l;
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P1366 有序表的合并​

洛谷 P1366 有序表的合并

给出两个数列 a,ba,b，均按不降序排序。其中保证 aa 中没有重复的数字。

现在请你求出：aa 中每一个数字在 bb 中出现了几次？

Solution

参考资料​

解题思路​

初始时，令左右边界 l=r=1l=r=1。

对于每个元素 aia_i，执行以下操作：

  1. 将区间左边界 ll 从 rr 开始向后枚举，直到 bl=aib_l=a_i（l≤ml\le m），说明 blb_l 是第一个等于 aia_i 的元素。
  2. 将区间右边界 rr 从 ll 开始向后枚举，直到 br≠aib_r\ne a_i（r≤mr\le m），说明 brb_r 是第一个不等于 aia_i 的元素。
  3. 此时 l−rl-r 即为 aia_i 出现的个数。

最后求出所有数的异或和。

参考代码​

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
const int N=10000005;
ull a[N],b[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=m;i++)cin>>b[i];
		int l=1,r=1,ans=0;
		for(int i=1;i<=n;i++)
		{
			l=r;
			while(l<=m&&b[l]<a[i])l++;
			r=l;
			while(r<=m&&b[r]==a[i])r++;
			ans^=r-l;
		}
		cout<<ans<<'\n';
	}
	return 0;
}