前缀和与差分模板（互逆运算）

序列和

#include<iostream>  using namespace std;  const int N=100010; int a[N],b[N]; int main(){     int n,m,l,r;     cin>>n>>m;     for(int i=1;i<=n;i++)    cin>>b[i];     for(int i=1;i<=n;i++)    a[i]=a[i-1]+b[i];          while(m--){         cin>>l>>r;         cout<<a[r]-a[l-1]<<endl;     }     return 0;      } 

矩阵和

#include<iostream> using namespace std;  const int N=1010; int a[N][N]; //就地转化   int main(){     int n,m,q;     scanf("%d%d%d",&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++){             a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];         }     }          while(q--){         int x1,y1,x2,y2;         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);         cout<<a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]<<endl;         }     return 0; }   //-----将矩阵和存入新数组 #include<iostream> using namespace std; const int N=1010; int a[N][N],b[N][N]; int main(){     int n,m,q;     scanf("%d%d%d",&n,&m,&q);     for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++)             scanf("%d",&b[i][j]);     }     for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++)             a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];     }     while(q--){         int x1,y1,x2,y2;         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);         printf("%dn",a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]);     }     return 0; } 

差分

#include<iostream> using namespace std;  const int N=100010; int a[N],b[N];  void insert(int l,int r,int c){     b[l]+=c;     b[r+1]-=c;     return ; }  int main(){     int n,m;     scanf("%d%d",&n,&m);     for(int i=1;i<=n;i++)   scanf("%d",&a[i]);     for(int i=1;i<=n;i++)   insert(i,i,a[i]);          while(m--){         int l,r,c;         scanf("%d%d%d",&l,&r,&c);         insert(l,r,c);     }     //B-->A     for(int i=1;i<=n;i++)   a[i]=a[i-1]+b[i];               for(int i=1;i<=n;i++)   printf("%d ",a[i]);      } 

差分矩阵

#include<iostream> using namespace std; 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;     return  ; }   int main(){     int n,m,q;     scanf("%d%d%d",&n,&m,&q);     for(int i=1;i<=n;i++)         for(int j=1;j<=m;j++)             scanf("%d",&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]<<" ";             if(j==m)    cout<<endl;         }                }     return 0;      } 

推荐这些文章：

快排模板

#include<iostream> using namespace std; const int N=1e6+10; int n,q[N],tmp[N]; void quick_sort(int q[],int l,int r){ if(l>=r) return; int x=q[l+r>>1],i=l-1,j=r+1; while(i<j){ do i++;while(q[i]<x); do j--;while(q[j]>x); if(i<j) swap...

二分模板

#include<iostream> using namespace std; const int N=100010; int n,m; int 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){ ...

差分（前缀和的逆运算）

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i] - a[i - 1]; //构建差分数组
}
//上面是构建差分数组，
// ...

[模板] 蛇形矩阵

点击查看代码
#include<iostream>

using namespace std;
const int N = 110;
int n, m;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int x = 0, y = 0, d = 1, q[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= m * n; i++) {
q[x][y] = i;
int a = x + dx[d]...

【代码模板】基础算法

快速排序
while写法
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
if(l >= r) return;

int x = q[l + r >> 1], i = l - 1, j = r + 1;
while(i < j)
{
while(q[++ i] < x);
while(...

前缀和与差分

题目

1.P1115 最大子段和
思路：从一段序列中找出最大的连续子序列。可以把前面的相加，累加的和直到小于0时，将sum赋值为0重新开始累加。
#include <iostream>
using namespace std;
const int N = 1e6;
int n;
int num[N];
int ans;
int sum;

int main(int argc, char *argv[]) {
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> num[i] ;
sum = ...

【Top】基础算法模板

摘要
本文所涉及到的算法和数据结果模板均来自于Acwing的算法基础课和算法提高课（部分）。本文仅给出算法代码与时空复杂度，具体证明和讲解暂无。
大数运算
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//由低位到高位储存 114514 -> {4 1 5 4 1 1}
typedef vector<int> bign;

//大正整数计算

//判断a>=b
bool cmp(bign& a, bign& b){...

力扣竞赛模板

Debug
void _debug(ostream& os) { os << '\n'; }
template<typename T, typename... Args>
void _debug(ostream& os, const T& t, const Args&... args) {
os << t;
if (sizeof...(args)) {
os << ", ";
}
_debug(os, args...);
}
#define debug(args....

基础算法 785.快速排序

代码模板：

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
void quicksort(int a[],int l,int r){

if(l>=r)return ;

int x=a[l],i=l-1,j=r+1;

while(i<j){
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j)swap(a[i],a[j]);
}
quicksort(a,l,j);
quicksort(a,j+1,r)...

（线段树 + 扫描线）洛谷模板题

原题链接：洛谷扫描线模板
题目描述：
求 n 个矩形的面积并。
第一行输入一个整数n，随后的n行依次输入x1,y1,x2,y2, (x1,y1),(x2,y2)分别代表矩形的左下角坐标和右上角坐标。
输入格式：
2
100 100 200 200
150 150 250 255
输出格式：
18000
说明：
1≤n≤10000,
0≤x1<x2≤1e9,
0≤y1<y2≤1e9.
思路：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typed...