rotate

rotate(beg, newbeg, end);

$将newbeg成为新第一元素，[beg,newbeg)区间元素放到end后面，调用者必须保证newbeg是[beg,end)内的有效位置$

nth_element

bool cmp(int a, int b) {
    return a > b;
}
int main() {
    int a[9] = {4, 7, 6, 9, 1, 8, 2, 3, 5};
    int b[9] = {4, 7, 6, 9, 1, 8, 2, 3, 5};
    int c[9] = {4, 7, 6, 9, 1, 8, 2, 3, 5};
    nth_element(a, a + 2, a + 9);
    //将下标为2，也就是第3个数放在正确的位置
    //也就是求的是第3小
    cout << "第3小是：" << a[2] << endl;

    //那么求第3大，就是求第9-3+1小,即第7小
    //也就是将下标为6的第7个数，放在正确的位置
    nth_element(b, b + 6, b + 9);
    cout << "第3大是：" << b[6] << endl;

    nth_element(c, c + 2, c + 9, cmp);  //第一种方法
    // nth_element(c,c+2,c+9,greater<int>()); //第二种方法
    cout << "第3大是：" << c[2] << endl;
}

进制转换

//任意进制转十进制
int Atoi(string& S, int R) {
    int ans = 0;
    for (int i = 0; i < S.size(); i++) {
        char t = S[i];
        if (t >= '0' && t <= '9')
            ans = ans * R + t - '0';
        else
            ans = ans * R + t - 'A' + 10;
    }
    return ans;
}
//十进制转任意进制
string Itoa(int Num, int R) {
    string ans = "";
    int temp;
    do {
        temp = Num % R;
        Num /= R;
        if (temp >= 10)
            ans += temp - 10 + 'A';
        else
            ans += temp + '0';
    } while (Num);
    reverse(ans.begin(), ans.end());
    return ans;
}

快速排序

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];
    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);
}

归并排序

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];
}

二分/三分模板

整数二分模板

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;
}

浮点数二分模板

const double eps = 1e-6;  // eps 表示精度，取决于题目对精度的要求
bool check(double x) {/* ... */}  // 检查x是否满足某种性质

double bsearch_3(double l, double r) {
    while (r - l > eps) {
        double mid = (l + r) / 2;  //注意double类型不能用右移运算
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    return l;
}

整数三分模板

//以凸函数位例子
int check(int x) {/*....*/}  //返回判断当前点对应的函数值
int bsearch_1(int l, int r) {
    while (l < r - 1) {
        //三分的两个中点有两种写法
        // m1 = l+(r-l)/3;
        // m2 = r-(r-l)/3;
        m1 = l + r >> 1;
        m2 = m1 + r >> 1;
        if (check(m1) > check(m2))
            r = m2;
        else
            l = m1;
    }
    return l;
}
//对于极大值的求法我觉得有个技巧吧，就是while里面的范围，l和 r 差的
//范围可以扩大一点点 这样最后求极大值时可以遍历l到r，避免的精度不到位出现问题；

浮点数三分模板

//以凸函数位例子
double check(x) {/*.....*/}  //返回判断当前点对应的函数值
double bsearch_1(double l, double r) {
    while (r - l > eps) {
        //三分的两个中点有两种写法
        // m1 = l+(r-l)/3;
        // m2 = r-(r-l)/3;
        m1 = (l + r) / 2;
        m2 = (m1 + r) / 2;
        if (check(m1) > check(m2))
            r = m2;
        else
            l = m1;
    }
    return l;
}

高精度

void init(int* x) {
    char s[305];
    cin >> s;
    x[0] = strlen(s);
    for (int i = 0; i < x[0]; i++) {
        x[x[0] - i] = s[i] - '0';  //将字符串转化为数字，并且倒叙存储
    }
}

int compare(int a[], int b[]) {  //比较，a>b返回1，a<b返回-1，a==b返回0
    if (a[0] > b[0])
        return 1;
    if (a[0] < b[0])
        return -1;
    for (int i = a[0]; i > 0; i--) {
        if (a[i] > b[i])
            return 1;
        if (a[i] < b[i])
            return -1;
    }
    return 0;
}

void print(int a[]) {
    if (a[0] == 0) {
        cout << 0;
        return;
    }
    for (int i = a[0]; i > 0; i--)
        cout << a[i];
    return;
}

高精度加法

void jia(int a[], int b[]) {
    int temp = max(a[0], b[0]);
    c[0] = temp + 1;
    for (int i = 1; i <= temp; i++) {
        c[i] += a[i] + b[i];
        c[i + 1] = c[i] / 10;
        c[i] %= 10;
    }
    while (c[c[0]] == 0 && c[0] > 1)
        c[0]--;
}

高精度减法

void jian(int m[], int n[]) {
    c[0] = m[0];
    for (int i = 1; i <= m[0]; i++) {
        if (m[i] < n[i]) {
            m[i + 1]--;
            m[i] += 10;
        }
        c[i] = m[i] - n[i];
    }
    while (c[c[0]] == 0 && c[0] > 1)
        c[0]--;
}

高精度乘低精度

void GaoChengDi(int a[], int b) {
    c[0] = a[0];
    for (int i = 1; i <= a[0]; i++) {
        c[i] += a[i] * b;
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c[c[0] + 1] > 0) {  //进位并调整长度
        c[c[0] + 2] = c[c[0] + 1] / 10;
        c[c[0] + 1] %= 10;
        c[0]++;
    }
}

高精度乘高精度

void cheng(int m[], int n[]) {
    c[0] = m[0] + n[0];
    for (int i = 1; i <= m[0]; i++) {
        for (int j = 1; j <= n[0]; j++) {
            c[i + j - 1] += m[i] * n[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    while (c[c[0]] == 0 && c[0] > 1)
        c[0]--;
}

高精度阶乘

a[0] = 1;
a[1] = 1;
for (int j = 1; j <= n; j++) {
    mem(c);  //清0
    c[0] = a[0];
    rep(i, 1, a[0]) {  //计算阶乘（高精乘低精）
        c[i] += a[i] * j;
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c[c[0] + 1] > 0) {  //进位并调整长度
        c[c[0] + 2] = c[c[0] + 1] / 10;
        c[c[0] + 1] %= 10;
        c[0]++;
    }
    rep(i, 0, c[0]) {
        a[i] = c[i];  //拷贝j的阶乘，便于计算后续的阶乘
    }
}

高精度除以低精度

void GaoChuDi(int a[], int b) {
    mem(c);
    c[0] = a[0];
    for (int i = a[0]; i >= 1; i--) {
        a[i] += a[i + 1] * 10;
        c[i] = a[i] / b;
        a[i] %= b;
    }
    while (c[c[0]] == 0 && c[0] > 1)
        c[0]--;
}

高精度除以高精度

void numcpy(int p[], int q[], int n) {
    for (int i = 1; i <= p[0]; i++)
        q[i + n - 1] = p[i];
    q[0] = p[0] + n - 1;
}
void minu(int a[], int b[])  //减法代替除法
{
    for (int i = 1; i <= a[0]; i++) {
        if (a[i] < b[i]) {
            a[i + 1]--;
            a[i] = a[i] + 10;
        }
        a[i] = a[i] - b[i];
    }
    while (a[a[0]] == 0 && a[0] > 1)
        a[0]--;
}
int main() {
    init(a);
    init(b);
    c[0] = a[0] - b[0] + 1;  //第0个为位数
    for (int i = c[0]; i >= 1; i--) {
        memset(temp, 0, sizeof(temp));
        numcpy(b, temp, i);  //将b移动i-1位,保存到temp中
        while (compare(a, temp) >= 0) {
            c[i]++;
            minu(a, temp);
        }
    }
    while (c[c[0]] == 0 && c[0] > 0)
        c[0]--;
    print(c);  //商
    cout << endl;
    print(a);  //余数
}

完全版封装大数

const int N = 1005;
struct bign {
    int len, s[N];
    bign() {
        memset(s, 0, sizeof(s));
        len = 1;
    }
    bign(int num) { *this = num; }
    bign(char* num) { *this = num; }
    bign operator=(int num) {
        char c[N];
        sprintf(c, "%d", num);
        *this = c;
        return *this;
    }
    bign operator=(const char* num) {
        len = strlen(num);
        for (int i = 0; i < len; i++)
            s[i] = num[len - 1 - i] - '0';
        return *this;
    }
    string str() {
        string res = "";
        for (int i = 0; i < len; i++)
            res = (char)(s[i] + '0') + res;
        return res;
    }
    void clean() {
        while (len > 1 && !s[len - 1])
            len--;
    }
    bign operator+(const bign& b) {
        bign c;
        c.len = 0;
        for (int i = 0, g = 0; g || i < len || i < b.len; i++) {
            int x = g;
            if (i < len)
                x += s[i];
            if (i < b.len)
                x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    bign operator-(const bign& b) {
        bign c;
        c.len = 0;
        int x;
        for (int i = 0, g = 0; i < len; i++) {
            x = s[i] - g;
            if (i < b.len)
                x -= b.s[i];
            if (x >= 0)
                g = 0;
            else {
                x += 10;
                g = 1;
            };
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }
    bign operator*(const bign& b) {
        bign c;
        c.len = len + b.len;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < b.len; j++)
                c.s[i + j] += s[i] * b.s[j];
        for (int i = 0; i < c.len - 1; i++) {
            c.s[i + 1] += c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }
    bign operator/(const int& b) {
        bign c;
        c.len = len;
        int down = 0;
        for (int i = len - 1; i >= 0; i--) {
            c.s[i] = (s[i] + down * 10) / b;
            down = s[i] + down * 10 - c.s[i] * b;
        }
        c.clean();
        return c;
    }
    bign operator%(const int& b) {
        bign c;
        c.len = len;
        int down = 0;
        for (int i = len - 1; i >= 0; i--) {
            down = ((down * 10) % b + s[i]) % b;
        }
        return down;
    }
    bign operator^(const int& b) {
        bign c, ret(1);
        if (b == 0)
            return 1;
        if (b == 1)
            return *this;
        int m = b;
        int i;
        while (m > 1) {
            c = *this;
            for (i = 1; (i << 1) <= m; i <<= 1)
                c = c * c;
            m -= i;
            ret = ret * c;
            if (m == 1)
                ret = ret * (*this);
        }
        return ret;
    }
    bool operator<(const bign& b) {
        if (len != b.len)
            return len < b.len;
        for (int i = len - 1; i >= 0; i--)
            if (s[i] != b.s[i])
                return s[i] < b.s[i];
        return false;
    }
    bign operator+=(const bign& b) {
        *this = *this + b;
        return *this;
    }
    bign operator-=(const bign& b) {
        *this = *this - b;
        return *this;
    }
};
istream& operator>>(istream& in, bign& x) {
    string s;
    in >> s;
    x = s.c_str();
    return in;
}
ostream& operator<<(ostream& out, bign& x) {
    out << x.str();
    return out;
}
int main() {
    bign a, b, c;
    // cin >> a >> b;
    // c = a + b;
    // cout << c << endl;
    bign k;
    int l;
    cin >> k >> l;
    a = (k ^ l);
    cout << a << endl;
}

高精快速幂+压位

int AchengB() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= a[0]; ++i) {
        for (int j = 1; j <= b[0]; ++j) {
            c[i + j - 1] += a[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    c[0] = a[0] + b[0];
    while (c[c[0]] == 0 && c[0] > 1)
        --c[0];
    for (int i = 1; i <= c[0]; ++i) {
        a[i] = c[i];
    }
    return c[0] > 500 ? 500 : c[0];  //压位，高于500位的不用再计算
}
int BchengB() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= b[0]; ++i) {
        for (int j = 1; j <= b[0]; ++j) {
            c[i + j - 1] += b[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    c[0] = b[0] + b[0];
    while (c[c[0]] == 0 && c[0] > 1)
        --c[0];
    for (int i = 1; i <= c[0]; ++i) {
        b[i] = c[i];
    }
    return c[0] > 500 ? 500 : c[0];
}

void power() {
    while (P) {
        if (P & 1)
            a[0] = AchengB();
        P >>= 1;
        b[0] = BchengB();
    }
}

二维差分

rep(i, 1, t) {
    cin >> a >> b >> c >> d;
    sum[a][b]++;
    sum[a][d + 1]--;
    sum[c + 1][b]--;
    sum[c + 1][d + 1]++;
}
rep(i, 1, n) {
    rep(j, 1, m) {
        sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        ans = max(ans, sum[i][j]);
    }
}

数据离散化

保序离散化

vector<int> 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
}

非保序离散化

unordered_map<int, int> mp;
int res;
int find(int x) {
    if (mp.count(x) == 0)
        return mp[x] = ++res;
    return mp[x];
}

RMQ(ST表查询区间最值)

// 以最大值为例
const int N = 200010, M = 18;
int n, m;
int w[N];
int f[N][M];
void init() {
    for (int j = 0; j < M; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            if (!j)
                f[i][j] = w[i];
            else
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}
int query(int l, int r) {
    int len = r - l + 1;
    int k = log(len) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    init();
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << endl;
    }
}