基本算法

---

差分

差分是前缀和的逆运算，运用于区间修改和询问。当对数据集A的某个区间做修改时，引入差分数组D，只需要修改这个区间的端点，就能记录整个区间的修改，这个修改的复杂度为O(1) 。当所有修改都完成后，再利用差分数组计算出新的A。

差分数组D[]的定义是：D[k] = a[k] - a[k-1]，a[]是原数组

显然，a[i] = D[1]+D[2]+...+D[i]，a[]是D[]的前缀和

例如，把数组区间[L,R]内的每个元素都加上d，只需要对应的差分数组D[]做以下操作：

把D[L]加上d：D[L] += d;

把D[R+1]减去d:D[R+1] -= d;

D[]只会修改区间[L,R]内的值，不会修改到区间外的，要查询a[i]时，做一个D[i]的前缀和即可

以HDU 1556 为例

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+1;

int a[maxn],D[maxn];

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    while(cin >> n){
        int l,r;
        memset(a,0,sizeof(a));
        memset(D,0,sizeof(D));
        for(int i=1;i<=n;i++){
            cin >> l >> r;
            D[l]++;D[r+1]--;
        }
        for(int i=1;i<=n;i++){
            a[i] = a[i-1] + D[i];
            cout << a[i] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

---

二分

Please remember：使用二分一定有一个前提----序列已经排序，且排序方式与使用的函数一致

C++STL标准模板库提供了二分查找函数，时间复杂度为 $O(\log n)$

lower_bound(a.begin(),a.end(),x)

找到序列 $[First\ ,\ last)$ 中第一个 $\geq x$ 的数，并返回该数的迭代器；找不到就返回a.end()。

如果要修改这个数的值为b，可以直接

*lower_bound(a.begin(),a.end(),x) = b;

如果序列是降序排列，要找到第一个 $\leq x$ 的数，可以用

lower_bound(a.begin(),a.end(),x,greater<int>())

upper_bound(a.begin(),a.end(),x)

找到序列 $[First\ ,\ last)$ 中第一个 $>x$ 的数，并返回该数的迭代器；找不到就返回a.end()。

如果要修改这个数的值为b，可以直接

*upper_bound(a.begin(),a.end(),x) = b;

如果序列是降序排列，要找到第一个 $<x$ 的数，可以用

upper_bound(a.begin(),a.end(),x,greater<int>())

---

倍增法

总所周知，前缀和和差分互为逆运算，两者是相反的关系。
而二分和倍增就类似于前缀和和差分，也是相反的关系。二分是每次缩小一半，以$O(log_2)$的速度极快的逼近区间；倍增则是每次增大一倍，以$O(2^n)$的速度极快地扩展。

倍增有两个主要的应用场合，一个是从小区间扩大到大区间，另一个是从小数值倍增到大数值

• ① 对于从小区间扩大到大区间，是求解和区间查询有关的问题，比如求区间最大值或最小值。具体应用有ST表、后缀数组等。
• ② 对于从小数值倍增到大数值，是求解某个元素的精确数值。具体应用有快速幂，LCA最近公共祖先等。

原理

倍增法利用了二进制的特性。你知道的，所有数都能用二进制表示，例如

$$35 = 1 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 32 + 2 + 1$$

所以$35$的二进制是$100011$。
根据《Attention is all you need》， 我们注意到，二进制的第$i$位的权值$2^i$前面一位$2^{i-1}$的两倍，也是前面所有权值之和$+1$，因此，二进制划分就反映了一种倍增的特性。
一个整数$n$，它的二进制只有$log_2n$位，所以如果要从$0$增长到$n$，可以以$1,2,4,...,2^k$做跳板，快速跳到$n$。
不过，倍增法也有局限，它需要提前计算出第$1,2,4,...,2^k$个跳板，并要求这些跳板的值是固定不变的。如果值发生了变化，那么所有跳板都要重新计算，跳板就失去了意义。

以洛谷的一道题为例：P4155 国旗计划

主要用到化圆为线，贪心求最优区间，倍增优化

化圆为线，把原来的圆圈复制再相接以保持首尾关系

贪心，每个区间的左端点排序，在区间x后面的区间里选择不超过x区间右端点的最大左端点的区间

倍增，go[s][i]表示从第s个区间出发，走$2^i$个最优区间后到达的区间

关键递推式： go[s][i] = go[go[s][i-1]][i-1]

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5+1;

int n,m,n2;
int go[N][20];

struct soldier{
    int id,l,r;
    bool operator < (const soldier b) const{return l<b.l;}
}s[N*2];  //排序需要重载 <  

void init(){        //贪心+预计算倍增 
    int nxt=1;
    for(int i=1;i<=n2;i++){		//贪心求每个区间的下一个区间 
        while(nxt<n2 && s[nxt].l<=s[i].r)
            nxt++;
        go[i][0] = nxt-1;
    }
    for(int i=1;(1<<i)<=n;i++)	//倍增 
        for(int j=1;j<=n2;j++)	//每个区间后的第2^i个区间 
            go[j][i] = go[go[j][i-1]][i-1];
}

int res[N];
void answer(int x){        //从第x个开始 
    int len=s[x].l+m,cur=x,ans=1;
    for(int i=log2(N);i>=0;i--){
        int pos = go[cur][i];
        if(pos && s[pos].r<len){
            ans+=1<<i;
            cur=pos;
        }
    }
    res[s[x].id] = ans+1;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        s[i].id=i;
        cin >> s[i].l >> s[i].r;
        if(s[i].r<s[i].l) s[i].r+=m;	//变环为链 
    }
    sort(s+1,s+n+1);
    n2=n;
    for(int i=1;i<=n;i++){				//拆环加倍为链 
        n2++;
        s[n2] = s[i];
        s[n2].l = s[i].l+m;
        s[n2].r = s[i].r+m;
    }
    init();
    for(int i=1;i<=n;i++) answer(i);
    for(int i=1;i<=n;i++) cout << res[i] << ' ';
    return 0;
}

---

ST表

ST(Sparse Table)稀疏表，基于倍增思想(和区间dp挺像的)。可以实现$O(nlogn)$的预处理和$O(1)$的查询。

预处理
我们定义$f[i][j]$为以第$i$个数为起点，长度为$2^j$的区间中的最大值，$f[i][j]$也就是$f[起点][区间长度]$。
长度为$2^j$区间中的最大值怎么求呢？把它划分为两个小区间：$[i,i+2^j] = [i,i+2^{j-1}] + [i+2^{j-1},i+2^j]$,大区间的最大值，就是两个小区间的最大值 的最大值

$$f[i][j] = max(f[i][j-1],f[i+2^{j-1}][j-1])$$

查询
以查询最大值为例，要查询区间$[l,r]$内的最大值，我们就把区间$[l,r]$分为两个重叠拼凑的小区间$[l,l+2^k]$和$[r-2^k+1,r]$，其中$k = log_2(r-l+1)$，是查询区间长度的关于2的指数。

以下是模板

int f[maxn][20];
//预处理
for(int i=0;i<n;i++) cin >> f[i][0];
for(int j=1;j<=20;j++)    //先枚举区间长度!!!
    for(int i=1;i+(1<<j)-1 <= n;i++) //注意终点
        f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1])
//m次查询
for(int i=0,l,r;i<m;i++){
    cin >> l >> r;
    int k = __lg(r-l+1);
    cout << max(f[l][k],f[r-(1<<k)+1][k]) << '\n';
}

注意

• 预处理时，起点的终点要满足$i+2^{j}-1 \leq n$，再次注意，这里有个$-1$，因为区间终点是$i+(1<<j)-1$，而递推式的f[i+(1<<j-1)][j-1]这里没有$-1$，因为这个起点就是上一个区间的终点$i+(1<<j-1)-1$的下一个位置$i+(1<<j-1)$。
• 查询时，第二个区间的起点是$r-(1<<k)+1$，这里有个$+1$，因为$起点+区间长度-1=终点$，那么$起点=终点-区间长度+1$

ST表用于求解区间查询，只要区间的数不变，且符合结合律且可重复贡献，就能用ST表。比如RMQ问题(查询区间最大值、最小值)、最大公因数、最小公倍数、按位与、按位或等等，都可以。
如果区间的数变了，涉及了区间修改，那就要用线段树了。

来一道例题

洛谷P1198

题目描述
现在请求你维护一个数列，要求提供以下两种操作：

1. 查询操作。

语法：Q L

功能：查询当前数列中末尾 $L$ 个数中的最大的数，并输出这个数的值。

限制：$L$ 不超过当前数列的长度。$(L > 0)$

2. 插入操作。

语法：A n

功能：将$n$加上$t$，其中$t$是最近一次查询操作的答案（如果还未执行过查询操作，则$t=0$），并将所得结果对一个固定的常数$D$取模，将所得答案插入到数列的末尾。

限制：$n$是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入格式

第一行两个整数，$M$和$D$，其中$M$表示操作的个数，$D$如上文中所述。

接下来的$M$行，每行一个字符串，描述一个具体的操作。语法如上文所述。

输出格式

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

输入 #1

5 100
A 96
Q 1
A 97
Q 1
Q 2

输出 #1

96
93
96

数据规模与约定

对于全部的测试点，保证$1 \leq M \leq 2 \times 10^5$，$1 \leq D \leq 2 \times 10^9$。

思路:
此题很明显是一道RMQ问题，ST表是代码量很少的做法。不过ST表要求要是静态数组，这里有插入的操作，是不是不能用ST表了？NoNoNo，还是可以！(你是不是想到线段树了，是的，线段树也可以)

根据《Attention is all you need》, 我们注意到，每次插入都是在数组的最后插入的，没有在数组中间乱插，所以即使ST表要维护，也只需要维护终点为$n$的f[][]。

终点为$n$，区间长度为$j$，那么第一段小区间起点就是$n-(2^j)+1$，第二段小区间的起点就是$n-(2^{j-1}+1)$

每有一个插入操作，我们就维护一遍终点为$n$的f[][]，因此时间复杂度是$O(nlogn)$的；查询的复杂度是$O(1)$，满足题目数据范围。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5+5;

int m, p;
int f[maxn][20];

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> m >> p;
    int t = 0,n = 0;
    while(m--){
        char a; cin >> a;
        int b; cin >> b;
        if(a == 'A'){
            f[++n][0] = (b + t) % p;
            for(int j=1;(1<<j)<=n;j++){
                f[n-(1<<j)+1][j] = max(f[n-(1<<j)+1][j-1], f[n-(1<<j-1)+1][j-1]);
            }
        }
        else{
            int l = n - b + 1, r = n, k = __lg(b);
            t = max(f[l][k],f[r-(1<<k)+1][k]);
            cout << t << '\n';
        }
    }
    return 0;
}

---

逆序对

简单的求逆序对的方法：冒泡排序，时间复杂度$ O(n^2) $

直接给代码，不解释了：

#include <bits/stdc++.h>
using namespace std;

int a[10] = {3,5,7,9,2,1,4,6,8,10};

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n = 10, cnt = 0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if(a[j] < a[i]){
                swap(a[i],a[j]);
                cnt++;
            }
    cout << cnt << '\n';
    return 0;
}

更好的求法：树状数组(逆序对+离散化)

也是好久没有接触树状数组了，最近一次出现树状数组还是德叔在重庆赛上秒H题

用树状数组求逆序对的个数，需要用到一个技巧：把数字看成树状数组的下标

例如，序列{5,4,2,6,3,1}，对应a[5]、a[4]、a[2]、a[6]、a[3]、a[1]

每处理一个数字，树状数组下标对应的元素数值加1，统计前缀和，就是逆序对的数量

倒序处理和正序处理都可以，我一般用倒序处理

倒序：

用树状数组倒叙处理序列，当前数字的前一个数的前缀和，即为以该数为较大数的逆序对的个数。

例如，还是序列{5,2,4,6,3,1}，倒叙处理：

数字1，把a[1]+1，计算a[1]的前缀和sum(0)，逆序对数量ans += sum(1-1) = 0

数字3，把a[3]+1，计算a[3]的前缀和sum(2)，逆序对数量ans += sum(3-1) = 1

数字6，把a[6]+1，计算a[6]的前缀和sum(5)，逆序对数量ans += sum(6-1) = 3

…

此外，还需要用到离散化来处理空间问题。

离散化就是把原来的数字用它们的相对大小替代，而它们的顺序仍然不变，不影响逆序对的计算。例如，{1,20000,10,30,890000000}，离散化后变为 {1,4,2,3,5}，新旧序列的逆序对数量是一样的

以一道模板题为例，洛谷P1908

---

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式

第一行，一个数 $n$，表示序列中有 $n$ 个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

输出格式

输出序列中逆序对的数目。

输入输出样例

样例1

6
5 4 2 6 3 1

输出

11

说明/提示

对于 $25\%$ 的数据，$n \leq 2500$。

对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$1 \leq n \leq 5 \times 10^5$。

请使用较快的输入输出。

---

#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
using namespace std;
using ll = long long;
const int maxn = 5e5+5;

int tree[maxn],dc[maxn],n;
struct node{
    int val,index;
}a[maxn];

bool cpa(node x,node y){
    if(x.val == y.val) return x.index < y.index;
    return x.val < y.val;
}

void update(int x,int d){
    while(x <= n){
        tree[x] += d;
        x += lowbit(x);
    }
}

int sum(int x){
    int ans = 0;
    while(x > 0){
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i].val;
        a[i].index = i;
    }
    sort(a+1,a+n+1,cpa);
    for(int i=1;i<=n;i++) dc[a[i].index] = i;
    ll cnt = 0;
    for(int i=n;i>=1;i--){
        update(dc[i],1);
        cnt += sum(dc[i]-1);
    }
    cout << cnt << '\n';
    return 0;
}

---