大纲
差分(重点处理数列区间值改变的问题)
差分可以看成前缀和的逆运算
- 一维差分板子
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) insert(i,i,a[i]);
while(m--){
int l,r,c;
cin>>l>>r>>c;
insert(l,r,c);
}
for(int i=1;i<=n;i++) b[i]+=b[i-1];
for(int i=1;i<=n;i++) cout<<b[i]<<" ";
return 0;
}
- 二维差分（差分矩阵）
#include<iostream>
using namespace std;
int n,m,q;
const int N=1010;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
insert(i,j,i,j,a[i][j]);
while(q--){
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<b[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
双指针
- 最长连续不重复子序列 给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int s[N]; //当前j到i之间每个数出现的次数
int main(){
int n,ans=0;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0,j=0;i<n;i++){
s[a[i]]++;
while(s[a[i]] > 1){
s[a[j]]--;
j++;
}
ans = max(ans,i-j+1);
}
cout<<ans<<endl;
return 0;
}
- 数组元素的目标和
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,m,x;
#define ff(a) for(int i=0;i<a;i++)
int main(){
cin>>n>>m>>x;
ff(n) cin>>a[i];
ff(m) cin>>b[i];
int p=0,q=m-1;
for(;p<n;p++){
while(b[q]>x-a[p]){
q--;
}
if(b[q]+a[p]==x){
cout<<p<<" "<<q;
break;
}
}
return 0;
}
位运算
- 模板
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,m,x;
#define ff(a) for(int i=0;i<a;i++)
int main(){
cin>>n>>m>>x;
ff(n) cin>>a[i];
ff(m) cin>>b[i];
int p=0,q=m-1;
for(;p<n;p++){
while(b[q]>x-a[p]){
q--;
}
if(b[q]+a[p]==x){
cout<<p<<" "<<q;
break;
}
}
return 0;
}
