3.23 总结

T1 Vacation Query

题目的查询要求一段区间内最长连续 1 的个数，对于最长连续……的问题，我们可以使用线段树维护并分三类情况进行区间合并：

左区间或者右区间的最长连续 1 个数的最大值
横跨左右两区间的最长连续 1 的个数，也就是左区间的以区间右端点为右端点的最长连续 1 个数与右区间的以区间左端点为左端点的最长连续 1 个数之和。

那么至此，我们就需要维护三个信息：

区间的最长连续 1 个数
以区间左端点为左端点的最长连续 1 个数。
以区间右端点为右端点的最长连续 1 个数。

再看修改操作，需要将区间取反，那么原先最长连续 1 个数就变成了最长连续 0 个数，所以我们需要再维护三个信息：

区间的最长连续 0 个数
以区间左端点为左端点的最长连续 0 个数。
以区间右端点为右端点的最长连续 0 个数。

至此这道题就做完了。

struct dat
{
    int l, r, s, z, ls, rs, lz, rz;
};
struct tag
{
    int cnt;
    tag(int _cnt = 0) {cnt = _cnt;}
    bool operator==(const tag& other) const
    {
        return cnt == other.cnt;
    }
};
dat f(const tag &t, const dat &d)
{
    dat res = d;
    if (t.cnt & 1)
    {
        swap(res.s, res.z);
        swap(res.ls, res.lz);
        swap(res.rs, res.rz);
    }
    return res;
}
tag g(const tag &x, const tag &y)
{
    return tag{x.cnt ^ y.cnt};
}
dat h(const dat &a, const dat &b)
{
    dat res;
    res.l = a.l;
    res.r = b.r;
    res.s = max({a.s, b.s, a.rs + b.ls});
    res.z = max({a.z, b.z, a.rz + b.lz});
    // :NOTE: 这里的 ls 在左区间全是 1 的情况下加上右区间的 ls。
    res.ls = a.ls + (a.ls == a.r - a.l + 1) * b.ls;
    res.rs = b.rs + (b.rs == b.r - b.l + 1) * a.rs;
    res.lz = a.lz + (a.lz == a.r - a.l + 1) * b.lz;
    res.rz = b.rz + (b.rz == b.r - b.l + 1) * a.rz;
    return res;
}
const tag tt;
const dat dd;

int main()
{
    st.init(1, 1, n);
    while (q--)
    {
        if (c == 1)
            st.upd(1, l, r, {1});
        else
            printf("%d\n", st.qry(1, l, r).s);
    }
    return 0;
}

T2 XOR on Segment

区间二进制操作和非二进制操作混合，考虑将数二进制拆分，此时我们的操作就变成了这样：

操作一，把每个数的每一位加起来（比如 $3+7=(2+1)+(4+2+1)=4+2\times 2+2\times 1$）
操作二直接将和的每一位分别异或即可。

const int M = 22;
struct dat
{
    int l, r, c[M];
    dat(int _l = 0, int _r = 0, ll _v = 0)
    {
        l = _l, r = _r;
        for (int i = 0; i < M; ++i)
            c[i] = (_v >> 1) & 1;
    }
    ll get()
    {
        ll res = 0;
        for (int i = 0; i < M; ++i)
            res += (1ll << i) * c[i];
        return res;
    }
};
struct tag
{
    ll x;
    tag(ll _x = 0)
    {
        x = _x;
    }
    bool operator==(const tag &other)
    {
        return x == other.x;
    }
};
const tag tt;
const dat dd;
dat f(const tag &t, const dat &d)
{
    dat res;
    res.l = d.l;
    res.r = d.r;
    for (int i = 0; i < M; ++i)
        res.c[i] = (((t.x >> i) & 1) ? d.r - d.l + 1 - d.c[i] : d.c[i]);
    return res;
}
tag g(const tag &x, const tag &y)
{
    return tag{x.x ^ y.x};
}
dat h(const dat &a, const dat &b)
{
    dat res;
    res.l = a.l;
    res.r = b.r;
    for (int i = 0; i < M; ++i)
        res.c[i] = a.c[i] + b.c[i];
    return res;
}

int main()
{
    st.init(1, 1, n);
    while (q--)
        if (op & 1)
            cout << st.qry(1, l, r).get() << "\n";
        else
            st.upd(1, l, r, {k});
    return 0;
}

T3 A Simple Task

由于是对字母排序，数字的范围很小（只有 26 ），考虑采取桶排序的思想，每一次查询先将区间的桶取出来，然后把区间推平重新填充即可。

struct dat
{
    int l, r;
    ll cnt[M];
    dat() { l = 0, r = 0; memset(cnt, 0, sizeof cnt); }
};
struct tag
{
    int x;
    tag(int _x = -1)
    {
        x = _x;
    }
    bool operator==(const tag &other)
    {
        return x == other.x;
    }
};
const tag tt;
const dat dd;
dat f(const tag &t, const dat &d)
{
    if (!~t.x)
        return d;
    dat tmp = d;
    memset(tmp.cnt, 0, sizeof tmp.cnt);
    tmp.cnt[t.x] = tmp.r - tmp.l + 1;
    return tmp;
}
dat h(const dat &a, const dat &b)
{
    dat tmp;
    tmp.l = a.l;
    tmp.r = b.r;
    for (int i = 0; i < M; ++i)
        tmp.cnt[i] = a.cnt[i] + b.cnt[i];
    return tmp;
}
int main()
{
    st.init(1, 1, n);
    while (q--)
    {
        int i, j, k;
        std::cin >> i >> j >> k;
        dat stmp = st.qry(1, i, j);
        for (int x = 0; x < M; ++x)
        {
            int xx = k ? x : M - 1 - x, cnt = stmp.cnt[xx];
            if (!cnt)
                continue;
            st.upd(1, i, i + cnt - 1, xx);
            i += cnt;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        dat stmp = st.qry(1, i, i);
        for (char _ = 'z'; _ >= 'a'; --_)
            if (stmp.cnt[_ - 'a'])
                std::cout << _;
    }
}