二分 排序

从小到大进行排序，选择中间数，小的放左边，大的放右边，然后递归两边

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

int i = l - 1, j = r + 1, x = q[l + r >> 1];     //x=q[(l+r)/2]，x=q[0];
while (i < j)
{
    do i ++ ; while (q[i] < x);
    do j -- ; while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);   //如果选j，x一定不能选最右端的数，否则死循环，如1，2
//最后，一定有，i>=j 最后临界有两种情况，当i==j时，应该使用(j,j+1)或(i,i+1),反例(1,2) i==j-1时，使用(j,j+1)或(i-1,i),反例(0,0),否则死循环.
同理如果取mid=l + r +1 >> 1，则应该取(i-1,i)

}

归并排序算法模板 —— 模板题 AcWing 787. 归并排序

从小到大进行排序，先取中间偏左数进行划分，先从整体用递归最小表示成两个数的排序（合并两个排好序的数），接着向上一层合并，两个分组已然有序；类似定义两个指针从两个分组头部开始，进行比较并指针自增，直至有一组到头，期间按比较顺序给新的数组赋值，新数组是预定义的。最后对剩下的分组中最后的数进行赋值，两个while，最后将新的数组的值tmp赋给原数组q。

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

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
    if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
    else tmp[k ++ ] = q[j ++ ];

while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

}

整数二分查找算法模板 —— 模板题 AcWing 789. 数的范围

bool check(int x) {/ … /} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}

[HTML_REMOVED]

[HTML_REMOVED]

[HTML_REMOVED]

[HTML_REMOVED]

[HTML_REMOVED]

[HTML_REMOVED]

浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根 二分法查找解

bool check(double x) {/ … /} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}

高精度加法 —— 模板题 AcWing 791. 高精度加法

// C = A + B, A >= 0, B >= 0

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
vector[HTML_REMOVED] add(vector[HTML_REMOVED]&a,vector[HTML_REMOVED]&b)
{
vector[HTML_REMOVED]C;
if(b.size()>a.size())return add(b,a);
int t=0;
for(int i=0;i<a.size();i++)
{
t=t+a[i];
if(i<b.size())t+=b[i];
C.push_back(t%10);
t=t/10;
}
if(t)C.push_back(t);
return C;
}

int main()
{
string a,b;
vector[HTML_REMOVED]A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i–)A.push_back(a[i]-‘0’);
for(int i=b.size()-1;i>=0;i–)B.push_back(b[i]-‘0’);
auto C=add(A,B);
for(int i=C.size()-1;i>=0;i–)printf(“%d”,C[i]);
return 0;
}

高精度减法 —— 模板题 AcWing 792. 高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

//判断是否有A>=B;
bool cmp(vector[HTML_REMOVED]&a,vector[HTML_REMOVED]&b)
{
if(a.size()!=b.size())return a.size()>b.size();
for(int i=a.size()-1;i>=0;i–)
{
if(a[i]!=b[i])return a[i]>b[i];
}
return true;
}

//C=A-B;
vector[HTML_REMOVED] sub(vector[HTML_REMOVED]&a,vector[HTML_REMOVED]&b)
{
vector[HTML_REMOVED]C;
int t=0;
for(int i=0;i[HTML_REMOVED]i)t=t-b[i];
C.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}

int main()
{
string a,b;
vector[HTML_REMOVED]A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i–)A.push_back(a[i]-‘0’);
for(int i=b.size()-1;i>=0;i–)B.push_back(b[i]-‘0’);
if(cmp(A,B))
{
auto C=sub(A,B);
for(int i=C.size()-1;i>=0;i–)printf(“%d”,C[i]);
}
else
{
auto C=sub(B,A);
printf(“-“);
for(int i=C.size()-1;i>=0;i–)printf(“%d”,C[i]);
}
return 0;
}

高精度乘低精度 —— 模板题 AcWing 793. 高精度乘法

// C = A * b, A >= 0, b >= 0

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

vector[HTML_REMOVED] mul(vector[HTML_REMOVED]&a,int b)
{
vector[HTML_REMOVED]C;
int t=0;
for(int i=0;i[HTML_REMOVED]1&&C.back()==0)C.pop_back();
return C;
}

int main()
{
string a;
int b;
vector[HTML_REMOVED]A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i–)A.push_back(a[i]-‘0’);
auto C=mul(A,b);
for(int i=C.size()-1;i>=0;i–)printf(“%d”,C[i]);
return 0;
}

高精度除以低精度 —— 模板题 AcWing 794. 高精度除法

// A / b = C … r, A >= 0, b > 0

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
vector[HTML_REMOVED]div(vector[HTML_REMOVED]&a,int &b,int &r)
{
vector[HTML_REMOVED]C;
r=0;
for(int i=a.size()-1;i>=0;i–)
{
r=r*10+a[i];
C.push_back(r/b);
r=r%b;
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}

int main()
{
string a;
int b,r=0;
cin>>a>>b;
vector[HTML_REMOVED]A;
for(int i=a.size()-1;i>=0;i–)A.push_back(a[i]-‘0’);
auto C=div(A,b,r);
for(int i=C.size()-1;i>=0;i–)printf(“%d”,C[i]);
printf(“\n”);printf(“%d”,r);
return 0;
}

一维前缀和

S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1]

include[HTML_REMOVED]

using namespace std;
const int N=100010;
int a[N],s[N];
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)s[i]=s[i-1]+a[i];
for(int i=1;i<=m;i++)
{
int l,r;
scanf(“%d%d”,&l,&r);
printf(“%d”,s[r]-s[l-1]);
printf(“\n”);
}
return 0;
}

二维前缀和 —— 模板题 AcWing 796. 子矩阵的和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

include[HTML_REMOVED]

using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int n,m,q;
int main()
{
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)
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];//求前缀和
while(q–)
{
int x1,y1,x2,y2;
scanf(“%d%d%d%d”,&x1,&y1,&x2,&y2);
printf(“%d\n”,s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);//求部分矩阵和
}
return 0;
}

一维差分 —— 模板题 AcWing 797. 差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

include[HTML_REMOVED]

using namespace std;
const int N=100010;
int a[N],b[N];//a接收原始数据，b为a的差分，即b可通过前缀和来求a,a的变化可由b的变化来表示
int n,m;

void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}

int main()
{
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);
}
for(int i=1;i<=n;i++)
{
    b[i]+=b[i-1]; //此时b为变化过后的s
    printf("%d\040",b[i]);
}
return 0;

}

二维差分 —— 模板题 AcWing 798. 差分矩阵

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

include[HTML_REMOVED]

using namespace std;
const int N=1010;
int a[N][N],b[N][N];
int n,m,q;
void insert(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1]+=c;
b[x1][y2+1]-=c;
b[x2+1][y1]-=c;
b[x2+1][y2+1]+=c;
}
int main()
{
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]);
insert(i,j,i,j,a[i][j]);
}
while(q–)
{
int x1,y1,x2,y2,c;
scanf(“%d%d%d%d%d”,&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];
printf(“%d “,b[i][j]);
}
printf(“\n”);
}
return 0;
}

位运算 —— 模板题 AcWing 801. 二进制中1的个数
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n
双指针算法 —— 模板题 AcWIng 799. 最长连续不重复子序列, AcWing 800. 数组元素的目标和
for (int i = 0, j = 0; i < n; i )
{
while (j < i && check(i, j)) j ;

// 具体问题的逻辑

}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
离散化 —— 模板题 AcWing 802. 区间和
vector[HTML_REMOVED] 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
}
区间合并 —— 模板题 AcWing 803. 区间合并
// 将所有存在交集的区间合并
void merge(vector[HTML_REMOVED] &segs)
{
vector[HTML_REMOVED] 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;

}