双指针 区间合并 离散化
双指针通俗理解
- 前缀和听起来好高级啊，那么他究竟是什么啊？
双指针是通过某些方式优化复杂度，从而实现。
接下来看几道栗子吧
双指针
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤10^5
输入样例：
5
1 2 2 3 5
输出样例：
3
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N],cnt[N];
void solve()
{
int n;
cin >> n;
int ans = 0;
for(int i = 1; i<=n; i++) cin >> a[i];
for(int r = 1,l = 1; r<=n; r++)
{
cnt[a[r]]++;;
while(cnt[a[r]]>=2) cnt[a[l++]]--;
ans=max(ans,r-l+1);
}
cout << ans <<endl;
}
signed main()
{
solve();
return 0;
}
再来看看另一种形式的双指针
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 mm 的整数序列 b1,b2,…,bm
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。
输入格式
第一行包含两个整数 n,m
第二行包含 n 个整数，表示 a1,a2,…,an
第三行包含 m 个整数，表示 b1,b2,…,bm
输出格式
如果 a 序列是 b 序列的子序列，输出一行 Yes。
否则，输出 No。
数据范围
1≤n≤m≤10^5
−109≤ai,bi≤109
输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
Yes
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
void solve()
{
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 i = 1,j = 1;;
while(i<=n&&j<=m)
{
if(a[i]==b[j]) i++;
j++;
}
if(i==n+1) cout <<"YES"<<endl;
else cout <<"NO"<<endl;
}
signed main()
{
solve();
return 0;
}
区间合并
标题如其名，就是合并不同区间
给定 n 个区间 [l,r]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000
−109≤l≤r≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int,int>PII;
PII a[N];
bool cmp(PII a,PII b)
{
if(a.first!=b.first) return a.first < b.first;
else return a.second <b.second;
}
void solve()
{
int n;
cin >> n;
for(int i = 1; i<=n; i++) cin >> a[i].first >> a[i].second;
sort(a+1,a+1+n,cmp);
int ans = 1;
int l = a[1].first,r = a[1].second;
for(int i = 2; i<=n; i++)
{
if(r<a[i].first)
{
ans++;
l=a[i].first,r=a[i].second;
}
else r=max(r,a[i].second);
}
cout << ans <<endl;
}
signed main()
{
solve();
return 0;
}
离散化
离散化就是将大的空间映射到小的空间里面去，减小空间消耗。
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109
1≤n,m≤10^5
−109≤l≤r≤109
−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int,int>PII;
int s[N];
PII a[N];
PII que[N];
vector<int>lsh;
int find(int x)
{
return lower_bound(lsh.begin(),lsh.end(),x)-lsh.begin()+1;
}
void solve()
{
int n,m;
cin >> n >> m;
for(int i = 1; i<=n; i++)
{
int x,y;
cin >> x >> y;
a[i]={x,y};
lsh.push_back(x);
}
for(int i = 1; i<=m; i++)
{
int l,r;
cin >> l >> r;
que[i]={l,r};
lsh.push_back(l);
lsh.push_back(r);
}
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
for(int i = 1; i<=n; i++)
{
int t = find(a[i].first);
s[t]+=a[i].second;
}
for(int i = 1; i<=lsh.size(); i++) s[i]+=s[i-1];
for(int i = 1; i<=m; i++)
{
int l = find(que[i].first),r = find(que[i].second);
cout << s[r]-s[l-1] <<endl;
}
}
signed main()
{
solve();
return 0;
}