1.Hotel

题意：有n个房间m次询问，房间初始都为空。
操作1：输入x。在1-n房间中找到连续x个空房，输出这写房间最左端的房间号，然后把这些房间标记为非空。
操作2：输入l,r。将房间号l-l+r-1的房间改为空房。
$区间修改，区间查询，维护区间最大连续空房数和从左开始最长连续，从右开始最长连续和lazytag$
$pushup有些复杂，更新区间从左最长连续空房时看一下能否从右边继承一从左开始的，右边同理$

#include <bits/stdc++.h>

#define endl "\n"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;

struct node {
    int l, r;
    int lx, rx, s;
    int tag;
}tr[N*4];
int n, m;

void push_up(int u) {
    if(tr[u<<1].lx == tr[u<<1].r - tr[u<<1].l + 1) {
        tr[u].lx = tr[u<<1].lx + tr[u<<1|1].lx;
    } else tr[u].lx = tr[u<<1].lx;

    if(tr[u<<1|1].rx == tr[u<<1|1].r - tr[u<<1|1].l + 1) {
        tr[u].rx = tr[u<<1|1].rx + tr[u<<1].rx;
    } else tr[u].rx = tr[u<<1|1].rx;
    tr[u].s = max({tr[u<<1].s, tr[u<<1|1].s, tr[u<<1].rx + tr[u<<1|1].lx});
}

void push_down(int u) {
    if(tr[u].tag == 0) return ;
    if(tr[u].tag == 1) {
        tr[u<<1].tag = tr[u<<1|1].tag = 1;
        tr[u<<1].s = tr[u<<1].lx = tr[u<<1].rx = 0;
        tr[u<<1|1].s = tr[u<<1|1].lx = tr[u<<1|1].rx = 0;
    } else if (tr[u].tag == 2) {
        tr[u<<1].tag = tr[u<<1|1].tag = 2;
        tr[u<<1].s = tr[u<<1].lx = tr[u<<1].rx = tr[u<<1].r - tr[u<<1].l + 1;
        tr[u<<1|1].s = tr[u<<1|1].lx = tr[u<<1|1].rx = tr[u<<1|1].r - tr[u<<1|1].l + 1;
    }
    tr[u].tag = 0;
}


void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if(l == r) {
        tr[u].lx = tr[u].rx = tr[u].s = 1;
    } else {
        int mid = l + r >> 1;
        build(u<<1, l, mid);
        build(u<<1|1, mid+1, r);
        push_up(u);
    }
}

void update(int u, int l, int r, int op) {
    if(l <= tr[u].l && tr[u].r <= r) {
        if(op == 1) {
            tr[u].s = tr[u].lx = tr[u].rx = 0;
        } else if (op == 2) {
            tr[u].s = tr[u].lx = tr[u].rx = tr[u].r - tr[u].l + 1;
        }
        tr[u].tag = op;
    } else {
        push_down(u);
        int mid = tr[u].r + tr[u].l >> 1;
        if(l <= mid) update(u<<1, l, r, op);
        if(r > mid) update(u<<1|1, l, r, op);
        push_up(u);
    }
}

int query(int u, int x) {
    if(tr[u].l == tr[u].r) {
        return tr[u].l;
    } else {
        push_down(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(tr[u<<1].s >= x) return query(u<<1, x);
        else if(tr[u<<1].rx + tr[u<<1|1].lx >= x) return mid - tr[u<<1].rx + 1;
        else if(tr[u<<1|1].s >= x) return query(u<<1|1, x);
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    build(1, 1, n);

    while(m --) {
        int op, l, r, x;
        cin >> op;
        if(op == 1) {
            cin >> x;
            if(tr[1].s < x) {
                cout << 0 << endl;
            } else {
                int l = query(1, x);
                cout << l << endl;
                update(1, l, l+x-1, 1);
            }
        } else {
            cin >> l >> r;
            update(1, l, l+r-1, 2);
        }
    }
}

2. xor on segment（区间异或）

n个数的序列a，m次操作。
1.区间求和
2.区间xor
考虑到$a_i$最大只有1e5，我们可以用线段树维护区间中每一位的情况。求和的时候暴力跑一次区间中所有数位即可。
复杂度多了一个log(1e5)
当我们处理区间异或上x时，我们只需要看x的某位是不是1，如果是1，则区间翻转。
具体来说就是如果区间中原来这一位上有j个1，那么此时变成区间长度-j个1.

#include <bits/stdc++.h>

#define endl "\n"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;

int n, Q;
int a[N];
ll p[N];
struct node {
    int l, r;
    int v[22], tag;
}tr[4*N];

void push_up(int u) {
    for(int i = 0; i < 20; i ++) {
        tr[u].v[i] = tr[u<<1].v[i] + tr[u<<1|1].v[i];
    }
}

void push_down(int u) {
    for(int i = 0; i < 20; i ++) if(tr[u].tag >> i & 1){
        tr[u<<1].v[i] = tr[u<<1].r - tr[u<<1].l + 1 - tr[u<<1].v[i];
        tr[u<<1|1].v[i] = tr[u<<1|1].r - tr[u<<1|1].l + 1 - tr[u<<1|1].v[i];
    }
    tr[u<<1].tag ^= tr[u].tag, tr[u<<1|1].tag ^= tr[u].tag;
    tr[u].tag = 0;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if(l == r) {
        for(int i = 0; i < 20; i ++) if(a[l] >> i & 1) {
            tr[u].v[i] = 1;
        }
        tr[u].tag = 0;
    } else {
        int mid = l + r >> 1;
        build(u<<1, l, mid);
        build(u<<1|1, mid+1, r);
        push_up(u);
    }
}

void update(int u, int l, int r, int x) {
    if(l <= tr[u].l && tr[u].r <= r) {
        for(int i = 0; i < 20; i ++) if(x >> i & 1) {
            tr[u].v[i] = (tr[u].r - tr[u].l + 1) - tr[u].v[i];
        }
        tr[u].tag ^= x;
    } else {
        push_down(u);
        int mid = tr[u].r + tr[u].l >> 1;
        if(l <= mid) update(u<<1, l, r, x);
        if(r > mid) update(u<<1|1, l, r, x);
        push_up(u);
    }
}

ll query(int u, int l, int r) {
    if(l <= tr[u].l && tr[u].r <= r) {
        ll res = 0;
        for(int i = 0; i < 20; i ++) {
            res += 1ll * tr[u].v[i] * p[i];
        }
        return res;
    } else {
        push_down(u);
        int mid = tr[u].r + tr[u].l >> 1;
        ll res = 0;
        if(l <= mid) res = query(u<<1, l, r);
        if(r > mid) res += query(u<<1|1, l, r);
        return res; 
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    p[0] = 1;
    for(int i = 1; i <= 20; i ++) {
        p[i] = p[i-1] * 2 * 1ll;
    }
    build(1, 1, n);

    cin >> Q;
    while(Q --) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if(op == 1) {
            cout << query(1, l, r) << endl;
        } else {
            cin >> x;
            update(1, l, r, x);
        }
    }
}

3. new year tree(dfs序)

给出一个n个结点的树，根为1，每个节点有一个颜色$c_i$,有m次操作
操作1：将以u为根的子树上所有节点颜色改为c
操作2：询问以u为跟的子树上的所有节点的颜色种类数
先跑一次dfs序，我们就将树上问题转换成区间上的问题了，那么就是简单的区间修改区间查询。
维护种类的话我们可以用二进制去维护，c最大才60，long long可以存的下

#include <bits/stdc++.h>

#define endl "\n"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 4e5 + 10;
const int mod = 1e9 + 7;

int n, m;
ll c[N];
vector<int> g[N];
int in[N], out[N], pos[N], idx;
struct node {
    int l, r;
    ll v, tag;
}tr[N*4];

void dfs(int u, int fa) {
    idx += 1;
    in[u] = idx;
    pos[idx] = u;
    for(auto v : g[u]) {
        if(v == fa) continue;
        dfs(v, u);
    }
    out[u] = idx;
}

void push_up(int u) {
    tr[u].v = tr[u<<1].v | tr[u<<1|1].v;
}

void push_down(int u) {
    if(tr[u].tag == 0) return ;
    tr[u<<1].v = tr[u].tag;
    tr[u<<1|1].v = tr[u].tag;
    tr[u<<1].tag = tr[u].tag;
    tr[u<<1|1].tag = tr[u].tag;
    tr[u].tag = 0;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if(l == r) {
        tr[u].v = 1ll << c[pos[l]];
        tr[u].tag = 0;
    } else {
        int mid = l + r >> 1;
        build(u<<1, l, mid);
        build(u<<1|1, mid+1, r);
        push_up(u);
    }
}

void update(int u, int l, int r, ll x) {
    if(l <= tr[u].l && tr[u].r <= r) {
        tr[u].v = 1ll << x;
        tr[u].tag = 1ll << x;
    } else {
        push_down(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) update(u<<1, l, r, x);
        if(r > mid) update(u<<1|1, l, r, x);
        push_up(u);
    }
}

ll query(int u, int l, int r) {
    if(l <= tr[u].l && tr[u].r <= r) {
        return tr[u].v;
    } else {
        push_down(u);
        int mid = tr[u].l + tr[u].r >> 1;
        ll res = 0;
        if(l <= mid) res |= query(u<<1, l, r);
        if(r > mid) res |= query(u<<1|1, l, r);
        return res;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    cin >> n >> m;

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

    for(int i = 1; i < n; i ++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0);
    build(1, 1, n);

    while(m --) {
        ll op, x, y;
        cin >> op;
        if(op == 1) {
            cin >> x >> y;
            update(1, in[x], out[x], y);
        } else {
            cin >> x;
            ll t = query(1, in[x], out[x]);
            int res = 0;
            for(ll i = t; i > 0; i -= (-i&i)) res ++;
            cout << res << endl;
        }
    }
}

4. The Child and Sequence(区间取模)

三个操作
1：区间求和 2：区间取模 3：单点修改
只有2操作比较难搞
考虑两种情况
区间最大值和模数的关系
1.max < mod，那么这次取模相当于没做
2.max >= mod, 那么这一次取模最多能得到max/2。所以一个数最多被操作log次。那么我们对每个取模操作都暴力做一下（类似开方）

#include <bits/stdc++.h>

#define endl "\n"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;

struct node {
    int l, r;
    ll s, mx;
}tr[N<<2];
int n, m;
ll a[N];

void push_up(int u) {
    tr[u].s = tr[u<<1].s + tr[u<<1|1].s;
    tr[u].mx = max(tr[u<<1].mx, tr[u<<1|1].mx);
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if(l == r) {
        tr[u].s = tr[u].mx = a[l];
    } else {
        int mid = l + r >> 1;
        build(u<<1, l, mid);
        build(u<<1|1, mid+1, r);
        push_up(u);
    }
}

void update(int u, int x, ll k) {
    if(tr[u].l == tr[u].r) {
        tr[u].s = tr[u].mx = k;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) update(u<<1, x, k); 
        else update(u<<1|1, x, k);
        push_up(u);
    }
}

void update_mod(int u, int l, int r, ll p) {
    if(l <= tr[u].l && tr[u].r <= r && tr[u].mx < p) return ;

    if(tr[u].l == tr[u].r) {
        tr[u].s %= p, tr[u].mx %= p;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) update_mod(u<<1, l, r, p);
        if(r > mid) update_mod(u<<1|1, l, r, p);
        push_up(u);
    }
}

ll query(int u, int l, int r) {
    if(l <= tr[u].l && tr[u].r <= r) {
        return tr[u].s;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        ll res = 0;
        if(l <= mid) res = query(u<<1, l, r);
        if(r > mid) res += query(u<<1|1, l, r);
        return res;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    build(1, 1, n);

    while(m --) {
        int op, l, r;
        cin >> op >> l >> r;

        if(op == 1) {
            cout << query(1, l, r) << endl;
        } else if (op == 2) {
            //区间mod
            ll x;
            cin >> x;
            update_mod(1, l, r, x);
        } else {
            update(1, l, r);
        }
    }
}

5. 无聊的数列（差分+线段树）

1:区间加等差数列
2:求某个位置上的数字
考虑维护差分，在[l, r]加等差数列即在$a_l加上首相，a_{l+1}....a_r加上公差，a_r+1 减去末项$
求某个数的时候直接求1~k位置的前缀和即可

#include <bits/stdc++.h>

#define endl "\n"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;

int n, m;
int a[N];
int d[N];
struct node {
    int l, r;
    ll s, tag;
}tr[N<<2];

void push_up(int u) {
    tr[u].s = tr[u<<1].s + tr[u<<1|1].s;
}

void push_down(int u) {
    if(!tr[u].tag) return ;
    tr[u<<1].tag += tr[u].tag, tr[u<<1|1].tag += tr[u].tag;
    tr[u<<1].s += 1ll * (tr[u<<1].r - tr[u<<1].l + 1) * tr[u].tag;
    tr[u<<1|1].s += 1ll * (tr[u<<1|1].r - tr[u<<1|1].l + 1) * tr[u].tag;
    tr[u].tag = 0;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if(l == r) {
        tr[u].s = d[l];
    } else {
        int mid = l + r >> 1;
        build(u<<1, l, mid);
        build(u<<1|1, mid+1, r);
        push_up(u);
    }
}

void update(int u, int l, int r, ll x) {
    if(l <= tr[u].l and tr[u].r <= r) {
        tr[u].tag += x;
        tr[u].s += 1ll * (tr[u].r - tr[u].l + 1) * x;
    } else {
        push_down(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) update(u<<1, l, r, x);
        if(r > mid) update(u<<1|1, l, r, x);
        push_up(u);
    }
}

ll query(int u, int l, int r) {
    if(l <= tr[u].l and tr[u].r <= r) {
        return tr[u].s;
    } else {
        push_down(u);
        int mid = tr[u].l + tr[u].r >> 1;
        ll res = 0;
        if(l <= mid) res = query(u<<1, l, r); 
        if(r > mid) res += query(u<<1|1, l, r);
        return res;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    build(1, 1, n);

    while(m --) {
        int op, l, r, k, d;
        cin >> op;
        if(op == 1) {
            cin >> l >> r >> k >> d;
            ll ed = (ll)(k + (r-l) * d);
            update(1, l, l, k);
            if(l+1 <= r) update(1, l+1, r, d);
            if(r+1 <= n) update(1, r+1, r+1, -ed);
        } else {
            cin >> k;
            cout << query(1, 1, k) << endl;
        }
    }

}

5. [区间加区间sin和（线段树+三角函数）] (https://www.luogu.com.cn/problem/P6327)

具体推导在代码中，维护sin和和cos和即可。

#include <bits/stdc++.h>

#define endl "\n"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;

struct node {
    int l, r;
    double ssin, ccos;
    ll tag;
    /*
    cos (x + y) = coscos - sinsin
    sin (x + y) = sincos + cossin
    */
}tr[N<<2];
int n;
int a[N];

void push_up(int u) {
    tr[u].ssin = tr[u<<1].ssin + tr[u<<1|1].ssin;
    tr[u].ccos = tr[u<<1].ccos + tr[u<<1|1].ccos;
}

/*
    val = [sin(a) + sin(b) + sin(c)] -> sin(a+v) + sin(b+v) + sin(c+v)

    sin(a)cos(v) + cos(a)sin(v) + sin(b)cos(v) + cos(b)sin(v) + sin(b)cos(v) + cos(b)sin(v) 
    --> sin(v) * [cos(a) + cos(b) + cos(c)] + cos(v) * [sin(a) + sin(b) + sin(c)]
*/

void update(int u, double sinx, double cosx) {
    double s = tr[u].ssin, c = tr[u].ccos;
    tr[u].ssin = s * cosx + c * sinx;
    tr[u].ccos = c * cosx - s * sinx;
}

void push_down(int u) {
    if(!tr[u].tag) return ;
    double sinx = sin(1.0*tr[u].tag);
    double cosx = cos(1.0*tr[u].tag);
    update(u<<1, sinx, cosx);
    update(u<<1|1, sinx, cosx);
    tr[u<<1].tag += tr[u].tag, tr[u<<1|1].tag += tr[u].tag;
    tr[u].tag = 0;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if(l == r) {
        tr[u].ssin = sin(1.0 * a[l]);
        tr[u].ccos = cos(1.0 * a[l]);
    } else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid+1, r);
        push_up(u);
    }
}

void modify(int u, int l, int r, ll v) {
    if(l <= tr[u].l && tr[u].r <= r) {
        update(u, sin(1.0*v), cos(1.0*v));
        tr[u].tag += v;
    } else {
        push_down(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u<<1, l, r, v);
        if(r > mid)modify(u<<1|1, l, r, v);
        push_up(u);
    }
}

double query(int u, int l, int r) {
    if(l <= tr[u].l && tr[u].r <= r) {
        return tr[u].ssin;
    } else {
        push_down(u);
        int mid = tr[u].l + tr[u].r >> 1;
        double ans = 0;
        if(l <= mid) ans += query(u<<1, l, r);
        if(r > mid) ans += query(u<<1|1, l, r);
        return ans;
    }

}


int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);

    scanf("%d", &n);

    for(int i = 1; i <= n; i ++) {
        scanf("%d", a+i);
    }

    build(1, 1, n);
    //cout << tr[1].ssin << endl;
    int Q;
    scanf("%d", &Q);

    while(Q --) {
        int op, l, r;
        ll x;
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d%d%d", &l, &r, &x);
            modify(1, l, r, x);
        } else {
            scanf("%d%d", &l, &r);
            printf("%.1lf\n", query(1, l, r));
        }   
    }
}