LinhoNotes

外观

假期练习 #2 ​

T2.1 P2824 [HEOI2016/TJOI2016] 排序 ​

哎二分还在追我

解题思路 ​

这道题需要我们进行 m 次排序，但排序是很慢的一种算法，直接排序是肯定会超时的。

那么我们来想想哪种序列是可以比较快速的进行排序的：01 序列。

01 序列可以在 O(log⁡n) 的复杂度内进行排序。方法是：

  • 统计 01 序列中 1 的个数 a，然后直接将序列后 a 个数赋为 1 ，其余位置赋为 0
  • 通过线段树维护可以把复杂度降到 log⁡n

下一步我们要考虑如何把 01 序列应用到这道题上。

首先我们可以注意到，这道题只有一个查询。

假设这次查询的答案为 x，我们可以将序列中大于等于 x 的数变为 1，而小于 x 的数变为 0。这样序列就转化为了一个 01 序列了。

x 的值我们可以枚举获得，但是要枚举获得 n 的话总时间复杂度会变为 O(nmlog⁡n) ，因此还要进行优化。

我们可以发现答案 x 的值是具有单调性的，因此我们是可以二分 x 的值的。

这样复杂度就变为 O(mlog2⁡n) ，符合要求。

AC 代码（使用了半吊子线段树板子） ​

c++
#include <bits/extc++.h>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
template <typename T> using vct = vector<T>;
template <typename T> using v2ct = vector<vector<T>>;
template <typename T> using v3ct = vector<vector<vector<T>>>;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

struct Sgm_tree {

    struct Tag {
        bool status;
        ll val;

        Tag() : status(0) {}
        Tag(ll x) : status(1), val(x) {}

        void apply(const Tag &t) {
            if (status) {
                *this = Tag(t.val);
            } else
                *this = t;
        }
    };

    struct Info {
        ll l, r, sum;
        Info() { l = r = sum = -1; }
        Info(const ll &pos, const ll &x) {
            l = r = pos;
            sum = x;
        }
        friend Info operator+(const Info &lhs, const Info &rhs) {
            Info res = Info();

            res.l = lhs.l;
            res.r = rhs.r;
            res.sum = lhs.sum + rhs.sum;

            return res;
        }
        void apply(const Tag &t) { sum = (r - l + 1) * t.val; }
    };

    ll n;
    vector<Info> info;
    vector<Tag> tag;

    template <typename V>
    Sgm_tree(const V &values)
        : n(values.size() - 1), info(4 * n, Info()), tag(4 * n, Tag()) {
        build_tree(1, 1, n, values);
    }

    template <typename V>
    void build_tree(ll o, ll l, ll r, const V &values) {
        if (l == r) {
            info[o] = Info(l, values[l]);
            return;
        }
        ll mid = (l + r) / 2;
        build_tree(o * 2, l, mid, values);
        build_tree(o * 2 + 1, mid + 1, r, values);
        info[o] = info[o * 2] + info[o * 2 + 1];
    }

    void push_down(ll o) {
        if (tag[o].status) {
            info[o * 2].apply(tag[o]);
            info[o * 2 + 1].apply(tag[o]);
            tag[o * 2].apply(tag[o]);
            tag[o * 2 + 1].apply(tag[o]);

            tag[o] = Tag();
        }
    }

    void modify(ll ql, ll qr, ll val) { modify(1, ql, qr, Tag(val)); }

    void modify(ll o, ll ql, ll qr, const Tag &t) {
        if (ql > qr)
            return;
        Info &cur = info[o];
        ll l = cur.l, r = cur.r;
        if (l >= ql && r <= qr) {
            info[o].apply(t);
            tag[o].apply(t);
            return;
        }
        push_down(o);
        ll mid = (l + r) / 2;
        if (ql <= mid)
            modify(o * 2, ql, qr, t);
        if (qr >= mid + 1)
            modify(o * 2 + 1, ql, qr, t);
        info[o] = info[o * 2] + info[o * 2 + 1];
    }

    ll query(ll ql, ll qr) { return query(1, ql, qr).sum; }

    Info query(ll o, ll ql, ll qr) {
        Info &cur = info[o];
        ll l = cur.l, r = cur.r;
        if (l >= ql && r <= qr) {
            //			OOO cout<<"!!!"<<endl;
            return info[o];
        }
        push_down(o);
        ll mid = (l + r) / 2;
        if (ql <= mid && qr >= mid + 1)
            return query(o * 2, ql, qr) + query(o * 2 + 1, ql, qr);
        if (ql <= mid)
            return query(o * 2, ql, qr);
        if (qr >= mid + 1)
            return query(o * 2 + 1, ql, qr);
    }
};

void solve() {
    ll n, m, q;
    cin >> n >> m;
    vector<ll> v(n + 1), op(m + 1), l(m + 1), r(m + 1);
    for (ll i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (ll i = 1; i <= m; i++) {
        cin >> op[i] >> l[i] >> r[i];
        if (l[i] > r[i])
            swap(l[i], r[i]);
        //		cout<<"!!!"<<endl;
    }

    cin >> q;

    auto check = [&](ll x) -> bool {
        vector<ll> tmp(n + 1);
        for (ll i = 1; i <= n; i++) {
            if (v[i] >= x)
                tmp[i] = 1;
        }
        Sgm_tree sgt(tmp);
        for (ll i = 1; i <= m; i++) {
            //			OOO OOO cout<<i<<endl;
            //			for(ll i=1;i<=n;i++) cout<<sgt.query(i,i)<<'
            //'; 			cout<<endl;
            if (op[i] == 0) {
                ll sum1 = sgt.query(l[i], r[i]);
                sgt.modify(r[i] - sum1 + 1, r[i], 1);
                sgt.modify(l[i], r[i] - sum1, 0);
            } else {
                ll sum1 = sgt.query(l[i], r[i]);
                sgt.modify(l[i], l[i] + sum1 - 1, 1);
                sgt.modify(l[i] + sum1, r[i], 0);
            }
        }
        return sgt.query(q, q);
    };

    ll L = 1, R = n;
    while (L < R) {
        ll mid = (L + R + 1) / 2;
        //		cout<<mid<<' '<<check(mid)<<endl;
        if (check(mid)) {
            L = mid;
        } else {
            R = mid - 1;
        }
    }
    //	OOO
    cout << L << endl;
}

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

    //	cin >> tt;	//非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}

T2.2 D - Median Pyramid Hard ​

中位数的中位数的中位数的中位数的......

解法思路 ​

有了上面那道题的启发，这道题就很容易想到采取同样的策略：

  • 将原数列二值化，然后二分答案

现在的问题是，对于这个问题，我们怎么进行高效的 check？

  • 一个显而易见的结论是，上一层的数值等于下一层三数的中位数，在二值化后也就是众数
  • 所以可以观察到一个规律，只要有两个 “最靠近中间位置的相同的位”，他们的数字就会一直向上传递知道决定顶部的数字（自己手玩一下就知道为什么了）
  • 那么我们就已经找到了一个高效的 check 方案了

开销 O(nlog⁡n) ，优秀

AC 代码 ​

c++
#include <bits/extc++.h>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
template <typename T> using vct = vector<T>;
template <typename T> using v2ct = vector<vector<T>>;
template <typename T> using v3ct = vector<vector<vector<T>>>;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

void solve() {
    ll n;
    cin >> n;
    vector<ll> v(2 * n, 0);
    for (ll i = 1; i <= n * 2 - 1; i++)
        cin >> v[i];

    function<bool(ll)> check = [&](ll x) -> bool {
        vector<ll> tmp(2 * n, 0);
        //		cout<<x<<"  :  ";
        for (ll i = 1; i <= 2 * n - 1; i++)
            tmp[i] = (v[i] >= x) /*,cout<<tmp[i]*/;
        //		cout<<endl;
        for (ll i = 1; i < n; i++) {
            if (tmp[n + i] == tmp[n + i - 1])
                return tmp[n + i];
            if (tmp[n - i] == tmp[n - i + 1])
                return tmp[n - i];
        }
        return (tmp[n] + n - 1) % 2;
    };

    ll l = 1, r = 2 * n - 1;
    while (r > l) {
        ll mid = (l + r + 1) / 2;
        ll flag = check(mid);
        //		OOO cout<<mid<<' '<<flag<<endl;
        if (flag)
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << endl;
}

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

    //	cin >> tt;	//非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}

T2.3 E. A Simple Task ​

解法显而易见

AC 代码（使用了炸带鱼的线段树板子 半完全体 ver.） ​

c++
#include <bits/extc++.h>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
template <typename T> using vct = vector<T>;
template <typename T> using v2ct = vector<vector<T>>;
template <typename T> using v3ct = vector<vector<vector<T>>>;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

template <typename T> class Segment_tree {
  public:
    class Tag { // 修改标记类
      public:
        bool status;
        // $$$ 要维护的标记内容，按需添加
        ll key;

        Tag() : status(false) {} // 无效 tag 初始化

        Tag(const T &t)
            : status(true), key(t) {} // $$$ 有效 tag 初始化，按需具体实现

        void apply(const Tag &t) { // 将 tag 下放应用到 当前tag 上的操作
            if (!t.status)
                return;
            if (status) { // $$$ 当前 tag 非空时的应用，按需具体实现
                key = t.key;
            } else // 当前 tag 为空
                *this = t;
        }
    };

    class Info { // 节点信息类
      public:
        ll l, r; // 左右端点
        // $$$ 要维护的具体信息，按需添加
        ll sum;

        Info()
            : l(0), r(0) {
        } // 无效 Info 初始化，默认将子节点引导向 0 节点，也就是无效节点

        Info(const ll &pos, const T &val)
            : l(pos), r(pos),
              sum(val) { // 有效 Info 初始化，在 pos 处的数值为 val 的节点
            // $$$ 具体数据初始化实现
        }

        friend Info
        operator+(const Info &lhs,
                  const Info &rhs) { // 重载加法运算符 实现节点信息的合并
            Info res = Info();
            res.l = lhs.l;
            res.r = rhs.r;
            // $$$ 具体合并时的数据维护操作 按需具体实现
            res.sum = lhs.sum + rhs.sum;
            return res;
        }

        void apply(const Tag &t) { // 将 tag 应用到当前节点上
            if (!t.status)
                return;
            // $$$ tag 有效时的具体应用操作 按需具体实现
            sum = t.key * (r - l + 1);
        }
    };

    // 用 vals 构造线段树 vals 是支持下标访问的容器对象, 例如
    // std::vector<T>.
    template <typename V>
    Segment_tree(const V &vals)
        : n(vals.size() - 1), info(4 * n + 1, Info()),
          tag(4 * n + 1, Tag()) {
        build_tree(1, 1, n, vals);
    }

    void modify(ll ql, ll qr, const Tag &_key) {
        if (ql < 1 || qr > n || ql > qr) {
            return;
            //			cout<<"Error form Segment_tree :: modify() ->
            //Range_Error "<<ql<<' '<<qr<<endl;
        }
        if (!_key.status)
            return;
        modify(1, ql, qr, _key);
    }

    Info query(ll ql, ll qr) {
        if (ql < 1 || qr > n || ql > qr) {
            cout << "Error form Segment_tree :: query() -> Range_Error "
                 << endl;
        }
        return query(1, ql, qr);
    }

  private:
    ll n;
    vector<Tag> tag;
    vector<Info> info;

    template <typename V>
    void build_tree(ll o, ll l, ll r, const V &vals) {
        if (l == r) {
            info[o] = Info(l, vals[l]);
            //			OOO cout<<l<<' '<<vals[l]<<endl;
            return;
        }
        ll mid = (l + r) / 2;
        build_tree(o * 2, l, mid, vals);
        build_tree(o * 2 + 1, mid + 1, r, vals);
        info[o] = info[o * 2] + info[o * 2 + 1];
    }

    void push_down(ll o) {
        info[o * 2].apply(tag[o]);
        info[o * 2 + 1].apply(tag[o]);
        tag[o * 2].apply(tag[o]);
        tag[o * 2 + 1].apply(tag[o]);
        tag[o] = Tag();
    }

    void modify(ll o, ll ql, ll qr, const Tag &_key) {
        Info &cur = info[o];
        ll l = cur.l, r = cur.r;
        if (l >= ql && r <= qr) {
            cur.apply(_key);
            tag[o].apply(_key);
            return;
        }

        push_down(o);

        ll mid = (l + r) / 2;
        if (ql <= mid)
            modify(o * 2, ql, qr, _key);
        if (qr >= mid + 1)
            modify(o * 2 + 1, ql, qr, _key);

        cur = info[o * 2] + info[o * 2 + 1];
    }

    Info query(ll o, ll ql, ll qr) {
        Info &cur = info[o];
        ll l = cur.l, r = cur.r;
        if (l >= ql && r <= qr) {
            return cur;
        }

        push_down(o);

        ll mid = (l + r) / 2;
        if (ql <= mid && qr >= mid + 1)
            return query(o * 2, ql, qr) + query(o * 2 + 1, ql, qr);
        else if (ql <= mid)
            return query(o * 2, ql, qr);
        else if (qr >= mid + 1)
            return query(o * 2 + 1, ql, qr);
    }
};

void solve() {
    ll n, q;
    cin >> n >> q;
    string s;
    vector<ll> v(n + 1), ls(q + 1), rs(q + 1), op(q + 1);
    cin >> s;
    for (ll i = 1; i <= n; i++)
        v[i] = s[i - 1] - 'a';
    for (ll i = 1; i <= q; i++)
        cin >> ls[i] >> rs[i] >> op[i];

    vector<ll> ans(n + 1);
    for (ll k = 0; k < 26; k++) {
        vector<ll> ch(n + 1);
        for (ll i = 1; i <= n; i++)
            if (v[i] >= k)
                ch[i] = 1;

        //		cout<<k<<endl;

        Segment_tree<ll> tmp(ch);

        for (ll i = 1; i <= q; i++) {
            ll cnt = tmp.query(ls[i], rs[i]).sum;

            //			cout<<ls[i]<<' '<<rs[i]<<' '<<cnt<<endl;
            //			for(ll i=1;i<=n;i++) cout<<tmp.query(i,i).sum<<'
            //'; 			cout<<endl;
            if (op[i] == 0) {
                tmp.modify(ls[i], ls[i] + cnt - 1, 1ll);
                tmp.modify(ls[i] + cnt, rs[i], 0ll);
            } else {
                tmp.modify(rs[i] - cnt + 1, rs[i], 1ll);
                tmp.modify(ls[i], rs[i] - cnt, 0ll);
            }
        }
        //		for(ll i=1;i<=n;i++) cout<<tmp.query(i,i).sum<<' ';
        //		cout<<endl;

        for (ll i = 1; i <= n; i++)
            if (tmp.query(i, i).sum)
                ans[i] = k;
    }

    for (ll i = 1; i <= n; i++)
        cout << (char)(ans[i] + 'a');
    cout << endl;
}

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

    //	cin >> tt;	//非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}