读入挂

发表于 2018-08-15 更新于 2023-12-05 分类于乱七八糟阅读次数：

请用文件读入!

struct fastIO{
	char s[100000]; int it,len;
	fastIO(){it = len = 0;}
	inline char get(){
		if (it < len) return s[it++];
    it = 0; len = fread(s, 1, 100000, stdin);
		if (len == 0) return EOF;
    else return s[it++];
	}
	bool notend(){
		char c = get();
		while(c == ' ' || c == '\n') c = get();
		if (it > 0) it--;
		return c != EOF;
	}
}_buff;
inline ll getNum(){
	ll r = 0; bool ng = 0; 
  char c = _buff.get();
	while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
	if (c == '-') ng = 1, c = _buff.get();
	while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
	return ng ? -r : r;
}

表达式计算

发表于 2018-08-14 更新于 2023-12-05 分类于乱七八糟阅读次数：

优先级

乘除 > 加减 > 左括号( > 右括号)

计算过程

维护一个操作数栈，一个操作符栈。

每次遇到一个数字或 ‘(‘ 压栈。

对于 +-*/ 符号，如果当前符号优先级小于等于栈顶符号，则进行计算，弹出栈顶，直到优先级大于栈顶符号，将当前符号压栈。

对于 ) 符号，不断出栈计算，直到遇到第一个 (。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;

char s[maxn];

int get(char ch){
    if (ch == '+' || ch == '-') return 1;
    if (ch == '*' || ch == '/') return 2;
    if (ch == '(') return 0;
    return -1;
}
int cmp(char x, char y){
    return get(x) <= get(y);
}

double cal(){
    stack<double> num; stack<char> ope;
    int len = strlen(s); double ans = 0;
    for (int i = 0; i < len; i++){
        if (s[i] >= '0' && s[i] <= '9') num.push(double(s[i] - '0'));
        else{
            if (s[i] == '(') {
                ope.push(s[i]); continue;
            }
            int flag = 0;
            while (!ope.empty() && cmp(s[i], ope.top())){
                char ch = ope.top(); 
                if (s[i] == ')'){
                    if (flag) break;
                    if (ch == '(') flag = 1;
                }
                ope.pop();
                if (ch == '*'){
                    double x = num.top(); num.pop();
                    double y = num.top(); num.pop();
                    num.push(x * y);
                }
                if (ch == '/'){
                    double x = num.top(); num.pop();
                    double y = num.top(); num.pop();
                    num.push(y / x);
                }
                if (ch == '+'){
                    double x = num.top(); num.pop();
                    double y = num.top(); num.pop();
                    num.push(x + y);
                }
                if (ch == '-'){
                    double x = num.top(); num.pop();
                    double y = num.top(); num.pop();
                    num.push(y - x);
                }
            }
            if (s[i] != ')') ope.push(s[i]);
        }
    }
    return ans = num.top();
}

int main(){
    int T; scanf("%d", &T);
    while (T--){
        scanf("%s", s + 1);
        int len = strlen(s + 1); s[0] = '(', s[len + 1] = ')'; s[len + 2] = '\0';
        printf("%.2lf\n", cal());
    }
    return 0;
}

Treap

发表于 2018-08-14 更新于 2023-12-05 分类于数据结构，平衡树阅读次数：

inline int rand(){
    static int seed = 233;
    return seed = int(seed * 48271LL % 2147483647);
}

struct Treap{
    int ch[maxn][2], key[maxn], size[maxn], rnd[maxn], cnt[maxn], sz, root;
    Treap(){ root = sz = 0; }
    void clear(){ root = sz = 0; }
    void pushup(int rt){ size[rt] = size[ch[rt][0]] + size[ch[rt][1]] + cnt[rt]; }
    void rot(int& x, int k){
        int v = ch[x][k ^ 1];
        ch[x][k ^ 1] = ch[v][k];
        ch[v][k] = x;
        x = v;
        pushup(ch[x][k]); pushup(x);
    }
    void insert(int& x, int val){
        if (!x){
            x = ++sz;
            ch[x][0] = ch[x][1] = 0;
            key[x] = val; rnd[x] = rand();
            size[x] = cnt[x] = 1;
            return;
        }
        if (key[x] == val){
            cnt[x]++; pushup(x); 
            return;
        }
        int k = val > key[x];
        insert(ch[x][k], val);
        if (rnd[x] < rnd[ch[x][k]]) rot(x, k ^ 1);
        pushup(x);
    }
    void del(int& x, int val){
        if (!x) return;
        if (key[x] == val){
            if (cnt[x] > 1) {
                cnt[x]--; pushup(x); 
                return;
            }
            if (ch[x][0] || ch[x][1]){
                if (!ch[x][1] || rnd[ch[x][0]] > rnd[ch[x][1]]){
                    rot(x, 1); del(ch[x][1], val);
                }
                else {
                    rot(x, 0); del(ch[x][0], val);
                }
                pushup(x);
                return;
            }
            x = 0;
            return;
        }
        del(ch[x][val > key[x]], val);
        pushup(x);
    }
    int find(int x, int val){
        if (!x) return 0;
        if (val == key[x]) return size[ch[x][0]] + 1;
        else if (val < key[x]) return find(ch[x][0], val);
        else return size[ch[x][0]] + cnt[x] + find(ch[x][1], val);
    }
    int findx(int x, int rank){
        if (!x) return inf;
        if (rank <= size[ch[x][0]]) return findx(ch[x][0], rank);
        else if (rank <= size[ch[x][0]] + cnt[x]) return key[x];
        else return findx(ch[x][1], rank - size[ch[x][0]] - cnt[x]);
    }
    int prev(int v){
        int x = root, ans = 0;
        while (x){
            if (v > key[x]) ans = key[x], x = ch[x][1];
            else x = ch[x][0];
        }
        return ans;
    }
    int succ(int v){
        int x = root, ans = 0;
        while (x){
            if (v < key[x]) ans = key[x], x = ch[x][0];
            else x = ch[x][1];
        }
        return ans;
    }
}f;

计算几何

发表于 2018-08-14 更新于 2023-12-05 分类于计算几何阅读次数：

const double eps = 1e-5;
const double pi = acos(-1.0);

inline int dcmp(double x) { 
    // double大小比较，考虑精度eps
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
inline int zero(double x) {
    return fabs(x) < eps;
}

struct Point {
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y){}
};
typedef Point Vector;

Vector operator + (Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (Point a, Point b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (Vector a, double p) { return Vector(a.x * p, a.y * p); }
Vector operator / (Vector a, double p) { return Vector(a.x / p, a.y / p); }
bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }

bool operator == (const Point& a, const Point& b) {
    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

double dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double length(Vector a) { return sqrt(a.x * a.x + a.y * a.y); }
double distance(Point a, Point b) { return length(b - a); }
double angle(Vector a, Vector b) { return acos(dot(a, b) / length(a) / length(b)); }
double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
double xmult(Point a, Point b, Point c) {
    // 0 -> 三点共线
    // + -> AC 在 AB 的逆时针方向
    // - -> AC 在 AB 的顺时针方向 
    return cross(b - a, c - a);
}
double area2(Vector a, Vector b, Vector c) { return cross(b - a, c - a); }

Vector rotate(Vector a, double rad) { 
    return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); 
}
Vector normal(Vector a) { // 计算单位法线，确保a不是零向量
    double l = length(a); return Vector(-a.y / l, a.x / l); 
}
Vector getNormal(Vector a) { return Vector(-a.y, a.x); }

// 直线表示： 已知直线上两个不同点A和B，则方向向量为（B-A），参数方程为 A + (B - A) t
// 直线 t 无限制，射线 t > 0，线段 t 在 0 到 1 之间
struct Line {
    Point p; Vector v;
    Line(Point a, Point b) : p(a), v(b - a) {}
};

Point getLineIntersection(Point p, Vector v, Point q, Vector w) {
    // P + tv 和 Q + wv 有唯一交点，当且仅当 cross(v,w) != 0
    Vector u = p - q;
    double t = cross(w, u) / cross(v, w);
    return p + v * t;
}
double getDistanceToLine(Point p, Point a, Point b) {
    // P 到 AB 的距离
    Vector v1 = b - a, v2 = p - a;
    return fabs(cross(v1, v2)) / length(v1);
}
double getDistanceToSegment(Point p, Point a, Point b) {
    // P 到线段 AB 的距离
    if (a == b) return length(p - a);
    Vector v1 = b - a, v2 = p - a, v3 = p - b;
    if (dcmp(dot(v1, v2)) < 0) return length(v2);
    else if (dcmp(dot(v1, v3)) > 0) return length(v3);
    else return fabs(cross(v1, v2)) / length(v1);
}
Point getLineProjection(Point p, Point a, Point b) {
    Vector v = b - a;
    return a + v * (dot(v, p - a) / dot(v, v));
}
bool segmentProperIntersection(Point a1, Point b1, Point a2, Point b2) {
    // 线段重合？
    // 线段相交在端点？
    // 不考虑上述两个case，线段A1B1,A2B2相交 -> 1
    double c1 = cross(b1 - a1, a2 - a1), c2 = cross(b1 - a1, b2 - a1);
    double c3 = cross(b2 - a2, a1 - a2), c4 = cross(b2 - a2, b1 - a2);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
bool onSegment(Point p, Point a1, Point a2) {
    // 点是否在一条线段上（不包含端点）
    return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0;
}
// p 是否在直线 a + v * t = 0 上
bool onLine(Point p, Vector v, Point a) {return dcmp(cross(v, p - a)) == 0;}
// 直线方向向量 v, P点到定点 A 的向量 t, 返回 P 点的参数 t
double getPosOnLine(Vector v, Vector t) {
    if (dcmp(v.x) == 0) return t.y / v.y;
    return t.x / v.x;
}

// 获取直线与圆的交点，直线 p + v * t = 0, 圆 (x - o.x) ^ 2 + (x - o.y) ^ 2 = r ^ 2
// 返回交点个数和点在直线上的参数 t1 和 t2
int getLineCircleIntersection(Point p, Vector v, Point o, double r, double &t1, double &t2) {
    double a = v.x, b = p.x - o.x, c = v.y, d = p.y - o.y;
    double e = a * a + c * c, f = 2 * (a * b + c * d), g = b * b + d * d - r * r;
    double delta = f * f - 4 * e * g;
    if (dcmp(delta) < 0)
        return 0;
    if (dcmp(delta) == 0){
        t1 = t2 = -f / (2 * e);
        return 1;
    }
    t1 = (-f - sqrt(delta)) / (2 * e);
    t2 = (-f + sqrt(delta)) / (2 * e);
    return 2;
}

double polygonArea(Point* p, int n) {
    // 计算多边形的面积，顶点要按顺序
    double area = 0;
    for (int i = 1; i < n - 1; i++)
        area += cross(p[i] - p[0], p[i + 1] - p[0]);
    return area / 2;
}

阅读全文 »

树链剖分

发表于 2018-08-14 更新于 2023-12-05 分类于树阅读次数：

树链剖分：树链更新和查询 + 子树更新和查询

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;

int to[maxn << 1], nxt[maxn << 1], head[maxn], tot = 0;
void add(int x, int y){
    to[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}

int n, m, a[maxn];

namespace hld{
    ll wt[maxn], tree[maxn << 2], laz[maxn << 2];
    void pushup(int rt){tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];}
    void pushdown(int rt, int ln, int rn){
        if (!laz[rt]) return;
        tree[rt << 1] += 1ll * laz[rt] * ln; tree[rt << 1 | 1] += 1ll * laz[rt] * rn;
        laz[rt << 1] += 1ll * laz[rt]; laz[rt << 1 | 1] += 1ll * laz[rt];
        laz[rt] = 0;
    }
    void build(int l, int r, int rt){
        if (l == r){
            laz[rt] = 0; tree[rt] = wt[l];
            return;
        }
        int m = (l + r) >> 1;
        build(lson); build(rson);
        pushup(rt);
    }
    void update(int i, int x, int l, int r, int rt){
        if (l == r){
            tree[rt] += 1ll * x;
            return;
        }
        int m = (l + r) >> 1; pushdown(rt, m - l + 1, r - m);
        if (i <= m) update(i, x, lson);
        else update(i, x, rson);
        pushup(rt);
    }
    void update(int L, int R, int x, int l, int r, int rt){
        if (L <= l && r <= R){
            tree[rt] += 1ll * x * (r - l + 1); laz[rt] += 1ll * x;
            return;
        }
        int m = (l + r) >> 1; pushdown(rt, m - l + 1, r - m);
        if (L <= m) update(L, R, x, lson);
        if (R > m) update(L, R, x, rson);
        pushup(rt);
    }
    ll query(int L, int R, int l, int r, int rt){
        if (L <= l && r <= R) return tree[rt];
        int m = (l + r) >> 1; pushdown(rt, m - l + 1, r - m);
        ll s = 0;
        if (L <= m) s += query(L, R, lson);
        if (R > m) s += query(L, R, rson);
        return s;
    }

    int siz[maxn], dep[maxn], fa[maxn], son[maxn], top[maxn], id[maxn], cnt = 0;
    void dfs(int p, int d, int old){
        dep[p] = d; fa[p] = old; siz[p] = 1;
        int m = -1;
        for (int i = head[p]; i; i = nxt[i]){
            int v = to[i];
            if (v == fa[p]) continue;
            dfs(v, d + 1, p);
            siz[p] += siz[v];
            if (siz[v] > m) son[p] = v, m = siz[v];
        }
    }
    void dfs(int p, int tp){
        id[p] = ++cnt; top[p] = tp; wt[cnt] = a[p];
        if (!son[p]) return;
        dfs(son[p], tp);
        for (int i = head[p]; i; i = nxt[i]){
            int v = to[i];
            if (v == fa[p] || v == son[p]) continue;
            dfs(v, v);
        }
    }
    void init(){
        cnt = 0; dfs(1, 1, 0); dfs(1, 1); build(1, n, 1);
    }

    int qpath(int x, int y){
        int ans = 0;
        while (top[x] != top[y]){
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            ans = (ans + query(id[top[x]], id[x], 1, n, 1)) % p;
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y);
        ans = (ans + query(id[x], id[y], 1, n, 1)) % p;
        return ans;
    }
    int qson(int x){
        return query(id[x], id[x] + siz[x] - 1, 1, n, 1);
    }
    void upath(int x, int y, int k){
        k %= p;
        while (top[x] != top[y]){
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            update(id[top[x]], id[x], k, 1, n, 1);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y);
        update(id[x], id[y], k, 1, n, 1);
    }
    void uson(int x, int k){
        update(id[x], id[x] + siz[x] - 1, k % p, 1, n, 1);
    }
}

伸展树区间翻转

发表于 2018-08-09 更新于 2023-12-05 分类于数据结构，平衡树阅读次数：

#include <cstdio>
#include <algorithm>
const int maxn = 100000 + 5;
const int inf = 1 << 30;

int a[maxn];
struct Splay{
    int f[maxn], ch[maxn][2], size[maxn], rev[maxn] = {0}, key[maxn], root, sz;
    Splay(){
        root = sz = size[0] = rev[0] = f[0] = 0; key[0] = inf;
    }
    int get(int x){return ch[f[x]][1] == x;}
    void pushup(int x){
        size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;
    }
    void pushdown(int x){
        if (!rev[x]) return;
        std::swap(ch[x][0], ch[x][1]);
        rev[ch[x][0]] ^= 1; rev[ch[x][1]] ^= 1; rev[x] = 0;
    }
    int build(int l, int r, int rt){
        if (l > r) return 0;
        int m = (l + r) >> 1, tot = ++sz;
        key[tot] = a[m]; f[tot] = rt; rev[tot] = 0;
        ch[tot][0] = build(l, m - 1, tot);
        ch[tot][1] = build(m + 1, r, tot);
        pushup(tot);
        return tot;
    }
    void rot(int x){
        int old = f[x], oldf = f[old], tp = get(x);
        pushdown(old); pushdown(x);
        ch[old][tp] = ch[x][tp ^ 1]; f[ch[old][tp]] = old;
        ch[x][tp ^ 1] = old; f[old] = x; 
        f[x] = oldf;
        if (oldf) ch[oldf][ch[oldf][1] == old] = x;
        pushup(old); pushup(x);
    }
    void splay(int x, int tar){
        for (int fa; (fa = f[x]) != tar; rot(x))
            if (f[fa] != tar)
                rot(get(fa) == get(x) ? fa : x);
        if (!tar) root = x;
    }
    int find(int k){
        int tot = root;
        while (1){
            pushdown(tot);
            if (k <= size[ch[tot][0]]) tot = ch[tot][0];
            else {
                k -= size[ch[tot][0]] + 1;
                if (!k) return tot;
                tot = ch[tot][1];
            }
        }
    }
    void reverse(int l, int r){
        int a = find(l), b = find(r + 2);
        splay(a, 0); splay(b, a);
        rev[ch[b][0]] ^= 1;
    }
    void print(int p){
        pushdown(p);
        if (ch[p][0]) print(ch[p][0]);
        if (key[p] != inf) printf("%d ", key[p]);
        if (ch[p][1]) print(ch[p][1]);
    }
}f;

int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) a[i + 1] = i;
    a[1] = inf; a[n + 2] = inf;
    f.root = f.build(1, n + 2, 0);
    while (m--){
        int l, r; scanf("%d%d", &l, &r);
        f.reverse(l, r);
    }
    f.print(f.root);
    return 0;
}

伸展树

发表于 2018-08-07 更新于 2023-12-05 分类于数据结构，平衡树阅读次数：

cnt[x] 表示 x 的出现次数，size[x] 表示以 x 为根节点的子树大小。

clean(int x)
清除当前节点
get(int x)
获取当前节点是父节点的左右孩子
update(int x)
更新当前节点的 size
rot(int x)
将当前节点向上旋转
splay(int x)
将当前节点伸展为根节点
insert(int v)
创建一个新的节点，并将其旋转至根
find(int v)
返回键为 v 的节点的名次，并将其旋转至根节点
findx(int x)
返回排名为 x 的键
prev()
返回根节点的前驱
succ()
返回根节点的后继
del(int v)
删除一个键为 v 的节点

模板:

struct Splay{
    int f[maxn], ch[maxn][2], key[maxn], cnt[maxn], size[maxn], sz = 0, root = 0;
    Splay(){sz = root = 0;}
    void clear(int x){
        ch[x][0] = ch[x][1] = f[x] = key[x] = cnt[x] = size[x] = 0;
    }
    int get(int x){
        return ch[f[x]][1] == x;
    }
    void update(int x){
        if (!x) return;
        size[x] = cnt[x];
        if (ch[x][0]) size[x] += size[ch[x][0]];
        if (ch[x][1]) size[x] += size[ch[x][1]];
    }
    void rot(int x){
        int old = f[x], oldf = f[old], tp = get(x);
        ch[old][tp] = ch[x][tp ^ 1]; f[ch[old][tp]] = old;
        f[old] = x; ch[x][tp ^ 1] = old;
        f[x] = oldf;
        if (oldf) ch[oldf][ch[oldf][1] == old] = x;
        update(old); update(x);
    }
    void splay(int x){
        for (int fa; fa = f[x]; rot(x))
            if (f[fa]) rot(get(x) == get(fa) ? fa : x);
        root = x;
    }
    int insert(int v){
        if (root == 0){
            sz++; ch[sz][0] = ch[sz][1] = f[sz] = 0;
            key[sz] = v; cnt[sz] = 1; size[sz] = 1; 
            root = sz;
            return 1;
        }
        int tot = root, fa = 0;
        while (1){
            if (key[tot] == v){
                cnt[tot]++; update(tot); update(fa);
                splay(tot);
                return cnt[tot];
            }
            fa = tot;
            tot = ch[tot][v > key[tot]];
            if (tot == 0){
                sz++; ch[sz][0] = ch[sz][1] = 0; 
                key[sz] = v; cnt[sz] = size[sz] = 1;
                f[sz] = fa; ch[fa][v > key[fa]] = sz;
                update(fa); splay(sz);
                break;
            }
        }
        return 1;
    }
    int find(int v){
        int ans = 0, tot = root;
        while (1){
            if (v < key[tot]) tot = ch[tot][0];
            else {
                ans += (ch[tot][0] ? size[ch[tot][0]] : 0);
                if (v == key[tot]){
                    splay(tot); return ans + 1;
                }
                ans += cnt[tot];
                tot = ch[tot][1];
            } 
        }
        return 0;
    }
    int findx(int x){
        int tot = root;
        while (1){
            if (ch[tot][0] && x <= size[ch[tot][0]]) tot = ch[tot][0];
            else {
                int t = (ch[tot][0] ? size[ch[tot][0]] : 0) + cnt[tot];
                if (x <= t) return key[tot];
                x -= t; tot = ch[tot][1];
            }
        }
        return -1;
    }
    int prev(){
        int tot = ch[root][0];
        while (ch[tot][1]) tot = ch[tot][1];
        return tot;
    }
    int succ(){
        int tot = ch[root][1];
        while (ch[tot][0]) tot = ch[tot][0];
        return tot;
    }
    void del(int v){
        find(v);
        if (cnt[root] > 1){
            cnt[root]--; return;
        }
        if (!ch[root][0] && !ch[root][1]){
            clean(root); root = 0; return;
        }
        if (!ch[root][0]){
            int old = root; root = ch[root][1]; f[root] = 0;
            clean(old); return;
        }
        else if (!ch[root][1]){
            int old = root; root = ch[root][0]; f[root] = 0;
            clean(old); return;
        }
        int lf = prev(), old = root;
        splay(lf); f[ch[old][1]] = root; ch[root][1] = ch[old][1];
        clean(old); update(root);
    }
};

线段树

发表于 2018-08-07 更新于 2023-12-05 分类于数据结构，线段树阅读次数：

线段树模板

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn = 100000 + 5;

// sum 节点, add 懒惰， a 原数组
int sum[maxn << 2], add[maxn << 2], a[maxn], n;
void pushup(int rt){sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}
void pushdown(int rt, int ln, int rn){
    if (add[rt]){
        add[rt << 1] += add[rt]; add[rt << 1 | 1] += add[rt];
        sum[rt << 1] = add[rt] * ln; sum[rt << 1 | 1] = add[rt] * rn;
        add[rt] = 0;
    }
}
void build(int l, int r, int rt){
    if (l == r){
        sum[rt] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(lson); build(rson);
    pushup(rt);
}
void update(int i, int x, int l, int r, int rt){
    if (l == r){
        sum[rt] += x;
        return;
    }
    int m = (l + r) >> 1;
    if (i <= m) update(i, x, lson);
    else update(i, x, rson);
    pushup(rt);
}
void update(int L, int R, int x, int l, int r, int rt){
    if (L <= l && r <= R){
        sum[rt] += x * (r - l + 1);
        add[rt] += x;
        return;
    }
    int m = (l + r) >> 1;
    pushdown(rt, m - l + 1, r - m);
    if (L <= m) update(L, R, x, lson);
    if (R > m) update(L, R, x, rson);
    pushup(rt);
}
int query(int i, int l, int r, int rt){
    if (l == r){
        return sum[rt];
    }
    int m = (l + r) >> 1;
    if (i <= l) return query(i, lson);
    return query(i, rson);
}
int query(int L, int R, int l, int r, int rt){
    if (L <= l && r <= R){
        return sum[rt];
    }
    int m = (l + r) >> 1;
    pushdown(rt, m - l + 1, r - m);
    int ans = 0;
    if (L <= m) ans += query(L, R, lson);
    if (R > m) ans += query(L, R, rson);
    return ans;
}

区间加乘双标记

int n, m, p;
ll a[maxn], sum[maxn << 2], add[maxn << 2], mul[maxn << 2];

void pushup(int rt){ sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % p; }
void pushdown(int rt, int ln, int rn){
    int ls = rt << 1, rs = rt << 1 | 1;
    if (mul[rt] != 1){
        mul[ls] *= mul[rt]; mul[rs] *= mul[rt];
        add[ls] *= mul[rt]; add[rs] *= mul[rt];
        sum[ls] *= mul[rt]; sum[rs] *= mul[rt];
        mul[rt] = 1;
    }
    if (add[rt] != 0){
        add[ls] += add[rt]; add[rs] += add[rt];
        sum[ls] += add[rt] * ln; sum[rs] += add[rt] * rn;
        add[rt] = 0;
    }
}
void build(int l, int r, int rt){
    mul[rt] = 1;
    if (l == r){
        sum[rt] = a[l] % p; return;
    }
    int m = l + r >> 1;
    build(lson); build(rson);
    pushup(rt);
}
void update1(int L, int R, int x, int l, int r, int rt){
    if (L <= l && r <= R){
        sum[rt] *= x;
        mul[rt] *= x;
        add[rt] *= x;
        return;
    }
    int m = l + r >> 1; pushdown(rt, m - l + 1, r - m);
    if (L <= m) update1(L, R, x, lson);
    if (R > m) update1(L, R, x, rson);
    pushup(rt);
}
void update2(int L, int R, int x, int l, int r, int rt){
    if (L <= l && r <= R){
        sum[rt] += x * (r - l + 1);
        add[rt] += x;
        return;
    }
    int m = l + r >> 1; pushdown(rt, m - l + 1, r - m);
    if (L <= m) update2(L, R, x, lson);
    if (R > m) update2(L, R, x, rson);
    pushup(rt);
}

区间取模

int n, m, a[maxn], mx[maxn << 2];;
ll sum[maxn << 2];

void pushup(int rt){
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
void build(int l, int r, int rt){
    if (l == r) {
        sum[rt] = mx[rt] = a[l]; return;
    }
    int m = l + r >> 1;
    build(lson); build(rson);
    pushup(rt);
}
void update(int i, int x, int l, int r, int rt){
    if (l == r){
        sum[rt] = mx[rt] = x; return;
    }
    int m = l + r >> 1;
    if (i <= m) update(i, x, lson);
    else update(i, x, rson);
    pushup(rt);
}
void update(int L, int R, int mod, int l, int r, int rt){
    if (L > r || l > R || mx[rt] < mod) return;
    if (L <= l && r <= R && l == r){
        sum[rt] = mx[rt] = mx[rt] % mod;
        return;
    }
    int m = l + r >> 1;
    update(L, R, mod, lson); update(L, R, mod, rson);
    pushup(rt);
}

优先级

计算过程

clean(int x)

get(int x)

update(int x)

rot(int x)

splay(int x)

insert(int v)

find(int v)

findx(int x)

prev()

succ()

del(int v)

模板:

线段树模板

区间加乘双标记

区间取模