基本算法

int128的读入输出

template <typename T>inline void read(T& t){
    T sum = 0, f = 1;
    char c=getchar();
    while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) sum=sum*10+c-'0',c=getchar();
    t=sum*f;
}
template<typename T> inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

位运算

下述数位是从右往左0开始计算

取出整数n在二进制表示下的第k位						 (n>>k)&1
取出整数n在二进制表示下的第0~k-1位(后k位)				n&((1<<k)-1)
把整数n在二进制表示下的第k位取反						 n^(1<<k)
对整数n在二进制表示下的第k位赋值1						 n|(1<<k)
对整数n在二进制表示下的第k位赋值0						 n&(~(1<<k))    n|(0<<k)

起床困难综合症

针对于该题，我们想到得到的结果是不超过m的最大数字所以我们可以通过二进制枚举，由于题目中数据m为<=10e9，所以二进制最多又30位，那么我们从最高位开始枚举，在不超过m的前提下，尽可能让高位的1更多，这样便能够起到最后数字越大的效果。，枚举每一位的时候，当该位填1的时候<=m才会有选择到底填0还是1，由于需要经过n次运算，使得最后的数越大，那么我们需要在当前位填1<=m的前提下，再去判断0，1经过n次运算得到的数哪个更大，再去选择填0还是1，倘若当前位填1大于m，那么当前位只能填0.

/*
21  世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。
作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。
通过研究相关文献，他找到了该病的发病原因： 在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。
正是由于 drd 的活动，起床困难综合症愈演愈烈， 以惊人的速度在世界上传播。
为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。
历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。
drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。
具体说来，drd 的防御战线由 n 扇防御门组成。
每扇防御门包括一个运算 op 和一个参数 t，其中运算一定是 OR,XOR,AND 中的一种，参数则一定为非负整数。
如果还未通过防御门时攻击力为 x，则其通过这扇防御门后攻击力将变为 x op t。
最终 drd 受到的伤害为对方初始攻击力 x 依次经过所有 n 扇防御门后转变得到的攻击力。
由于 atm 水平有限，他的初始攻击力只能为 0 到 m 之间的一个整数（即他的初始攻击力只能在 0,1,…,m 中任选，但在通过防御门之后的攻击力不受 m 的限制）。
为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。
输入格式
第 1 行包含 2 个整数，依次为 n,m，表示 drd 有 n 扇防御门，atm 的初始攻击力为 0 到 m 之间的整数。
接下来 n 行，依次表示每一扇防御门。每行包括一个字符串 op 和一个非负整数 t，两者由一个空格隔开，且 op 在前，t 在后，op 表示该防御门所对应的操作，t 表示对应的参数。
输出格式
输出一个整数，表示 atm 的一次攻击最多使 drd 受到多少伤害。
输入样例：
3 10
AND 5
OR 6
XOR 7
输出样例：
1
样例解释
atm可以选择的初始攻击力为 0,1,…,10。
假设初始攻击力为 4，最终攻击力经过了如下计算
4 AND 5 = 4
4 OR 6 = 6
6 XOR 7 = 1
类似的，我们可以计算出初始攻击力为 1,3,5,7,9 时最终攻击力为 0，初始攻击力为 0,2,4,6,8,10 时最终攻击力为 1，因此 atm 的一次攻击最多使 drd 受到的伤害值为 1。
运算解释
在本题中，选手需要先将数字变换为二进制后再进行计算。如果操作的两个数二进制长度不同，则在前补 0 至相同长度。
OR 为按位或运算，处理两个长度相同的二进制数，两个相应的二进制位中只要有一个为 1，则该位的结果值为 1，否则为 0。
XOR 为按位异或运算，对等长二进制模式或二进制数的每一位执行逻辑异或操作。如果两个相应的二进制位不同（相异），则该位的结果值为 1，否则该位为 0。
AND 为按位与运算，处理两个长度相同的二进制数，两个相应的二进制位都为 1，该位的结果值才为 1，否则为 0。
例如，我们将十进制数 5 与十进制数 3 分别进行 OR、XOR 与 AND 运算，可以得到如下结果：

    0101 (十进制 5)             0101 (十进制 5)             0101 (十进制 5)             
 OR 0011 (十进制 3)         XOR 0011 (十进制 3)         AND 0011 (十进制 3)             
  = 0111 (十进制 7)           = 0110 (十进制 6)           = 0001 (十进制 1)             
*/

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int a[N], op[N];
char str[4];
int n,m;
bool cal(bool x, int j);

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;++i)
    {
        cin>>str>>a[i];
        if(str[0]=='O')
            op[i]=1;
        else if(str[0]=='X')
            op[i]=2;
        else
            op[i]=3;
    }
    int ans=0;
    for(int i=29;i>=0;--i)//从高位到低位枚举填0还是1
    {
        if((1<<i)<=m)
        {
            bool x=cal(0, i), y=cal(1, i);
            if(x>=y)
                ans |= (x<<i);
            else
            {
                ans |= (y<<i);
                m -= 1<<i;
            }
        }
        else
            ans |= cal(0,i)<<i; 
    }
    
    cout<<ans<<endl;
    
    return 0;
}

bool cal(bool x, int j)
{
    for(int i=0;i<n;++i)
    {
        if(op[i]==1)
            x |= ((a[i]>>j)&1);
        else if(op[i]==2)
            x ^= ((a[i]>>j)&1);
        else if(op[i]==3)
            x &= ((a[i]>>j)&1);
    }
    return x;
}

二进制

(原码反码补码)

/*
原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 
[+1]原 = 0000 0001
[-1]原 = 1000 0001

反码的表示方法是:
正数的反码是其本身
负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反

补码的表示方法是:
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
*/

快速幂

/*
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数，表示a^b mod p的值。
数据范围
0≤a,b≤109
1≤p≤109
输入样例：
3 2 7
输出样例：

*/
#include <iostream>using namespace std;
typedef long long LL;

int main(
{
    LL a,b,p;
    cin>>a>>b>>p;
    LL res=1%p;
    for(;b;b>>=1)
    {
        if(b&1)
            res = (res*a)%p;
        a = (a*a)%p;
    }
    cout<<res<<endl;
    return 0;
}

64位整数乘法

/*
求 a 乘 b 对 p 取模的值。
输入格式
第一行输入整数a，第二行输入整数b，第三行输入整数p。
输出格式
输出一个整数，表示a*b mod p的值。
数据范围
1≤a,b,p≤1018
输入样例：
3
4
5
输出样例：
2
*/
#include <iostream>
using namespace std;
typedef long long LL;
LL a, b, p;

int main ()
{
    //scanf("%lld\n%lld\n%lld",&a,&b,&p);
    cin>>a>>b>>p;
    LL res=0;
    while(b)
    {
        if(b&1)
            res = (res + a) % p;
        a = a * 2 % p;
        b>>=1;
    }
    cout<<res<<endl;
    return 0;
}

递归

递归实现指数型枚举

通过二进制下每一位的0/1表示该位置有没有被选择，在进行递归枚举的时候当枚举完n个位置之后对n个位置进行一次遍历若该位置上为1则输出对应的位置编号，此为递归截止条件，每一次递归有两种选择即在判断每一个位置的时候有两种选择：选与不选。选的话需要将对应位置上的数字改为1，不选择的话则不需要做变化。

/*
从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤15
输入样例：
3
输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

*/
#include <iostream>
using namespace std;
int n;
void dfs(int u, int state);

int main()
{
    cin>>n;    
    dfs(0,0);
    return 0;
}
void dfs(int u, int state)
{
    if(u==n)
    {
        for(int i=0;i<n;++i)
            if(state>>i&1)
                cout<<i+1<<" ";
        cout<<endl;
        return ;
    }
    dfs(u+1, state);
    dfs(u+1, state|(1<<u));
}

递归实现组合型枚举

在递归实现指数型枚举的基础上加上了只能选m个的限制

/*
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25
输入样例：
5 3
输出样例：
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
思考题：如果要求使用非递归方法，该怎么做呢？
*/
#include <iostream>
using namespace std;
int n, m;
void dfs(int u, int num, int state);

int main()
{
    cin>>n>>m;
    dfs(0, 0, 0);
    return 0;
}

void dfs(int u, int num, int state)
{
    if(num+n-u<m||num>m)
        return ;
    if(num==m)
    {
        for(int i=0;i<n;++i)
            if(state>>i&1)
                cout<<i+1<<" ";
        cout<<endl;
        return ;
    }
    
    dfs(u+1, num+1, state|(1<<u));
    dfs(u+1, num, state);
}


#include <iostream>
#include <stack>
using namespace std;
int n, m;
struct State
{
  int pos,u,num,state;  
};

int main()
{
    cin>>n>>m;
    
    stack<State> stk;
    stk.push({0,0,0,0});
    while(stk.size())
    {
        auto t = stk.top();
        stk.pop();
        if(t.pos == 0)
        {
            if(t.num+n-t.u<m || t.num>m)
                continue;
            if(t.num == m)
            {
                for(int i=0;i<n;++i)
                    if(t.state>>i&1)
                        cout<<i+1<<" ";
                cout<<endl;        
                continue;
            }
            t.pos=1;
            stk.push(t);
            stk.push({0,t.u+1,t.num+1,t.state|(1<<t.u)});
        }
        else if(t.pos == 1)
        {
            t.pos=2;
            stk.push(t);
            stk.push({0,t.u+1,t.num,t.state});
        }
        else
            continue;
    }
    return 0;
}

递归实现排列型枚举

/*
把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1≤n≤9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/
#include <iostream>
#include <vector>
using namespace std;
const int N=15;
bool st[N];
vector<int> p;
int n;
void dfs(int u);

int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

void dfs(int u)
{
    if(u==n)
    {
        for(auto x:p)
            cout<<x<<' ';
        cout<<endl;
    }
    for(int i=1;i<=n;++i)
    {
        if(!st[i])
        {
            st[i]=true;
            p.push_back(i);
            dfs(u+1);
            p.pop_back();
            st[i]=false;
        }
    }
}

带重复元素的全排列问题

/*
输入一组数字（可能包含重复数字），输出其所有的排列方式。
样例
输入：[1,2,3]
输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]
*/
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums) {
        sort(nums.begin(),nums.end());//保证相同的数字连续
        path.resize(nums.size());
        dfs(nums, 0, 0, 0);
        return res;
    }
    void dfs(vector<int> &nums, int u, int start, int state)
    //u表示已经放的个数，start表示从哪一位开始放，state表示已经放过的状态
    {
        if(u == nums.size())
        {
            res.push_back(path);
            return ;
        }
        if(!u || nums[u] != nums[u-1])
            start=0;
        for(int i=start;i<nums.size();++i)//从start开始找没有被放过的元素
        {
            if(!(state>>i & 1))
            {
                path[i]=nums[u];
                dfs(nums,u+1,i+1,state|(1<<i));
            }
        }
    }
};

排列式

/*
7254是一个不寻常的数，因为它可以表示为7254 = 39 x 186，这个式子中1~9每个数字正好出现一次
　　输出所有这样的不同的式子（乘数交换被认为是相同的式子）
　　结果小的先输出；结果相同的，较小的乘数较小的先输出。
输入描述:
　　每一行输出一个式子，式子中的等号前后空格、乘号（用字母x代表）前后空格
 　　较小的乘数写在前面 
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int a[9]={1,2,3,4,5,6,7,8,9};
vector<int> res;
struct node
{
    int a,b,c;
    bool operator < (node& A)
    {
        if(a!=A.a)
            return a<A.a;
        else
            return b<A.b;
    }
};
node ans[110];
int idx;
bool st[9];

int cal(vector<int> a, int i, int j);
void dfs(int u);

int main()
{
    dfs(0);
    sort(ans,ans+idx);
    for(int i=0;i<idx;++i)
    {
        bool flag=true;
        for(int j=i+1;j<idx;++j)
        {
            if(ans[i].b==ans[j].c)
            {
                flag=false;
                cout << ans[i].a << " " << "=" << " " << ans[i].b << " " << "x" << " " << ans[i].c << endl;
                break;
            }
            if(ans[i].a!=ans[j].a)
                break;
        }
        //if(flag)

    }
    return 0;
}
int cal(vector<int> a, int i, int j)
{
    int t=0;
    for(int k=j;k>=i;--k)
        t=t*10+a[k];
    return t;
}
void dfs(int u)
{
    if(u==9)
    {
        for (int i = 3; i < 7; ++i)
            for (int j = i + 1; j < 8; ++j)
                if (cal(res, 0, i) == cal(res, i + 1, j) * cal(res, j + 1, 8)) {
                    ans[idx].a = cal(res, 0, i);
                    ans[idx].b = cal(res, i + 1, j);
                    ans[idx].c = cal(res, j + 1, 8);
                    ++idx;
                }
        return ;
    }
    for(int i=0;i<9;++i)
    {
        if(!st[i]) {
            st[i] = true;
            res.push_back(a[i]);
            dfs(u + 1);
            st[i] = false;
            res.pop_back();
        }
    }
}

排序

快速排序

\[\begin{align} &快速排序主要步骤如下：((分治的思想)以数组q[N]举例) \\ &①.确定分界点(一般情况下取左端点q[L]、右端点q[R]、中间点q[L+R/2]、等) \\ &②.调整区间(将所有数据调整至步骤①中分界点的两边) \\ &③.递归处理左右两端区间. \\ \end{align} \]

/*
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int q[N];
int n;
void quick_sort(int q[],int l,int r);

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    for(int i=0;i<n;++i)
        printf("%d ",q[i]);
    return 0;
}
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(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

第k个数

\[\begin{align} &将给定数组利用快速排序排序完后输出第k个元素即可 \\ \end{align} \]

/*
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 k 小数。
数据范围
1≤n≤100000,
1≤k≤n
输入样例：
5 3
2 4 1 5 3
输出样例：
3
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6+10;
int q[N];
int n,k;
void quick_sort(int p[],int l,int r);
int main()
{
    scanf("%d %d",&n,&k);    
    for(int i=0;i<n;++i)
    {
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    printf("%d",q[k-1]);
    return 0;
}
void quick_sort(int p[],int l,int r)
{
    if(l>=r)
    return ;
    int x=p[l+r>>1],i=l-1,j=r+1;
    while(i<j)
    {
        do
        ++i;
        while(p[i]<x);
        do
        --j;
        while(p[j]>x);
        if(i<j)
        {
            swap(p[i],p[j]);
        }
    }
    quick_sort(p,l,j);
    quick_sort(p,j+1,r);
}

归并排序

\[\begin{align} &归并排序主要步骤：(归并排序需要一个额外的数组tmp) \\ &①.选取中间点(下标) \\ &②.递归处理左右两端区间 \\ &③.双指针i,j分别指针两端区间开头,指针后移过程比较两个指针指向元素的大小，将小的放置到tmp数组中 \\ &④.处理两端区间中没有放完的元素，直接放置到tmp数组的后方 \\ &⑤.将tmp得到的顺序复制给原数组 \\ \end{align} \]

/*
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int q[N],tmp[N];
int n;
void merge_sort(int q[],int l,int r);

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&q[i]);
        
    merge_sort(q,0,n-1);
    
    for(int i=0;i<n;++i)
        printf("%d ",q[i]);
        
    return 0;
}
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,j<k;++i,++j)
        q[i]=tmp[j];
}

逆序对数量

\[\begin{align} &首先我们考虑归并排序的步骤(参考上文),取出中间点(下标),我们能将所有逆序对分为三种，第一张是在左区间，第二种是在右区间 \\ &第三种是一半在左，一半在右，那么我们考虑第三种情况：由于先递归处理左右区间，所以左右区间的逆序对数量可以在递归过程中 \\ &得到，当递归完成后，左右区间已有序，双指针i,j开始遍历两段有序区间，直至发现右区间的一个元素q[j]小于左区间的一元素q[i] \\ &即q[i]>q[j](左区间一元素大于右区间)我们假设一开始选取中间点(下标)为mid,那么我们可以发现q[i]往后元素(包含q[i])将都大于 \\ &q[j]，那么此时逆序对数量为mid-i+1，由此可知，递归过程中左右区间的逆序对数量也是由此得出，最终累加在一起即可得到结果. \\ \end{align} \]

/*
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,109]。
输入样例：
6
2 3 4 5 6 1
输出样例：
5
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
typedef long long LL;
int q[N],tmp[N];
int n;
LL merge_sort(int l,int r);

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&q[i]);
    cout<<merge_sort(0,n-1)<<endl;
    
    return 0;
}
LL merge_sort(int l,int r)
{
    if(l>=r)
        return 0;
    int mid=l+r >>1;
    LL res=merge_sort(l,mid)+merge_sort(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++];
            res+=(mid-i+1);
        }
    }
    while(i<=mid)
        tmp[k++]=q[i++];
    while(j<=r)
        tmp[k++]=q[j++];
    for(i=l,j=0;i<=r,j<k;++i,++j)
        q[i]=tmp[j];
    return res;
}

希尔排序

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110;
int m[4]={6,3,2,1};
int n;
int a[N];
void shell(int q[], int len);

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
        cin>>a[i];
    shell(a, n);
    for(int i=0;i<n;++i)
        cout<<a[i]<<" ";
    return 0;
}
void shell(int q[], int len)
{
    for(int i=0;i<4;++i)
    {
        for(int j=m[i];j<len;++j)
        {
            int t=q[j];
            int k=j-m[i];
            while(k>=0&&q[k]>t)
            {
                q[k+m[i]]=q[k];
                k-=m[i];
            }
            q[k+m[i]]=t;
        }
        for(int i=0;i<len;++i)
            cout<<q[i]<<' ';
        cout<<endl;
    }
}

二分

二分的应用在数据结构单调队列章节也有一道例题

\[\begin{align} &二分的本质不是单调性(有单调性一定可以二分) \\ &①.整数二分 \\ &二分的本质是边界，给定一个区间，我们在区间上定义一种性质，使得该性质右半边满足，左半边不满足(整数二分左右两边没有交点) \\ &那么我们既可以二分出左右两个边界点，如下图所示 \\ & \\ &②.浮点数二分 \\ &由于浮点数二分不会发生整除，所以与整数二分相似，不需要考虑发生整除的情况 \end{align} \]

整数二分

找最小的最大值：l=mid, r=mid-1;

找最大的最小值：r=mid, l=mid+1;

/*
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
*/
#include <iostream>
using namespace std;
const int N=1e5+10;
int q[N];
int n,T;

int main()
{
    cin>>n>>T;
    for(int i=0;i<n;++i)
        cin>>q[i];
    while(T--)
    {
        int x;
        cin>>x;
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            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>>1;
                if(q[mid]<=x)
                    l=mid;
                else
                    r=mid-1;
            }
            cout<<r<<endl;
        }
    }
    return 0;
}

/*
峰值定义为比左右相邻元素大的元素。
给定一个长度为 n 的数组 nums，数组下标从0开始，保证 nums[i]≠nums[i+1]，请找出该数组的峰值，并返回峰值的下标。
数组中可能包含多个峰值，只需返回任意一个即可。
假定 nums[-1] = nums[n] = -∞。
本题中数组是隐藏的，你可以通过我们预设的 int 函数 query 来获得数组中某个位置的数值是多少。
例如，query(a) 即可获得下标为 a 的元素的值。
注意：
query 函数的调用次数不能超过 min(3×⌈log2n⌉,10)。
数据范围
1≤n≤105，
数组中的整数在 int 范围内。
输入样例1：
[1, 2, 3, 1]
输出样例1：
2
输入样例2：
[1, 2, 1, 3, 5, 6, 4]
输出样例2：
1
样例解释
对于样例 1，3 是峰值，其下标为 2。

对于样例 2，2 和 6 是峰值，下标为 1 和 5，输出任意一个均可。
*/
// Forward declaration of queryAPI.
// int query(int x);
// return int means nums[x].

class Solution {
public:
    int findPeakElement(int n) {
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(query(mid)>query(mid+1))
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
};

/*
给定一个浮点数 n，求它的三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
*/
#include <iostream>
using namespace std;
const double eps=1e-8;

int main()
{
    double n;
    scanf("%lf",&n);
    double l=-10000,r=10000;
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        if(mid*mid*mid>=n)
            r=mid;
        else
            l=mid;
    }
    printf("%.6f",l);
    return 0;
}

高精度

在高精度中对于大整数的存储方式都是一致的，可以用数组或者vector进行存储

高精度加法

\[\begin{align} &高精度加法是由于C++基本数据类型能表示的数字有最大界限，所以才会需要我们自己去处理高精度加法操作，但是在java和python \\ &中是不需要我们自己去处理高精度问题的，那么在C++中我们应当如何处理高精度加法呢.我们可以参考我们列竖式的加法计算过程并对 \\ &其进行模拟即可.可以用过将数字的每一位存放在数组的每一位上，之后将两个数组的每一位相加，每次相加需要考虑是否有进位的操作,这 \\ &样可以保证完全模拟出加法列竖式的过程. \end{align} \]

/*
给定两个正整数（不含前导 0），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤100000
输入样例：
12
23
输出样例：
35
*/
//STL写法
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e6+10;
char num1[N],num2[N];
vector<int> a,b;
vector<int> add(vector<int> A, vector<int> B);

int main()
{
    cin>>num1>>num2;
    int len1=strlen(num1),len2=strlen(num2);
    for(int i=0;i<len1;++i)
        a.push_back(num1[len1-1-i]-'0');
    for(int i=0;i<len2;++i)
        b.push_back(num2[len2-1-i]-'0');
    auto c=add(a,b);
    for(int i=c.size()-1;i>=0;--i)
        cout<<c[i];
    return 0;
}

vector<int> add(vector<int> A,vector<int> B)
{
    if(A.size()<B.size())
        return add(B,A);
    vector<int> c;
    int t=0;
    for(int i=0;i<A.size();++i)
    {
        t+=A[i];
        if(i<B.size())
            t+=B[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t)
        c.push_back(t);
    return c;
}
//数组写法
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6+10;
char num1[N], num2[N];//存放两个很大的整数，这里是以字符串的形式存储的
int n1[N], n2[N];//存放两个很大的整数字符串变成数字之后的值
int res[N] = { 0 };//存放结果
int main()
{
    cin >> num1 >> num2;
    int l1 = strlen(num1);
    int l2 = strlen(num2);
    for (int i = 0; i < l1; ++i)
    {
        n1[i] = (num1[l1 - 1 - i] - '0');//将字符转换成数字
    }
    for (int i = 0; i < l2; ++i)
    {
        n2[i] = (num2[l2 - 1 - i] - '0');//将字符转换成数字
    }
    int over = 0;//用于进位
    for (int i = 0; i < N; ++i)//进行加法运算
    {
        int temp = n1[i] + n2[i] + over;
        res[i] = temp % 10;
        over = temp / 10;
    }
    int j=N-1;
    for (j; j >= 0; --j)//去前置0
    {
        if (res[j])
        {
            break;
        }
    }
    for (int k = j; k>=0; --k)//倒叙输出结果
    {
        cout << res[k];
    }
    return 0;
}

高精度减法

\[\begin{align} &高精度减法同样也是对列竖式计算减法的过程进行模拟即可(注意考虑借位的情况)注意前导0 \end{align} \]

/*
给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤105
输入样例：
32
11
输出样例：
21
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N=1e6+10;
char num1[N],num2[N];
vector<int> a,b;
bool cmp(vector<int> A, vector<int> B);//判断是否A>=B
vector<int> sub(vector<int> A, vector<int> B);

int main()
{
    cin>>num1>>num2;
    int len1=strlen(num1),len2=strlen(num2);
    for(int i=0;i<len1;++i)
        a.push_back(num1[len1-i-1]-'0');
    for(int i=0;i<len2;++i)
        b.push_back(num2[len2-i-1]-'0');
    
    if(cmp(a,b))
    {
        auto c=sub(a,b);
        for(int i=c.size()-1;i>=0;--i)
            cout<<c[i];
    }
    else
    {
        auto c=sub(b,a);
        printf("-");
        for(int i=c.size()-1;i>=0;--i)
            cout<<c[i];
    }
        
    return 0;
}

bool cmp(vector<int> A, vector<int> 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;
}

vector<int> sub(vector<int> A, vector<int> B)
{
    vector<int> c;
    for(int i=0,t=0;i<A.size();++i)
    {
        t=A[i]-t;
        if(i<B.size())
            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;
}

高精度乘法

\[\begin{align} &此处由于一般情况下高精度乘高精度不常用所以此处只使用高精度乘低精度. \\ &但是此处得高精度乘法和我们平时进行列竖式计算乘法得方法并不相似，由于我们是高精度乘以低精度，所以我们会将低精度作为一个 \\ &整体，其次将高精度得每一位乘以低精度这个整体并考虑进位得情况. \end{align} \]

/*
给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共一行，包含 A×B 的值。
数据范围
1≤A的长度≤100000,
0≤B≤10000
输入样例：
2
3
输出样例：
6
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> mul(vector<int> A,int B);

int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i=0;i<a.size();++i)
        A.push_back(a[a.size()-i-1]-'0');
    auto c=mul(A,b);
    for(int i=c.size()-1;i>=0;--i)
        cout<<c[i];
    return 0;
}

vector<int> mul(vector<int> A,int B)
{
    vector<int> c;
    int t=0;
    for(int i=0;i<A.size()||t;++i)
    {
        if(i<A.size())
            t+=(A[i]*B);
        c.push_back(t%10);
        t/=10;
    }
    while(c.size()>1&&c.back()==0)
        c.pop_back();
    return c;
}

高精度除法

\[\begin{align} &与之类似我们可以参考列竖式去计算除法，但是这里对于高精度的存储仅仅是对除法来说其实正序存储更方便，但是 \\ &为了与其他运算相一致，所以此处我们仍然使用逆序存储，每次用高精度的一位去除以低精度数这个整体，然后其得 \\ &到的上保存，余数*10+下一位再去除以低精度数这个整体依次后续进行，最后将商的答案去除前导0即可. \end{align} \]

/*
给定两个非负整数（不含前导 0） A，B，请你计算 A/B 的商和余数。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000,
B 一定不为 0
输入样例：
7
2
输出样例：
3
1
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> div(vector<int> A, int B, int &r);

int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i=0;i<a.size();++i)
        A.push_back(a[a.size()-i-1]-'0');
    int r=0;
    auto c=div(A,b,r);
    for(int i=c.size()-1;i>=0;--i)
        cout<<c[i];
    cout<<endl<<r<<endl;
    return 0;
}
vector<int> div(vector<int> A,int B,int &r)
{
    vector<int> c;
    for(int i=A.size()-1;i>=0;--i)
    {
        r=r*10+A[i];
        c.push_back(r/B);
        r%=B;
    }
    reverse(c.begin(),c.end());
    while(c.size()>1&&c.back()==0)
        c.pop_back();
    return c;
}

前缀和、差分

前缀和

\[\begin{align} &前缀和是有一个长度为n的数组a[N]，讲前缀和定义为数组s[N]，s[i]表示的是前i个数字的和。且前缀和中我们下标从1开始. \\ &①.如何求前缀和：s[i]=s[i-1]+a[i]\quad (s[0]=0) \\ &②.前缀和的作用：可以快速求解出一段区间中的和，假设求解区间[l,r]这一段所有数的和，那么这里的总和为：s[r]-s[l-1] \\ &s[r]=a[1]+a[2]+……+a[r] \\ &s[l-1]=a[1]+a[2]+……+a[l-1] \\ &那么我们可以推出s[r]-s[l-1]=a[l]+……+a[r]. \\ \end{align} \]

/*
输入一个长度为 n 的整数序列。
接下来再输入 m 个询问，每个询问输入一对 l,r。
对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。
输出格式
共 m 行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int pre[N],a[N];
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
        pre[i]=pre[i-1]+a[i];
    for(int i=0;i<m;++i)
    {
        int l,r;
        cin>>l>>r;
        cout<<pre[r]-pre[l-1]<<endl;
    }
    return 0;
}

\[\begin{align} &当我们将前缀和推广矩阵当中求解子矩阵的前缀和，即二维前缀和. \\ &见下图： \end{align} \]

/*
输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 q 行，每行输出一个询问的结果。
数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int a[N][N],pre[N][N];
int n,m,q;

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)
            pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
    for(int i=0;i<q;++i)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1]<<endl;
    }
    return 0;
}

差分

\[\begin{align} &差分是构造出一个数组b[N]，使得原数组a[N]的每一项a[i]是b[]数组的前缀和.即i>2时，相邻两项之差即为差分 \\ &构造的方法为:\quad \ b1=a1 \\ &\quad \quad \quad \quad \quad \quad \quad b2=a2-a1 \\ &\quad \quad \quad \quad \quad \quad \quad b3=a3-a2 \\ &\quad \quad \quad \quad \quad \quad \quad …… \\ &\quad \quad \quad \quad \quad \quad \quad b_n=a_n-a_{n-1} \\ &但是我们在实际题目中不适用这种方式构造出差分数组. \\ &那么差分有什么实际应用嘛，当我们想要给数组a的某一段区间上加上一个同一个数值，有什么O(1)的方法嘛？ \\ &我们可以利用差分，并且当我们想要得到数组a仅需对b数组进行前缀和的求解，假设我们需要让数组a的[l,r] \\ &区间都+c那么我们可以先让b[l]+c，那么这样的效果就是使得从a[l]开始到a[N]都+c，但是我们不需要使 \\ &得[r+1,N]这一段+c，所以我们再令b[r+1]-c即可，综上我们想要使得数组a中[l,r]这段区间都+c的 \\ &操作仅需要两步：b[l+c];b[r+1]-c即可. \\ &那么还剩最后一个问题没有解决就是怎么构造差分数组，由于上文我们说不使用那种构造方法，所以此处在提供 \\ &一种构造方法：我们假设a数组初始时为0，那么差分数组b也必然全为0，那么我们将数组的的插入过程转换成 \\ &在[i,i]的区间上插入一个a[i]的操作，那么既可以起到输入数组的目的，也同时构造了差分数组. \\ \end{align} \]

/*
输入一个长度为 n 的整数序列。
接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数序列。
接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。
输出格式
共一行，包含 n 个整数，表示最终序列。
数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2
*/
#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,m;
void insert(int l,int r,int 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;
}
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

\[\begin{align} &差分矩阵与一维差分相类似，我们不需要去考虑如何构造，采用与一维数组一致的做法即可. \\ \end{align} \]

/*
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。
输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2
*/
#include <iostream>
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);

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]<<" ";
        }
        puts("");
    }
    return 0;
}
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;
}

双指针

\[\begin{align} &双指针算法的应用大部分情况下是针对与优化的.将O(N^2)的复杂度优化为O(N)复杂度.一般情况下实在单调的情况下使用 \\ &双指针算法 \end{align} \]

/*
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例：
5
1 2 2 3 5
输出样例：
3
*/
 #include <iostream>
 #include <algorithm>
 using namespace std;
 const int N=1e5+10;
 int a[N],s[N];
 int n;
 
 int main()
 {
    cin>>n;
    for(int i=0;i<n;++i)
        cin>>a[i];
    int res=0;
    for(int i=0,j=0;i<n;++i)
    {
        ++s[a[i]];
        while(s[a[i]]>1)
        {
            --s[a[j]];
            ++j;
        }
        res=max(res,i-j+1);
    }
    
    cout<<res<<endl;
    
    return 0;
 }

\[\begin{align} &针对于这道题中两个有序序列都是升序的数组，我们先分析起暴力解法，一个双重循环枚举两个数组中选择的每一个选法，当满足 \\ &a[i]+b[j]==x时输出i,j.那么之后再考虑对其的优化使用双指针算法，找到单调性，首先a,b数组单调上升，其次对于每个i \\ &而言找到一个对应的j，使得a[i]+b[j]>=x，并且j最小，那么可以发现当i右移时，j是往左移动的，那么找到了一个单调性 \\ &至此我们可以将其使用双指针进行优化. \end{align} \]

/*
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m 个整数，表示数组 B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,m,x;

int main()
{
    cin>>n>>m>>x;
    for(int i=0;i<n;++i)
        cin>>a[i];
    for(int i=0;i<m;++i)
        cin>>b[i];
    for(int i=0,j=m-1;i<n;++i)
    {
        while(j>0&&a[i]+b[j]>x)
        {
            --j;
        }
        if(a[i]+b[j]==x)
            cout<<i<<" "<<j<<endl;
    }
    return 0;
}

\[\begin{align} & 对于这道题，我们知道数组a倘若是数组b的子序列，那么数字a的顺序必定是数组b的原有次序，那么我们用双指针 \\ &去寻找答案，遍历a数组中每一个元素，在数组b中找到最左边与之匹配的一个，将两个匹配，重复该做法，得到一 \\ &个双指针的解，那么我们在假设存在一个解，那么我们能不能通过双指针找到解呢，由于我们刚使用双指针时说明 \\ &每次寻找匹配时找最左边的与之匹配的元素，那么我们存在的解的位置必然在双指针解的右边或在同一位置，那么 \\ &存在解必然可以替换为双指针解.我们遍历数组a，当a中元素在b中找到匹配则指针后移，b中指针后移，若找不到则 \\ &b中指针后移，最后若a中指针遍历完则说明找到全部的匹配. \end{align} \]

/*
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。
输入格式
第一行包含两个整数 n,m。
第二行包含 n 个整数，表示 a1,a2,…,an。
第三行包含 m 个整数，表示 b1,b2,…,bm。
输出格式
如果 a 序列是 b 序列的子序列，输出一行 Yes。
否则，输出 No。
数据范围
1≤n≤m≤105,
−109≤ai,bi≤109
输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
Yes
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;++i)
        cin>>a[i];
    for(int i=0;i<m;++i)
        cin>>b[i];
    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(a[i]==b[j])
            ++i;
        ++j;
    }
    if(i==n)
        puts("Yes");
    else
        puts("No");
    return 0;
}

双指针之快慢指针

/*
给定一个包含 n 个整数的数组，请你删除数组中的重复元素并将数组从小到大排序后输出。
输入格式
第一行包含一个整数 n。
第二行包含 n 个不超过 1000 的正整数。
输出格式
输出去重和排序完毕后的数组。
数据范围
1≤n≤1000
输入样例：
6
8 8 7 3 7 7
输出样例：
3 7 8
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N], n;

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i)
        cin >> a[i];
    sort(a, a+n);
    int p = 0, q = 1;
    while(q < n)
    {
        if(a[p] != a[q])
        {
            a[p + 1] = a[q];
            ++p;
        }
        q++;
    }
    for(int i = 0; i <= p; ++ i)
        cout << a[i] << " ";
    return 0;
}

位运算

\[\begin{align} &位运算种有几种基本的位运算符 \\ &左移：在二进制的表示下将数字同时向左移动，低位以0填充，高位越界后舍弃 \\ &1<<n=2^n \quad n<<1=2n \\ &算术右移：在二进制的表示下把数字同时向右移动，高位以符号位填充，低位越界后舍弃 \\ &n>>1=n/2(下取整) \\ &C++中整数/2是向0取整的 \\ &逻辑右移：在二进制的表示下把数字同时向右移动，高位以0填充，低位越界后舍弃 \\ &C++中默认采用算术右移 \\ &lowbit(x)操作 ：用于返回x的最后一位1与后面0组成的数. \\ &例：x=1010\quad lowbit(10)=10(bin) \\ &那么lowbit()怎么实现呢：\quad \quad x \& (-x) \\ &C++中一个整数的负数是原数的补码，则-x=~x+1，则x \&(-x)==x\&(~x+1) \\ \end{align} \]

\[\begin{align} &针对于这道题提供两种写法\\ &我们将数字表示为二进制，由题目中给出的数据范围推出大概是2^{32}次方左右，由此我们可以将每一个数字的每一位右移并且\&1\\ &判断这一位上是不是1，每对于一个数用一变量存储其1的个数.\\ &那么我们使用lowbit操作也可以实现查找二进制中一的个数，我们每次找到最后一位1，之后将其删除\\ &最后记录一共删除了多少次代表了有多少个1.\\ \end{align} \]

/*
给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，表示整个数列。
输出格式
共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。
数据范围
1≤n≤100000,
0≤数列中元素的值≤109
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
        cin>>a[i];
    for(int i=0;i<n;++i)
    {
        int res=0;
        for(int j=0;j<32;++j)
            if((a[i]>>j)&1)
                ++res;
        cout<<res<<" ";
    }
        
    return 0;
}



#include <iostream>
#include <algorithm>
using namespace std;
int lowbit(int x);
int n;

int main()
{
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        int res=0;
        while(x)
        {
            x-=lowbit(x);
            ++res ;
        }
        cout<<res<<" ";
    }
    return 0;
}
int lowbit(int x)
{
    return x&(-x);
}

离散化

\[\begin{align} &此处的离散化特指整数以及有序的离散化，是特殊的哈希 \\ &当我们值域较大但是实际数的个数比较少时我们需要才去离散化(特殊的哈希)，将其映射到较小的区域内 \\ &假设我们需要使用这些数字，但是倘若开一个标记数组那么我们需要开的数组维度肯能会超出最大能开的范围，那么此时 \\ &我们就需要将很大的值域映射到较小的区间中(保序).但是这期间可能会出现问题 \\ &假设我们将数据映射到数组当中 \\ &①.可能出现重复元素 \\ &②.如何算出x离散化后的值.即a中的下标-------二分 \\ &假设需要我们求解出[L,R]这段区间上的和，我们可以先可以找到L,R离散化后的值K_L,K_R，然后计算出a[K_L,K_R]的和 \\ &即可. \\ &其他语言中没有unique函数可以参考实现. \end{align} \]

/*
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=300010;
typedef pair<int, int> PII;
vector<int> alls;//存储所有需要离散化的点
vector<PII> add, quary;//add存储在x位置上+c，quary存储查询的区间
int n,m;
int a[N],s[N];
int find(int x);

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;++i)
    {
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i=0;i<m;++i)
    {
        int l,r;
        cin>>l>>r;
        quary.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    //保序去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    for(auto item:add)
    {
        int x=find(item.first);
        a[x]+=item.second;
    }
    //求前缀和
    for(int i=1;i <= alls.size();++i)
        s[i]=s[i-1]+a[i];
    //处理查询
    for(auto item:quary)
    {
        int l=find(item.first), r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}
int find(int x)
{
    int l=0,r=alls.size();
    while(l<r)
    {
        int mid= l+r >> 1;
        if(alls[mid]>=x)
            r=mid;
        else
            l=mid+1;
    }
    return r+1;
}
//unique的实现
/*
vector<int>::iterator unique(vector<int> &a)
{
    int j=0
    for(int i=0;i<a.size();++i)
        if(!i || a[i]!=a[i-1])
            a[j++]=a[i];
    return a.begin()+j;
}
*/

区间合并

\[\begin{align} &区间合并是讲所有有交集的区间合并成一个区间，是一道典型的贪心的习题. \\ &当合并区间时我们需要尽量保证区间涵盖范围尽可能大. \\ & \end{align} \]

/*
给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−109≤li≤ri≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
vector<PII> section;
int n;
void merge(vector<PII> &segs);

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
    {
        int l,r;
        cin>>l>>r;
        section.push_back({l,r});
    }
    merge(section);
    cout<<section.size()<<endl;
    return 0;
}

void merge(vector<PII> &segs)
{
    sort(segs.begin(),segs.end());
    vector<PII> res;
    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;
}