十三、双指针
先想暴力做法，然后根据i,j之间是否存在某种单调关系，进行双指针优化。
核心模板
for(int i=0,j=0;i<n;i++){ while(j<i&&check(i,j)) j++; //具体问题的逻辑 } //常见问题分类： （1）对于一个序列，用两个指针维护一段区间。 （2）对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
例子：
输入n个字符串（不含空格），由空格隔开。每行依次输出每个字符串。
思路：i指针指向字符串第一个字母，j向后寻找空格，如果找到，输出位置i到j的字符串，并将i更新为j（下次从空格位置后找下一个字符串），直到将n个字符串输出。
代码：
题目一
题目链接：799. 最长连续不重复子序列
13.1题目描述
给定一个长度为 n 的整数序列，请找出 最长的不包含重复的数的连续区间，输出 它的长度。
输入格式
第一行包含整数 n 。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例：
5 1 2 2 3 5
输出样例：
3
13.2思路分析
i枚举区间右端点，j枚举区间左端点。枚举所有可能区间，记录满足条件区间长度的最大值。
优化：
i枚举区间右端点，j枚举区间左端点，每次判断[j,i]区间是否满足条件，如果不满足区间就缩短，即j++。记录满足条件区间的最大长度。
对于每次i如果向后移动，则j必定不动或者向后移动，j一定不会向前移动。原因：如果i往后走，假设j往前走，如果找到了满足条件的区间，则这个区间一定满足无重复元素，而且比i在其原来位置找到的区间要长，由于i在原来位置找到最长满足条件区间才向后移，说明原来[j,i]区间就是从j开始到i满足条件的区间长度最大值。若i往后移动，j也往前移动能求得最优区间长度，说明原来[j,i]区间不是i在原位置的区间长度最大（而是[j-x,i]，即j应该在求得[j,i]区间中的j的左边），这就互相矛盾了，所以j只能向后或者不动。
s[]记录a[]中每个数出现的个数
双指针执行具体流程：i每次向后移动，同时记录a[i]的值的出现次数在s[i]中，i向后走的过程中，如果s[a[i]]>1，即当前a[i]位置的数不是第一次出现，出现重复了，此时需要缩小区间，将j指向的数的出现次数-1，移动j指针，将j指针依次向后移动，来找到与a[i]重复的位置，如果j已经越过该位置，说明当前区间无重复元素，s[a[i]]<=1，满足题目要求，j停下，此时继续向后移动i指针，重复上述过程，直到遍历完a[]数组。
13.3代码实现
#include <iostream> #include <algorithm> using namespace std; const int N=100010; int a[N],s[N]; //s[a[i]]存储当前[j,i]区间中a[i]的值出现的次数 int n,ans; int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0,j=0;i<n;i++){ s[a[i]]++; //每次i指向的值的出现次数+1 //循环条件可以不写j<=i，因为j>i时，区间一定满足要求，不会走循环 while(s[a[i]]>1){ //如果此时i指向的值的出现次数>1，说明区间中有重复的值，此时应该缩小区间来去掉重复值 s[a[j]]--; //j指向的元素要出区间,j指向的值的出现次数-1 j++; //j往后移动，缩小区间 } ans=max(ans,i-j+1); //统计出区间长度的最大值 } cout<<ans; return 0; }
题目二
题目链接：800. 数组元素的目标和
13.1题目描述
给定两个升序排序的有序数组 A 和 B ，以及一个目标值 x 。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j) 。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x ，分别表示 A 的长度，B 的长度以及目标值 x 。
第二行包含 n 个整数，表示数组 A 。
第三行包含 m 个整数，表示数组 B 。
输出格式
共一行，包含两个整数 i 和 j 。
数据范围
数组长度不超过 105 。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6 1 2 4 7 3 4 6 8 9
输出样例：
1 1
13.2思路分析
待更~
13.3代码实现
待更~
十四、离散化
对一组值范围比较大而其中出现的数的个数比较少的情况，使用离散化。
第一步，将原数组元素去重；
第二步，用二分来查找每个元素离散化之后的值（离散化后数组元素的下标为离散化后的值，则该数组元素的值为待离散前原数组元素的值）。
unique自己手写思路：
将序列中第一次出现，而且和它前面的数不相等就把这个数拿出来，将所有满足条件的数拿出来即完成了去重。
手写unique函数代码
vector<int> ::iterator unique(vector<int> &a){ int j=0; for(int i=0;i<a.size();i++){ if(!i||a[i]!=a[i-1]){ a[j++]=a[i]; } } //a[0]~a[j-1] 所有a中不重复的数 return a.begin()+j; }
核心模板
unqiue作用：unique(a.begin(),a.end())将a数组去重并且返回去重后数组的尾端点。
vector<int> alls; //存储所有待离散化的值 sort(alls.begin(),alls.end());//将所有值排序 alls.erase(unique(alls.begin(),alls.end()),alls.end()); //去掉重复元素 //二分求出x对应的离散化的值 int find(int x){ //找到第一个大于等于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; //映射1,2,...,n；不+1从0开始映射 }
题目链接：802. 区间和
14.1题目描述
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0 。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c 。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r ，你需要求出在 区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m 。
接下来 n 行，每行包含两个整数 x 和 c 。
再接下来 m 行，每行包含两个整数 l 和 r 。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109,1≤n,m≤105,−109≤l≤r≤109,−10000≤c≤10000
输入样例：
3 3 1 2 3 6 7 5 1 3 4 6 7 8
输出样例：
8 0 5
14.2思路分析
套用模板即可，注意细节。
14.3代码实现 #include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; const int N=300010; typedef pair<int,int> PII; int n,m; int a[N],s[N]; //a[]存储每个数，s[]存储前缀和 vector<int> alls; //存储待离散的值 vector<PII> add,query; //存储操作 //二分查找x离散化后的结果 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; //将x映射成从1开始的下标 } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ int x,c; cin>>x>>c; add.push_back({x,c}); alls.push_back(x); } for(int i=0;i<m;i++){ int l,r; cin>>l>>r; query.push_back({l,r}); alls.push_back(l); alls.push_back(r); } //去重 sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()),alls.end()); //处理插入 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; }
十五、区间合并
将区间按左端点排序。
区间情况数如图三种，第一种和第三种不需要改变原来需要维护的区间，第二种需要把原有区间延长至新的ed。
如果前两种情况都已处理，只剩下第三种情况（区间st比原需维护的区间的ed还要大），原需维护区间不会再与第三种情况的区间及其后面的区间有交集，所以将原需维护的区间放入答案中取，然后将其更新为第三种情况的第一个这样的区间，再进行后续合并操作。
核心模板
//将所有存在交集的区间合并
void merge(vector<PII> &segs){ vector<PII> res; sort(segs.begin(),segs.end()); int st=-2e9,ed=-2e9; //按题目要求设置边界即可 for(auto seg:segs){ if(ed<seg.first){ if(st!=-2e9) res.push_back({st,ed}); st=seg.first,ed=seg.second; } else ed=max(ed,seg.second); } if(st!=-2e9) res.push_back({st,ed}); segs=res; }
题目链接：803. 区间合并
15.1题目描述
给定 n 个区间 [li,ri] ，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的 区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,−109≤li≤ri≤109
输入样例：
5 1 2 2 4 5 6 7 8 7 9
输出样例：
3
15.2思路分析
套用模板即可，注意细节。
15.3代码实现
#include <iostream> #include <utility> #include <algorithm> #include <vector> using namespace std; typedef pair<int,int> PII; const int N=100010; int n; vector<PII> v; //存储每个区间，first为左端点，second为右端点 void merge(vector<PII> &v){ vector<PII> ans; //存储合并后的区间结果 sort(v.begin(),v.end()); //默认按区间左端点（first）从小到大排序 int st=-2e9, ed=-2e9; //设置边界值，即初始化不存在合法区间 //遍历所有区间 for(auto i:v){ //如果是第三种情况，即当前区间的左端点比原维护区间的右端点大，不需要合并 if(ed<i.first){ //要特判，如果是初始化的区间则不放入数组 if(st!=-2e9){ ans.push_back({i.first,i.second}); } st=i.first,ed=i.second; //将需维护区间更新为当前枚举的区间 } //如果是第二种情况，说明区间有交集，则将原需维护区间的右端点和枚举区间的右端点取max else ed=max(ed,i.second); } //防止输入的为空数组，需特别判断一下 if(st!=-2e9) ans.push_back({st,ed}); v=ans; } int main(){ cin>>n; for(int i=0;i<n;i++){ int l,r; cin>>l>>r; v.push_back({l,r}); } merge(v); cout<<v.size(); return 0; }
以下内容为拓展内容
十六、树状数组（了解）
下图内容作者如图。侵删。
树状数组主要用于查询前缀和、区间和及点更新，对点查询、区间修改效率较低。
下述图片内容来源这里。侵删。
核心模板
//树状数组长度是固定的，为n+1 //树状数组的下标必须从1开始（下标为0会死循环） int tr[n+1]; //求最低位的一位1 int lowbit(int x){ return x&-x; } //点更新：在tr[x]的位置上加上c void add(int x,int c){ for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; } //查询前缀和 int query(int x){ int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res; } //区间和 int sum(int i,int j){ return query(j)-query(i-1); }
十七、线段树（了解）
下述图片内容来源这里。侵删。
核心模板
#define lc p<<1 #define rc p<<1|1 int n,w[N]; //w[]是需维护的一维数组 struct node{ int l,r,sum,add; }tr[N*4]; //向上更新 void pushup(int p){ tr[p].sum=tr[lc].sum+tr[rc].sum; } //向下更新 void pushdown(int p){ if(tr[p].add){ tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1); tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1); tr[lc].add+=tr[p].add; tr[rc].add+=tr[p].add; tr[p].add=0; } } void build(int p,int l,int r){ tr[p]={l,r,w[l],0}; if(l==r) return ; //是叶子则返回 int m=l+r>>1; //不是叶子则裂开 build(lc,l,m); build(rc,m+1,r); pushup(p); } void update(int p,int x,int y,int k){ if(x<=tr[p].l&&tr[p].r<=y){ //覆盖则修改 tr[p].sum+=(tr[p].r-tr[p].l+1)*k; tr[p].add+=k; return ; } int m=tr[p].l+tr[p].r>>1; //不覆盖则裂开 pushdown(p); if(x<=m) update(lc,x,y,k); if(y>m) update(rc,x,y,k); pushup(p); } int query(int p,int x,int y){ if(x<=tr[p].l&&tr[p].r<=y) return tr[p].sum; //覆盖则返回 int m=tr[p].l+tr[p].r>>1; //不覆盖则裂开 pushdown(p); int sum=0; if(x<=m) sum+=query(lc,x,y); if(y>m) sum+=query(rc,x,y); return sum; }
