线段树

20240825

1. 区间查询 modify

2. 区间修改 query

原理:分治思想

懒标记模板题:

P3372 【模板】线段树 1

P3373 【模板】线段树 2

比较厉害的题目 P1637 三元上升子序列

Boss (Level. NOI-) TorCoder CF240F

时间复杂度 $ O(M • logN • 26) $

1. 统计一段区间[L, R]中每种字母出现的次数, 若奇数出现的次数至多1次, 可以回文;

2. 若有1种字母出现奇数次, 则中间位置放该字母, 剩下的字母按照字典序依次放;

3. 每种字母维护一颗关于下标的线段树, 数值为1或0表示出现/没出现该字母;

4. 询问时, 对于26种字母query, 并统计奇数出现的次数cnt, 若cnt>1, 则无解, 不修改

5. 修改时, 对每一种字母区间修改, 最多26次

20240825:代码还在写 祝我速切省选题 别忘了要点赞❤️…

20240826:写完了不一样的感受…

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 26;
int st[M];
char s[N];

struct Segment
{
    int l, r;
    int sum, add;
} tr[M][N << 2];

void pushup(int p, int u)
{
    tr[p][u].sum = tr[p][u << 1].sum + tr[p][u << 1 | 1].sum;
}

void pushdown(int p, int u)
{
    auto &root = tr[p][u], &left = tr[p][u << 1], &right = tr[p][u << 1 | 1];

    if (~root.add)
    {
        left.add = root.add;
        left.sum = (left.r - left.l + 1) * root.add;

        right.add = root.add;
        right.sum = (right.r - right.l + 1) * root.add;

        root.add = -1;
    }
}

void build(int p, int u, int l, int r)
{
    tr[p][u] = {l, r, 0, -1};

    if (l == r)
    {
        tr[p][u].sum = (s[l] - 'a' == p);
        return;
    }

    int mid = l + r >> 1;

    build(p, u << 1, l, mid);
    build(p, u << 1 | 1, mid + 1, r);

    pushup(p, u);
}

void modify(int p, int u, int l, int r, int d)
{
    if (tr[p][u].l >= l && tr[p][u].r <= r)
    {
        tr[p][u].sum = (tr[p][u].r - tr[p][u].l + 1) * d;
        tr[p][u].add = d;
        return;
    }

    pushdown(p, u);

    int mid = tr[p][u].l + tr[p][u].r >> 1;

    if (l <= mid) modify(p, u << 1, l, r, d);
    if (r > mid) modify(p, u << 1 | 1, l, r, d);

    pushup(p, u);
}

int query(int p, int u, int l, int r)
{
    if (tr[p][u].l >= l && tr[p][u].r <= r) return tr[p][u].sum;

    pushdown(p, u);

    int mid = tr[p][u].l + tr[p][u].r >> 1;

    int sum = 0;
    if (l <= mid) sum = query(p, u << 1, l, r);
    if (r > mid) sum += query(p, u << 1 | 1, l, r);

    return sum;
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m >> s + 1;

    for (int i = 0; i < 26; i++) build(i, 1, 1, n);

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

        memset(st, 0, sizeof st);

        for (int i = 0; i < 26; i++) st[i] = query(i, 1, l, r);

        int cnt = 0, p = -1;
        for (int i = 0; i < 26; i++)
            if (st[i] & 1) p = i, cnt++;

        if (cnt < 2)
        {
            for (int i = 0; i < 26; i++) modify(i, 1, l, r, 0);

            if (cnt && ~p)
            {
                st[p]--;
                modify(p, 1, l + r >> 1, l + r >> 1, 1);
            }

            int L = l, R = r;
            for (int i = 0; i < 26; i++)
                if (st[i])
                {
                    modify(i, 1, L, L + (st[i] >> 1) - 1, 1);

                    L += st[i] >> 1;

                    modify(i, 1, R - (st[i] >> 1) + 1, R, 1);

                    R -= st[i] >> 1;
                }
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 26; j++)
            if (query(j, 1, i, i)) cout << (char)(j + 'a');


    return 0;
}

20240908

P1471 方差

询问[l,r]

$$S^2=$$

$$\frac{\sum\limits_{l}^r\left(A_i-\overline A\right)^2}{r-l+1}=$$

$$\frac{\sum\limits_{l}^r\left(A_i^2-2*A_i*\overline A +\overline A^2\right)}{r-l+1}=$$

$$\frac{\sum\limits_{l}^rA_i^2-2*\overline{A}*\sum\limits_{l}^rA_i+(r-l+1)*\overline{A}^2}{r-l+1}=$$

$$\frac{\sum A_i^2}{r-l+1}-2*\overline{A}^2+\overline{A}^2=$$

$$\frac{\sum A_i^2}{r-l+1}-\overline{A}^2$$

$query2(1, l, r) / (r - l + 1), b = query1(1, l, r) / (r - l + 1)$

修改 [l,r]=v

1. 区间和的影响 tr[u].v += (r - l + 1) * v, tr[u].lazy += v…

2. 区级平方和的影响;

$\sum\limits_{l}^r A_i^2$

= $\sum\limits_{l}^r (A_i+v)^2$

= $\sum\limits_{l}^r (A_i+2*A_i*v+v^2)^2$

= $\sum\limits_{l}^r A_i^2+2*v*\sum\limits_{l}^r A_i+v^2*(r-l+1)$

$ tr2(u) + 2 * v * tr1(u) + v * v * (r - l + 1) $

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
double w[N];

struct Segment
{
    int l, r;
    double sum1, sum2, lazy;
} tr[N << 2];

void pushup(int u)
{
    tr[u].sum1 = tr[u << 1].sum1 + tr[u << 1 | 1].sum1;
    tr[u].sum2 = tr[u << 1].sum2 + tr[u << 1 | 1].sum2;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    int x = root.r - root.l + 1;
    if (root.lazy)
    {
        left.sum2 += 2 * root.lazy * left.sum1 + (x - x / 2) * root.lazy * root.lazy;
        right.sum2 += 2 * root.lazy * right.sum1 + (x / 2) * root.lazy * root.lazy;

        left.sum1 += (x - x / 2) * root.lazy;
        right.sum1 += (x / 2) * root.lazy;

        left.lazy += root.lazy;
        right.lazy += root.lazy;

        root.lazy = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};

    if (l == r)
    {
        tr[u].sum1 = w[l];
        tr[u].sum2 = w[l] * w[l];
        return;
    }

    int mid = l + r >> 1;

    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

    pushup(u);
}

void modify(int u, int l, int r, double d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum2 += 2 * d * tr[u].sum1 + d * d * (tr[u].r - tr[u].l + 1);
        tr[u].sum1 += (tr[u].r - tr[u].l + 1) * d;
        tr[u].lazy += d;
        return;
    }

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;

    if (l <= mid) modify(u << 1, l, r, d);
    if (r > mid) modify(u << 1 | 1, l, r, d);

    pushup(u);
}

double query1(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum1;

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;

    double res = 0;
    if (l <= mid) res = query1(u << 1, l, r);
    if (r > mid) res += query1(u << 1 | 1, l, r);

    return res;
}

double query2(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum2;

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;

    double res = 0;
    if (l <= mid) res = query2(u << 1, l, r);
    if (r > mid) res += query2(u << 1 | 1, l, r);

    return res;
}

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> w[i];

    build(1, 1, n);

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

        if (op == 1)
        {
            cin >> d;

            modify(1, l, r, d);
        }
        else if (op == 2)
            cout << fixed << setprecision(4) << query1(1, l, r) / (r - l + 1) << '\n';
        else
        {
            double a = query2(1, l, r) / (r - l + 1), b = query1(1, l, r) / (r - l + 1);

            cout << fixed << setprecision(4) << a - b * b << '\n';
        }
    }


    return 0;
}

P2894 [USACO08FEB] Hotel G

新技能:三段拼接

题目本质:

1. 长度为n的0串, m次操作;

2. 操作1 x, 寻找不小于x的最小的0串

解法:

1. 操作2理解为区级修改, 打懒标记, 0表示 没有标记, 1表示住人, 2表示退房;

2. 操作1需要维护三个信息, lx, rx, ans;

3. 弱当前区级的ans满足条件, 优先去左子树, 再去拼接, 最后去右子树

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;

struct Segment
{
    int l, r;
    int lx, rx, v;
    int lazy;
} tr[N << 2];

void pushup(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    root.lx = left.lx;

    if (left.v == left.r - left.l + 1) root.lx = left.v + right.lx;

    root.rx = right.rx;
    if (right.v == right.r - right.l + 1) root.rx = right.v + left.rx;

    root.v = max({left.v, right.v, left.rx + right.lx});
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    if (root.l == root.r) return;

    if (!root.lazy)
    {
        left.v = 0;
        left.lazy = 0;

        right.v = 0;
        right.lazy = 0;

        left.lx = left.rx = 0;
        right.lx = right.rx = 0;

        root.lazy = 2;
    }
    else if (root.lazy == 1)
    {
        left.v = left.r - left.l + 1;
        left.lazy = 1;

        right.v = right.r - right.l + 1;
        right.lazy = 1;

        left.lx = left.rx = left.v;
        right.lx = right.rx = right.v;

        root.lazy = 2;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    tr[u].lazy = 2;

    if (l == r)
    {
        tr[u].lx = tr[u].rx = tr[u].v = r - l + 1;
        return; 
    }

    int mid = l + r >> 1;

    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

    pushup(u);
} 

void modify(int u, int l, int r, int d)
{
    if (tr[u].r < l || tr[u].l > r) return;

    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].lazy = d;

        if (d == 1) tr[u].v = tr[u].r - tr[u].l + 1;
        else tr[u].v = 0;

        tr[u].lx = tr[u].rx = tr[u].v;

        return;
    }

    pushdown(u);

    modify(u << 1, l, r, d);
    modify(u << 1 | 1, l, r, d);

    pushup(u);
}

int query(int u, int d)
{
    if (tr[u].l == tr[u].r) return tr[u].l;

    pushdown(u);

    if (tr[u << 1].v >= d) return query(u << 1, d);
    if (tr[u << 1].rx + tr[u << 1 | 1].lx >= d) return tr[u << 1].r - tr[u << 1].rx + 1;
    if (tr[u << 1 | 1].v >= d) return query(u << 1 | 1, d);
}

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

    int n, m;
    cin >> n >> m;

    build(1, 1, n);

    int op, x, d;
    while (m--)
    {
        cin >> op >> x;

        if (op == 1)
        {
            if (tr[1].v < x) cout << "0\n";
            else
            {
                int now = query(1, x);

                modify(1, now, now + x - 1, 0);

                cout << now << '\n';
            }
        }
        else
        {
            cin >> d;

            modify(1, x, x + d - 1, 1);
        }
    }


    return 0;
}

CF620E New Year Tree

1. 对于2操作, 由于c不超过60, 考虑状态压缩, 每种颜色对应一个数位, 0和1表示颜色没有出现和出现;

2. 对于1操作, 将子树的赋值转换为区间的赋值, 利用子树的 $dfs$ 序是连续的;

3. 按位或1即可将二进制转化为区级赋值为1

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 4e5 + 10, M = 8e5 + 10;
ll h[N], e[M], ne[M], idx;
ll c[N], s[N];
ll dfn[N], timestamp;
ll st[N];

struct Segment
{
    ll l, r;
    ll v, lazy;
} tr[N << 2];

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

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

void pushdown(ll u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    if (root.lazy)
    {
        left.lazy = root.lazy;
        left.v = 1ll << root.lazy;  

        right.lazy = root.lazy;
        right.v = 1ll << root.lazy;

        root.lazy = 0;
    }
}

void build(ll u, ll l, ll r)
{
    tr[u] = {l, r};

    if (l == r)
    {
        tr[u].v = 1ll << c[st[l]];
        return;
    }

    ll mid = l + r >> 1;

    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

    pushup(u);
}

ll query(ll u, ll l, ll r)
{
    if (tr[u].r < l || tr[u].l > r) return 0;

    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    pushdown(u);

    return query(u << 1, l, r) | query(u << 1 | 1, l, r);
}

void modify(ll u, ll l, ll r, ll d)
{
    if (tr[u].r < l || tr[u].l > r) return;

    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].lazy = d;
        tr[u].v = 1ll << d;
        return;
    }

    pushdown(u);

    modify(u << 1, l, r, d);
    modify(u << 1 | 1, l, r, d);

    pushup(u);
}

void dfs(ll u, ll p)
{
    s[u] = 1;
    dfn[u] = ++timestamp;

    st[timestamp] = u;

    for (ll i = h[u]; ~i; i = ne[i])
    {
        ll j = e[i];

        if (j != p)
        {
            dfs(j, u);

            s[u] += s[j];
        }
    }
}

ll lowbit(ll x)
{
    return x & -x;
}

ll get(ll x)
{
    ll cnt = 0;
    while (x)
    {
        cnt++;
        x -= lowbit(x);
    }

    return cnt;
}

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

    ll n, m;
    cin >> n >> m;

    for (ll i = 1; i <= n; i++) cin >> c[i];

    memset(h, -1, sizeof h);

    ll a, b;
    for (ll i = 1; i < n; i++)
    {
        cin >> a >> b;

        add(a, b);
        add(b, a);
    }

    dfs(1, 0);
    build(1, 1, n);

    ll op, x, y;
    while (m--)
    {
        cin >> op >> x;

        if (op == 1)
        {
            cin >> y;

            modify(1, dfn[x], dfn[x] + s[x] - 1, y);
        }
        else
            cout << get(query(1, dfn[x], dfn[x] + s[x] - 1)) << '\n';
    }


    return 0;
}