#include<bits/stdc++.h>  //万能
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1010,M=1010;

typedef long long LL;


1.比赛环境：devc++5.11  
    （1）加编译命令：-std=c++11
    （2）注释代码：选中之后 Ctrl+/ ，恢复也是这样操作
    （3）调试问题：打印输出调试法；设置断点调试法；可以再存一份代码，二者同步调试

2.一维前缀和 O(1)时间复杂度内求区间[l,r]的和
（1）方法一
int a[N],s[N];

//s[i] 表示a[1]+a[2]+---a[i]
for(int i=1;i<=n;i++) {
    cin>>a[i];
    s[i]=s[i-1]+a[i];
}

cout<<s[r]-s[l-1]<<"\n";

（2）方法二
int a[N];

for(int i=1;i<=n;i++){
    cin>>a[i];
    a[i]+=a[i-1];
}

cout<<a[r]-a[l-1]<<"\n";

3.二维前缀和 O(1)时间复杂度内求子矩阵的和
（1）方法一
int a[N][M],s[N][M];

//s[i][j] 表示左上角为[1,1]，右下角为[i,j]的子矩阵的和
for(int i=1;i<=n;i++)
    for(int j=1;i<=m;j++){
        cin>>a[i][j];
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }

//左上角为[x1,y1],右下角为[x2,y2]的子矩阵的和
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<"\n";

（2）方法二类似一维前缀和的处理
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];

3.一维差分  O(1)时间复杂度内对区间[l,r]每个数都加上一个数c(c<0时为减去)
int a[N],b[N];  //分别为原数组，差分数组，差分数组求前缀和为原数组

//差分数组的初始化，当原数组都为0时省去此步骤
for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];

b[l]+=c,b[r+1]-=c;

for(int i=1;i<=n;i++){
    b[i]+=b[i-1];
    a[i]=b[i];
}

//注：当原数组元素都是0时，只用一个b[N]即可

4.二维差分 O(1)时间复杂度内对以[x1,y1]为左上角，[x2,y2]为右下角的子矩阵内所有元素都加c
//由于差分为前缀和的逆运算，我们可以通过记忆比较二者
int a[N][M],b[N][M];

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];

b[x1][y1]+=c,b[x2+1][y1]-=c,b[x1][y2+1]-=c,b[x2+1]b[y2+1]+=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];
        a[i][j]=b[i][j];
    }

//元素都为0时的处理同一维差分

5.STL容器库
（1）变长数组
    #include<vector>

    vector<int> a;
    vector<int> a(n);  ==  int a[N];  vector<int> a(n,1);
    vector<int> b(a);  vector<int> b=a;

    vector<int> a[5];//第一维固定（行固定）
    vector<vector<int>> a;

    a.push_back(x);  a.pop_back();
    a.front()  a.back()  a.begin()  a.end()  a.clear();  a.size()
    //注意：a.begin()返回第一个元素地址，a.end()返回最后一个元素后一个位置的地址

    for(int i=0;i<a.size();i++) cout<<a[i]<<"";
    for(auto &x:a) cout<<x<<" ";

（2）栈
    #include<stack>

    stack<int> s;
    s.push(x);  s.pop();  s.top() s.empty() s.size()

    while(!s.empty()){
        cout<<s.top<<" ";
        s.pop();
    }

    用数组模拟的栈要快一些：

（3）队列
    #include<queue>

    queue<int> q;
    q.push(x);  q.pop();  q.front()  q.back()  q.empty() q.size()

    while(!empty){
        cout<<q.front()<<" ";
        q.pop();
    }

    用数组模拟的队列：

（4）优先队列（底层实现逻辑为堆）
    #include<queue>

    priority_queue<int> q; //默认大根堆
    priority_queue<int,vector<int>,greater<int>> q;//小根堆

    q.push(x);  q.pop();  q.top()  q.empty()  q.size()
    //q.push(),q.pop()的时间复杂度都为O(logn)

    可以用数组模拟大根堆与小根堆来模拟优先队列

（5）pair
    pair<int,int> pii;
    pii.first=c1,pii.second=c2;

    //可以用来存坐标
    #define x first
    #define y second
    typedef pair<int,int> PII;

    PII a[N];
    for(int i=0;i<n;i++) a[i]={c1,c2};
    for(int i=0;i<n;i++) cout<<a[i].x<<" "<<a[i].y<<"\n";

（6）有序键值对映射（底层实现逻辑为红黑树）  键-值对 key-value pair 键不可重复（可重复的用multimap）
    #include<map>

    map<int,int> mp;//按键的大小自动从小到大排序
    map<int,int,greater<int>> mp;

    //O(logn)
    mp.insert({c1,c2});  mp[c1]=c2; 
    mp.insert(make_pair(c1,c2)); mp.insert(pair<int,int>(c1,c2));

    mp.erase(key);//O(logn) 删除所有键为key的键值对

    mp.find(key)   //返回的是迭代器（物理地址），不存在返回mp.end()  O(logn)
    mp.count(key)  //存在返回1，不存在返回0 O(logn)  推荐用这个
    mp[key]        //O(logn)

    mp.begin()  mp.end()  mp.empty()  mp.size()  mp.clear();

    for(auto &i:mp) cout<<i.first<<" "<<i.second<<"\n";


（7）无序键值对映射（底层实现逻辑为哈希表）适合大量查询
    #include<unordered_map>

    unordered_map<int,int> hash;  //内部元素杂乱无序，键不可重复

    hash.count(key)  //O(1)

    unordered_multimap<int,int> um;//内部元素杂乱无序，键可重复

（8）有序集合 
    #include<set>

    set<int> s;  //不重复且有序（默认从小到大）
    set<int,greater<int>> s;//从大到小

    s.insert(x);

    erase(x);

    s.count(x)  //由于元素不重复，所有返回值为1或0

    for(auto &i:s) cout<<i<<" ";

    s.begin()  s.end()  s.empty()  s.size()  s.clear();

    multiset<int> ms;   //重复且有序
    unordered_set<int> us;  //不重复且无序
    unordered_multiset<int> um;   //重复且无序

6.函数库
（1）排序 sort(beg,end) 对[beg,end)排序 默认从小到大 O(nlogn) 
    int a[N];
    sort(a,a+n);
    sort(a,a+n,greater<int>());

    sort(a+l,a+r+1);  对区间[l,r]排序

    vector<int> v;
    sort(v.begin(),v.end());
    sort(v.begin(),v.end(),greater<int>()); == sort(v.rbegin(),v.rend());

（2）查找（二分查找）O(logn)
    binary_search(beg,end,x)   //存在x返回true，反之返回false

    lower_bound(beg,end,x)   //返回第一个>=x的元素的位置(注意是物理地址,减去首地址才是逻辑地址)
    eg: int idx=lower_bound(a,a+n,x)-a;

    upper_bound(beg,end,x)  //返回第一个>x的元素的位置(如上)

（3）初始化
    //按字节进行赋值
    memset(a,0,sizeof a);  memset(a,-1,sizeof a);  memset(a,0x3f,sizeof a);

    //对某个特定值赋值
    fill(a,a+n,x);
（4）赋值拷贝  也是按字节
    memcpy(b,a,sizeof a);

7.位运算
（1）类型   符号   0 0   0 1   1 0   1 1   
     按位与  &      0     0     0     1
     按位或  |      0     1     1     1
    按位异或 ^      0     1     1     0
    按位取反 ~      ~1=0      ~0=1
（2）n的二进制表示中第k位是几 
    n>>k&1
（3）返回x的最后一位1 
    int lowbit(int x){
        return x&-x;
    }
    可以用来统计x的二进制表示中1的个数

8.二分
（1）整数二分
步骤：
  a.找一个区间[l,r]，使得答案一定在该区间中
  b.找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点
  c.分析中点mid在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案
在哪个区间；
  d.如果更新方式写的是r=mid，则不用做任何处理；如果更新方式是l=mid，则需要在计算mid时加1。

答案在左段的最右端点
while(l<r){
    int mid=l+r+1>>1;
    if(check(mid)) l=mid;
    else r=mid-1;
}

答案在右段的最左端点
while(l<r){
    int mid=l+r>>1;
    if(check(mid)) r=mid;
    else l=mid+1;
}


9.数论
（1）最大公约数
    int gcd(int a,int b){
        return b?gcd(b,a%b):a;
    }
（2）最小公倍数
    int lcm(int a,int b){
        return a*b/gcd(a,b);
    }
（3）高精度取模
（4）判断质数（朴素法）
（5）判断质数（埃氏筛法）
（6）算数基本定理（唯一分解定理）


10.dfs（暴搜）

void dfs(参数)
{
    if(越界不合法情况){直接return}
    if(终点边界,输出答案) {输出答案 return}
    for循环枚举所有方案
    {
        if(未被标记）
        {
            标记
            dfs(下一层)
            还原标记
        }
    }
}


11.bfs 可以来求边权为1的最短路

//假设求1号节点到n号节点的最短路 基于邻接表
int d[N];  
int bfs(){
    queue<int> q;
    q.push(1);

    memset(d, -1, sizeof d);
    d[1]=0;

    while(!q.empty()){
        int t=q.front();
        q.pop();

        //扩展q的邻接节点
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];

            if(d[j]==-1){
                d[j]=d[t]+1;
                q.push(j);
            }
        }
    }

    return d[n];
}




12.图论
（1）用邻接表存图
    const int N=100010,M=N*2;（无向图要乘以2）

    int h[N],e[M],ne[M],idx;

    memset(h, -1, sizeof h);

    void add(int a,int b){
        e[idx]=b,ne[idx]=h[a],h[a]=idx,idx++;
    }

13.动态规划

























int main()
{
    //输入的数据量超过了1e5或大小超过了
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    return 0;
}