双指针&位运算&离散化&区间合并

89 阅读 0 评论 59 点赞

我是靠谱客的博主炙热秀发，这篇文章主要介绍双指针&位运算&离散化&区间合并，现在分享给大家，希望可以做个参考。

双指针

双指针核心，利用某种性质降低时间复杂度。一般可以将O(n²)降为O(n)。这里的指针并不是指针变量。通常来说，我们首先，先想出一个暴力方案，重点利用指针i，j的单调性关系对它进行优化。
模板：

复制代码

1
2
3
4
5
for(int i=0,j=0;i<n;i++){
while(j<i && check(i,j)) j++;
//这道题的逻辑
}

结合一个具体例题来讲解：最长连续不重复子序列

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn],n,s[maxn],ans;
int main(){
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0,j=0;i<n;i++){
s[a[i]] ++;
while(j<i && s[a[i]] > 1){
s[a[j]]--;
j++;
}
ans = max(ans,i-j+1);
}
cout<<ans<<endl;
return 0;
}

1.整体思路，让指针i遍历整数序列，当区间中有重复元素时移动指针j。指针i，j的移动一定是单向的。像这样，i，j一共最多只需要2*n次就可以得出结果，因此时间复杂度是O(n)。
下面两个技巧可以提炼：
2.数组s，用于判断当前区间中，每个元素出现的次数。
3.ans用来存放结果。

位运算

位运算包含<<（左移），>>（右移），&(按位与)，^（按位或）。常用的操作如下：

复制代码

1
2
3
4
5
6
7
8
9
10
int x;
x >> k & 1;//取x的第k位，最低位记为第0位。
//返回最末尾的1
int lowbit(int x){ return (x&(-x)); }
/*
eg. x = (101000)2;
y = lowbit(x);
输出结果： y = (1000)2;
*/

结合一道例题，二进制中1的个数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int n;
int lowbit(int x){
return (x & -x);
}
int main(){
cin>>n;
while(n--){
int k,cnt=0;
scanf("%d",&k);
while(k) k -= lowbit(k), cnt++ ;
printf("%d ",cnt);
}
return 0;
}

离散化

离散化是一种映射，To be specific,有一组数据1,20,300,6000,100000。它们在数轴上相距较远，通过离散化将它们映射成距离较近的位置。先上例题：区间和

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<vector>
#include<utility> //pair 头文件
#include<algorithm>
using namespace std;
const int maxn = 3e5 + 10;
typedef pair<int,int> PII;
vector<int> alls;
vector<PII> add,query; //vector嵌套型数组
int n , m;
int a[maxn] , s[maxn];
int find(int x){ //二分映射
int l = 0,r = alls.size() - 1 ;
while(l < r){
int mid = (l + r) >> 1;
if(alls[mid] >= x) r = mid ;
else l = mid + 1;
}
return r + 1 ;
}
int main(){
cin>>n>>m;
while(n--){
int x ,c;
cin>>x>>c;
alls.push_back(x);
add.push_back({x,c});
}
while(m--){
int l , r;
cin>>l>>r;
alls.push_back(l);
alls.push_back(r);
query.push_back({l,r});
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end()); //vector数组去重。
for(auto item : add){
int x = find(item.first);
a[x] += item.second;
}
for(int i = 1;i <= alls.size() ; i++) s[i] = s[i-1] + a[i] ;
for(auto item : query){
int l = find(item.first), r = find(item.second);
cout<<s[r] - s[l-1]<<endl;
}
return 0;
}

如果纯属是为了解题的话，写这么长纯属没必要用哈希更快。但是为了写离散化，咱们还是来看一下，这代码。先讲一下，先序知识：
1.vector数组去重

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<algorithm>
#include<vector>
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end())
/*
函数unique，将重复元素放在高位并返回去重后的尾地址。它只对相邻元素去重，如果元素无序，需要排序。
eg. a = [1 , 2 ,
2 ,4 , 4, 5
];
unique(a);
a = [1 2 4 5];实际上数组长度没有变化，这样理解就可以了。
*/

STL容器的嵌套

复制代码

1
2
3
4
typedef pair<int , int> PII;
vector<PII> a;
// a用first和second访问元素。eg.a[i].first，a[i].second;

for循环

复制代码

1
2
3
for(auto a:b) //利用a访问b的每一个值，和python的语法类似
//用在STL中极为方便。

对于这个题呢，由于给出的区间过大，不能直接用前缀和处理。因此，将x以及l，r；进行映射。映射之前，要去重并且要将x，l，r一起映射，这样才能明确表示它们之间的大小关系。最后利用前缀和。

区间合并

区间合并，就是将有交点的，离散的小区间合并。
例题：区间合并

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
const int maxn = 1e9;
typedef pair<int,int> PII;
vector<PII> a;
int n;
vector<PII> merge(){
vector<PII> ans;
int st = maxn * (-2),ed = st; //当前处理的区间
for(auto c:a){
if(ed < c.first){ //第一个无法合并区间
if(st != -2 * maxn) ans.push_back({st,ed});
st = c.first , ed = c.second; //更新区间
}
else ed = max(ed,c.second); //可以合并，合并右端点。
}
if(st != maxn*(-2)) ans.push_back({st,ed});
return ans ;
}
int main(){
cin>>n;
while(n--){
int l , r;
cin>>l>>r;
a.push_back({l,r});
}
sort(a.begin(),a.end());//将区间按照做端点升序排序
a = merge();
cout<<a.size()<<endl;
return 0;
}