526互联

Limit线段树题单题解（更新中）

发布时间 2023-08-03 01:55:14作者: Zeoy_kkk

P3373 线段树模板 2

image-20230803010844370

\(1 \leq n \leq 10^5\)

题解：考查标记与标记的合并

  • 我们考虑打两个懒惰标记实现区间乘和区间加
  • 线段树维护区间和
  • 对于信息与信息的合并：左儿子加上右儿子即可
  • 对于标记与标记的合并：
  • 我们发现如果某个区间存在加法的\(lazy\)，但是现在对该区间又打上乘法的\(lazy\)，如果我们不更新加法的\(lazy\)，那么下放加法\(lazy\)的时候会出现错误
  • 所以我们在打乘法\(lazy\)的时候也要将加法的\(lazy\)乘上相应的标记值，这是两个不同的标记之间的合并
  • 对于相同标记之间，直接合并即可
  • 对于信息和标记的合并，简单合并即可
  • 标记下放时我们注意，因为加法的\(lazy\)有可能被更新过了，所以我们应该先下放乘法标记并更新区间信息，再下放加法标记并更新区间信息即可
const int N = 1e5 + 10, M = 4e5 + 10;

int n, q, m;
int a[N];
struct info
{
    int sum;
};
struct SEG
{
    int mul_lazy, add_lazy;
    int len;
    info val;
    SEG()
    {
        mul_lazy = 1;
        add_lazy = 0;
    }
} seg[N << 2];
info operator+(const info &a, const info &b)
{
    info c;
    c.sum = (a.sum + b.sum) % m;
    return c;
}

void settag_mul(int id, int tag)
{
    seg[id].val.sum = seg[id].val.sum * tag % m;
    seg[id].mul_lazy = seg[id].mul_lazy * tag % m;
    seg[id].add_lazy = seg[id].add_lazy * tag % m;
}

void settag_add(int id, int tag)
{
    seg[id].val.sum = (seg[id].val.sum + seg[id].len * tag % m) % m;
    seg[id].add_lazy = (seg[id].add_lazy + tag) % m;
}

void up(int id)
{
    seg[id].val = seg[lson].val + seg[rson].val;
}

void down(int id)
{
    if (seg[id].mul_lazy != 1)
    {
        settag_mul(lson, seg[id].mul_lazy);
        settag_mul(rson, seg[id].mul_lazy);
    }
    if (seg[id].add_lazy != 0)
    {
        settag_add(lson, seg[id].add_lazy);
        settag_add(rson, seg[id].add_lazy);
    }
    seg[id].add_lazy = 0, seg[id].mul_lazy = 1;
}

void build(int id, int l, int r)
{
    seg[id].len = r - l + 1;
    if (l == r)
    {
        seg[id].val.sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    up(id);
}

void modify(int id, int l, int r, int ql, int qr, int op, int val)
{
    if (ql <= l && r <= qr)
    {
        if (op == 1)
            settag_mul(id, val);
        else
            settag_add(id, val);
        return;
    }
    down(id);
    int mid = l + r >> 1;
    if (qr <= mid)
        modify(lson, l, mid, ql, qr, op, val);
    else if (ql > mid)
        modify(rson, mid + 1, r, ql, qr, op, val);
    else
    {
        modify(lson, l, mid, ql, qr, op, val);
        modify(rson, mid + 1, r, ql, qr, op, val);
    }
    up(id);
}

info query(int id, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
    {
        return seg[id].val;
    }
    down(id);
    int mid = l + r >> 1;
    if (qr <= mid)
        return query(lson, l, mid, ql, qr);
    else if (ql > mid)
        return query(rson, mid + 1, r, ql, qr);
    else
        return query(lson, l, mid, ql, qr) + query(rson, mid + 1, r, ql, qr);
}

void solve()
{
    cin >> n >> q >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1)
        {
            cin >> x;
            modify(1, 1, n, l, r, 1, x);
        }
        else if (op == 2)
        {
            cin >> x;
            modify(1, 1, n, l, r, 2, x);
        }
        else
        {
            cout << query(1, 1, n, l, r).sum % m << endl;
        }
    }
}

P1276 校门外的树（增强版）

image-20230803012200912

\(1 \leq L \leq 10^4\)

题解：两颗线段树

  • 由于懒惰标记较为麻烦，我们考虑建两颗线段树
  • 一颗维护树和树苗存在的数量，另一颗维护树存在的数量
  • 那么对于答案我们可以通过简单容斥获得
  • 最后留下的树苗 = 最后留下的树和树苗的数量 - 最后留下的树的数量
  • 每次被砍掉的树苗 = 每次砍掉的树和树苗的数量 - 每次砍掉的树的数量，统计每次数量即可
  • 我们考虑线段树如何维护数量
  • 线段树维护区间和
  • 一开始所有叶子节点全为\(1\)
  • 每次砍树，我们将对应的区间的区间和赋值为\(0\)，并利用懒惰标记更新下面的区间
  • 每次种树，我们将对应的区间的区间和赋值为区间长度，并利用懒惰标记更新下面的区间
const int N = 1e4 + 10, M = 4e5 + 10;

int n, q;
struct SEG_TREE
{
    struct info
    {
        int sum;
        // 信息与信息的合并
        friend info operator+(const info &a, const info &b)
        {
            info c;
            c.sum = a.sum + b.sum;
            return c;
        }
    };
    struct SEG
    {
        int lazy, len;
        info val;
    } seg[N << 2];
    void settag(int id, int tag)
    {
        // 信息与标记的合并
        if (tag == -1) // 砍树，区间赋0
            seg[id].val.sum = 0;
        else if (tag == 1) // 种树， 区间赋1
            seg[id].val.sum = seg[id].len;
        // 标记与标记的合并
        seg[id].lazy = tag;
    }
    void up(int id)
    {
        seg[id].val = seg[lson].val + seg[rson].val;
    }
    void down(int id)
    {
        if (seg[id].lazy == 0)
            return;
        // 下放标记
        settag(lson, seg[id].lazy);
        settag(rson, seg[id].lazy);
        // 清空标记
        seg[id].lazy = 0;
    }
    void build(int id, int l, int r)
    {
        seg[id].len = r - l + 1;
        if (l == r)
        {
            seg[id].val.sum = 1;
            return;
        }
        int mid = l + r >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        up(id);
    }
    void modify(int id, int l, int r, int ql, int qr, int val)
    {
        if (ql <= l && r <= qr)
        {
            settag(id, val);
            return;
        }
        down(id);
        int mid = l + r >> 1;
        if (qr <= mid)
            modify(lson, l, mid, ql, qr, val);
        else if (ql > mid)
            modify(rson, mid + 1, r, ql, qr, val);
        else
        {
            modify(lson, l, mid, ql, qr, val);
            modify(rson, mid + 1, r, ql, qr, val);
        }
        up(id);
    }
    info query(int id, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr)
        {
            return seg[id].val;
        }
        down(id);
        int mid = l + r >> 1;
        if (qr <= mid)
            return query(lson, l, mid, ql, qr);
        else if (ql > mid)
            return query(rson, mid + 1, r, ql, qr);
        else
            return query(lson, l, mid, ql, qr) + query(rson, mid + 1, r, ql, qr);
    }
} tr1, tr2;

void solve()
{
    cin >> n >> q;
    ++n;
    tr1.build(1, 1, n), tr2.build(1, 1, n);
    int ans = 0;
    while (q--)
    {
        int op, l, r;
        cin >> op >> l >> r;
        ++l, ++r;
        if (op == 0)
        {
            // 被砍掉的树苗和树的总数， 被砍掉的树的总数
            int sum1 = tr1.query(1, 1, n, 1, n).sum, sum2 = tr2.query(1, 1, n, 1, n).sum;
            tr1.modify(1, 1, n, l, r, -1);
            tr2.modify(1, 1, n, l, r, -1);
            sum1 -= tr1.query(1, 1, n, 1, n).sum;
            sum2 -= tr2.query(1, 1, n, 1, n).sum;
            ans += sum1 - sum2;
        }
        else
        {
            tr1.modify(1, 1, n, l, r, 1);
        }
    }
    cout << tr1.query(1, 1, n, 1, n).sum - tr2.query(1, 1, n, 1, n).sum << endl;
    cout << ans << endl;
}

P5057 [CQOI2006] 简单题

image-20230803012935958

\(1 \leq n \leq 10^5\)

题解：只有标记的线段树

  • 线段树不需要维护任何信息，只需要利用标记来完成数字反转
  • 对于\(lazy\)来说，\(1\)代表该区间需要反转，\(0\)代表不需要反转
  • 因为只有标记，所以我们只需要关注标记与标记的合并：
  • 如果某个区间上存在标记，说明该区间需要反转，如果我们再对该区间打上标记的话，该区间不反转，所以标记的合并实际上就是异或
  • 对于单点查询来说，如果该区间的\(lazy = 1\)，直接输出\(1\)即可，否则输出\(0\)
const int N = 1e5 + 10, M = 4e5 + 10;

int n, q;
struct SEG
{
    int lazy;
} seg[N << 2];

void settag(int id, int tag)
{
    seg[id].lazy ^= tag;
}

void down(int id)
{
    if (seg[id].lazy == 0)
        return;
    int tag = seg[id].lazy;
    settag(lson, tag);
    settag(rson, tag);
    seg[id].lazy = 0;
}

void modify(int id, int l, int r, int ql, int qr, int tag)
{
    if (ql <= l && r <= qr)
    {
        settag(id, tag);
        return;
    }
    down(id);
    int mid = l + r >> 1;
    if (qr <= mid)
        modify(lson, l, mid, ql, qr, tag);
    else if (ql > mid)
        modify(rson, mid + 1, r, ql, qr, tag);
    else
    {
        modify(lson, l, mid, ql, qr, tag);
        modify(rson, mid + 1, r, ql, qr, tag);
    }
}

int query(int id, int l, int r, int x)
{
    if (l == r)
        return seg[id].lazy;
    down(id);
    int mid = l + r >> 1;
    if (x <= mid)
        return query(lson, l, mid, x);
    else
        return query(rson, mid + 1, r, x);
}

void solve()
{
    cin >> n >> q;
    while (q--)
    {
        int op, l, r, x;
        cin >> op;
        if (op == 1)
        {
            cin >> l >> r;
            modify(1, 1, n, l, r, 1);
        }
        else
        {
            cin >> x;
            if (query(1, 1, n, x) == 1)
                cout << 1 << endl;
            else
                cout << 0 << endl;
        }
    }
}

P4588 [TJOI2018] 数学计算

image-20230803013819752

\(1 \leq Q \leq 10^5\)

题解：对时间点建线段树

  • 我们考虑对于时间点建线段树
  • 线段树维护区间乘，初始所有区间为\(1\)
  • 对于操作一，我们直接在当前的时间点上修改即可
  • 对于操作二，我们直接在线段树将第\(pos\)次时间点上的修改为\(1\)即可
  • 对于查询来说，我们直接输出\(seg[1]\)即可
const int N = 1e5 + 10, M = 4e5 + 10;

int q, m;
int mp[N];

struct info
{
    int ans;
};
struct SEG
{
    info val;
} seg[N << 2];
info operator+(const info &a, const info &b)
{
    info c;
    c.ans = a.ans * b.ans % m;
    return c;
}

void up(int id)
{
    seg[id].val = seg[lson].val + seg[rson].val;
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        seg[id].val.ans = 1;
        return;
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    up(id);
}

void change(int id, int l, int r, int x, int val)
{
    if (l == r)
    {
        seg[id].val.ans = val;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        change(lson, l, mid, x, val);
    else
        change(rson, mid + 1, r, x, val);
    up(id);
}

void solve()
{
    cin >> q >> m;
    build(1, 1, q);
    for (int i = 1; i <= q; ++i)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
        {
            change(1, 1, q, i, x);
            cout << seg[1].val.ans % m << endl;
        }
        else
        {
            change(1, 1, q, x, 1);
            cout << seg[1].val.ans % m << endl;
        }
    }
}

P1908 逆序对

image-20230803014308569

\(1 \leq n \leq 5\times10^5\)

题解：动态开点

const int N = 5e5 + 10, M = 8e6 + 10;

int n, m;
int a[N];
int rt, lson[M], rson[M], sum[M], idx;

void up(int id)
{
    sum[id] = sum[lson[id]] + sum[rson[id]];
}

void change(int &id, int l, int r, int x, int val)
{
    if (!id)
        id = ++idx;
    if (l == r)
    {
        sum[id] += val;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        change(lson[id], l, mid, x, val);
    else
        change(rson[id], mid + 1, r, x, val);
    up(id);
}

int query(int id, int l, int r, int ql, int qr)
{
    if (!id)
        return 0;
    if (ql <= l && r <= qr)
    {
        return sum[id];
    }
    int mid = l + r >> 1;
    if (qr <= mid)
        return query(lson[id], l, mid, ql, qr);
    else if (ql > mid)
        return query(rson[id], mid + 1, r, ql, qr);
    else
        return query(lson[id], l, mid, ql, qr) + query(rson[id], mid + 1, r, ql, qr);
}

void solve()
{
    m = 1e9 + 10;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans += query(rt, 1, m, a[i] + 1, m);
        change(rt, 1, m, a[i], 1);
    }
    cout << ans << endl;
}