大纲
前缀和(重点处理数列区间和的问题)
- 前缀和板子
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N],s[N],n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
s[0]=0;
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
while(m--){
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
- 二维前缀和
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N],s[N][N];
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++){
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
}
}
while(q--){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << endl;
}
return 0;
}
二分
- 二分模板
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,q[N];
int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&q[i]);
while(m--){
int x;
scanf("%d",&x);
int l=0,r=n-1;
while(l < r){
int mid = (l + r) / 2;
if(q[mid] >= x) r=mid;
else l=mid+1;
}
if(q[l] != x){
cout << "-1 -1" << endl;
}else{
cout << l << " ";
l=0,r=n-1;
while(l < r){
int mid = (l + r + 1) / 2;
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
这里二分很重要的是区分边界问题（我的mid取的是 (l+r+1)/2 还是 (l+r)/2 ）：
- 查找最后一个 ≤ x 的数
// x: 查询条件
// st: 数组起始下标
// ed: 数组结束下标
int find(int x, int st, int ed)
{
int l = st - 1, r = ed + 1; // 开区间
while (l + 1 < r)
{
int mid = l + r >> 1;
if (a[mid] <= x)
l = mid;
else
r = mid;
}
return l;
}
- 查找第一个 ≥x 的数
int find(int x, int st, int ed)
{
int l = st - 1, r = ed + 1;
while (l + 1 < r)
{
int mid = l + r >> 1;
if (a[mid] >= x)
r = mid;
else
l = mid;
}
return r;
}
