首页 > 其他分享 >P5350 序列 题解

P5350 序列 题解

时间：2024-02-13 20:55:41浏览次数：39  
标签：template int 题解 void st P5350 序列 include define

题目链接：P5350 序列

比较不难的可持久化文艺平衡树？

有道弱化版：数组操作

不过弱化版没有随机数据，很显然 ODT 会直接被卡，这题数据随机倒是能用 ODT 做一下，而且码量也比较小，可以自己写写，或者参照我给的弱化版我给了这题部分操作的 ODT 写法。我们还是来讲最实用的可持久化文艺平衡树的做法。在做这题之前，确保你已经会常见的一些基本高级数据结构，手写平衡树，可持久化平衡树，线段树的常见 lazy 标记使用，文艺平衡树，可持久化的文艺平衡树。

在你拥有前置知识点的情况下，对于增加、覆盖、翻转，这三个属于基本操作，可以直接通过打 lazy 标记保证复杂度，不再细谈。关于交换操作，我们保证 \([l_1,,r_1]\) 在 \([l_2,r_2]\) 的右侧以后，就可以常规操作拆段拼段：\([1,l_1-1]+[l_2,r_2]+[r_1+1,l_2-1]+[l_1,r_1]+[r_2+1,n]=[1,n]=root\)。拆很简单，先拆 \([1,r_2]\) 这一组，再由 \([1,l_2-1]\) 作为根拆剩下的。

关于复制操作，这个是很经典的需要可持久化的操作，我们分出两个区间以后，拼的时候用复制的区间拼，这个时候其实是 \([l_1,r_1]\) 和 \([l_2,r_2]\) 共用了 \([l_1,r_1]\) 这个区间节点，后续对 \([l_2,r_2]\) 上进行修改，也会影响到 \([l_1,r_1]\) 上的操作，所以这里需要可持久化复制版本，保证各种操作互不干扰。

然后就结束了，如何优雅书写这题，我们尽量的以封装各类操作，直观地分类各类操作进行书写。最后还是老生常谈的问题，空间给的很小，那就利用经典的平衡树重构思想---替罪羊树思想，进行重构。重构老规矩，中序遍历拿文艺平衡树的节点值即为最终序列，然后使用笛卡尔树单调栈建树法建树即可，一般 \(节点数目 >10 \times n\) 进行重构。

参照代码 
#include <bits/stdc++.h>

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (typeid(x) == typeid(char))return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 3e5 + 10;
constexpr int MOD = 1e9 + 7;
int root;

struct FHQ
{
    int child[2];
    int add, sum;
    int val, cov;
    int siz;
    int rnk;
    bool rev;
    FHQ() = default;

    explicit FHQ(const int value)
    {
        add = child[0] = child[1] = 0;
        cov = -1;
        rnk = Rand(1, MOD);
        val = sum = value;
        siz = 1, rev = false;
    }
} node[N << 5];

#define left(x) node[x].child[0]
#define right(x) node[x].child[1]
#define rnk(x) node[x].rnk
#define add(x) node[x].add
#define cov(x) node[x].cov
#define val(x) node[x].val
#define siz(x) node[x].siz
#define sum(x) node[x].sum
#define rev(x) node[x].rev
int cnt;

struct
{
    static void Cover(const int curr, const ll val)
    {
        val(curr) = val;
        sum(curr) = val * siz(curr) % MOD;
        add(curr) = 0;
        cov(curr) = val;
    }

    static void Add(const int curr, const ll val)
    {
        val(curr) = (val(curr) + val) % MOD;
        sum(curr) = (sum(curr) + val * siz(curr)) % MOD;
        add(curr) = (add(curr) + val) % MOD;
    }
} Tag;

inline int copy(const int curr)
{
    node[++cnt] = node[curr];
    return cnt;
}

inline void push_up(const int curr)
{
    siz(curr) = siz(left(curr)) + siz(right(curr)) + 1;
    sum(curr) = (1LL * sum(left(curr)) + sum(right(curr)) + val(curr)) % MOD;
}

inline void push_down(const int curr)
{
    if (!add(curr) and cov(curr) == -1 and !rev(curr))return;
    if (left(curr))
        left(curr) = copy(left(curr));
    if (right(curr))
        right(curr) = copy(right(curr));
    if (cov(curr) != -1)
    {
        Tag.Cover(left(curr),cov(curr));
        Tag.Cover(right(curr),cov(curr));
        cov(curr) = -1;
    }
    if (add(curr))
    {
        Tag.Add(left(curr),add(curr));
        Tag.Add(right(curr),add(curr));
        add(curr) = 0;
    }
    if (rev(curr))
    {
        swap(left(curr),right(curr));
        rev(left(curr)) = !rev(left(curr));
        rev(right(curr)) = !rev(right(curr));
        rev(curr) = false;
    }
}

inline void split(const int curr, const int k, int& x, int& y)
{
    if (!curr)
    {
        x = y = 0;
        return;
    }
    push_down(curr);
    if (siz(left(curr)) < k)
    {
        x = copy(curr);
        split(right(curr), k - siz(left(curr)) - 1,right(x), y);
        push_up(x);
        return;
    }
    y = copy(curr);
    split(left(curr), k, x,left(y));
    push_up(y);
}

inline int merge(const int x, const int y)
{
    if (!x or !y)return x ^ y;
    push_down(x), push_down(y);
    int curr;
    if (rnk(x) < rnk(y))
    {
        curr = copy(x);
        right(curr) = merge(right(curr), y);
    }
    else
    {
        curr = copy(y);
        left(curr) = merge(x,left(curr));
    }
    push_up(curr);
    return curr;
}

inline int merge(const int l, const int mid, const int r)
{
    return merge(merge(l, mid), r);
}

inline int merge(const int a1, const int a2, const int a3, const int a4, const int a5)
{
    return merge(merge(a1, a2, a3), a4, a5);
}

inline ll Query(const int l, const int r)
{
    int lTree, rTree, lSon, rSon;
    split(root, r, lTree, rTree);
    split(lTree, l - 1, lSon, rSon);
    ll ans = sum(rSon);
    root = merge(lSon, rSon, rTree);
    return ans;
}

enum Update
{
    Add, Cover, Rev
};

inline void Update(const int l, const int r, const Update type, const int val = 0)
{
    int lTree, rTree, lSon, rSon;
    split(root, r, lTree, rTree);
    split(lTree, l - 1, lSon, rSon);
    switch (type)
    {
    case Add:
        Tag.Add(rSon, val);
        break;
    case Cover:
        Tag.Cover(rSon, val);
        break;
    default:
        rev(rSon) ^= 1;
        break;
    }
    root = merge(lSon, rSon, rTree);
}

inline void Copy(const int l1, const int r1, const int l2, const int r2)
{
    int lTree1, rTree1, lson1, rson1;
    split(root, r1, lTree1, rTree1); //[1,r1]、[r1+1,n]
    split(lTree1, l1 - 1, lson1, rson1); //[1,l1-1]、[l1,r1]
    int lTree2, rTree2, lson2, rson2;
    split(root, r2, lTree2, rTree2); //[1,r2]、[r2+1,n]
    split(lTree2, l2 - 1, lson2, rson2); //[1,l2-1]、[l2,r2]
    root = merge(lson2, rson1, rTree2); //[1,l2-1]+[l1,r1]+[r2+1,n]
}

inline void Swap(const int l1, const int r1, const int l2, const int r2)
{
    int lTree2, rTree2, lson2, rson2;
    split(root, r2, lTree2, rTree2); //[1,r2]、[r2+1,n]
    split(lTree2, l2 - 1, lson2, rson2); //[1,l2-1]、[l2,r2]
    int lTree1, rTree1, lson1, rson1;
    split(lson2, r1, lTree1, rTree1); //[1,r1]、[r1+1,l2-1]
    split(lTree1, l1 - 1, lson1, rson1); //[1,l1-1]、[l1,r1]
    root = merge(lson1, rson2, rTree1, rson1, rTree2);
    //[1,l1-1]+[l2,r2]+[r1+1,r2-1]+[l1,r1]+[r2+1,n]
}

vector<int> point;

inline void dfs(const int curr)
{
    if (curr)
    {
        push_down(curr);
        dfs(left(curr));
        point.push_back(val(curr));
        dfs(right(curr));
    }
}

inline void build()
{
    cnt = 0;
    stack<int> st;
    for (const int x : point)
    {
        int last = 0;
        node[++cnt] = FHQ(x);
        while (!st.empty() and rnk(st.top()) > rnk(cnt))push_up(last = st.top()), st.pop();
        if (!st.empty())
            right(st.top()) = cnt;
        left(cnt) = last, st.push(cnt);
    }
    while (!st.empty())
    {
        if (st.size() == 1)root = st.top();
        push_up(st.top());
        st.pop();
    }
}

int n, q, x;

inline void solve()
{
    cin >> n >> q;
    point.resize(n);
    for (int& x : point)cin >> x;
    build();
    while (q--)
    {
        int op, l, r;
        int l1, r1, l2, r2;
        cin >> op;
        if (op == 1)
        {
            cin >> l >> r;
            cout << Query(l, r) << endl;
        }
        else if (op == 2 or op == 3)
        {
            int val;
            cin >> l >> r >> val;
            Update(l, r, op == 2 ? Cover : Add, val);
        }
        else if (op == 4)
        {
            cin >> l1 >> r1 >> l2 >> r2;
            Copy(l1, r1, l2, r2);
        }
        else if (op == 5)
        {
            cin >> l1 >> r1 >> l2 >> r2;
            //保证拼段操作[1,l1-1]+[l2,r2]+[r1+1,r2-1]+[l1,r1]+[r2+1,n]=[1,n]
            if (l1 > l2)swap(l1, l2), swap(r1, r2);
            Swap(l1, r1, l2, r2);
        }
        else
        {
            cin >> l >> r;
            Update(l, r, Rev);
        }
        if (cnt > 10 * n)point.clear(), dfs(root), build();
    }
    point.clear(), dfs(root);
    for (const auto x : point)cout << x << ' ';
}

signed int main()
{
    // MyFile
    Spider
    //------------------------------------------------------
    // clock_t start = clock();
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
    // clock_t end = clock();
    // cerr << "time = " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
}

\[时间复杂度为:\ O(C \times n+m\log{n})，C\ 为建树次数 \]

标签：template,int,题解,void,st,P5350,序列,include,define
From： https://www.cnblogs.com/Athanasy/p/18014811

相关文章

  • UVA12467 Secret Word 题解
    题目传送门前置知识前缀函数与KMP算法解法考虑将\(S\)翻转后得到\(S'\)，然后就转化为求\(S'\)的一个最长子串使得其是\(S\)的前缀。使用KMP求解即可。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglong#d......
  • WGOI R1 真夏飞焰 题解.18014664
    【题目大意】给定序列\(a\)，我们定义序列\(a,b\)是「\(k\)相似」的，当且仅当对于\(a\)中每一个四元组\((l_1,r_1,l_2,r_2)\)，若满足\(r_1-l_1+1=r_2-l_2+1\lek,l_2=r_1+1,a_{l_1\ldotsr_1}=a_{l_2\ldotsr_2}\)，则有\(b_{l_1\ldotsr_1}=b_{l_2\ldot......
  • CF609D题解
    Gadgetsfordollarsandpounds题目传送门题解给一个单\(\log\)题解。“求最早完成买\(k\)样东西的天数。”——很明显的二分答案。在检验函数中，我们应当把前\(k\)小的物品费用之和与总金额作比较，其它题解大多使用直接排序的方法，于是就多了一只\(\log\)。其实没有必......
  • P1631 序列合并
    题目链接：第一时间想到的思路是将\(a,b\)数组中的\(n^2\)个和全部枚举并压入优先队列中，最后再输出前\(n\)个数，代码如下：#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inta[N],b[N];intmain(){ intn; cin>>n; for(inti=0;i<......
  • P4559 [JSOI2018] 列队 题解
    题目链接：列队半年前mark的题，结果现在一下子就会做了。顺便写写我的手玩过程和复杂度说明。考虑比较特殊的情况：比较特殊的，发现从黑色到红色区间我们无论咋选择，由于\(\left|a_{right}-a_{left}\right|\)，这玩意如果\(right\)表示红色的一边，那么这个绝对值可以直接拆掉，那么......
  • [ARC171E] Rookhopper's Tour 题解
    题目链接首先把\(m=2\)和\(m\)为奇数的情况判掉，由于我们要对合法的摆放方案计数，而一个摆放方案要判断合法性就必须通过一组合法的移动过程，对移动的状态进行记录以此转移和优化显然没啥前途，因此我们考虑摆放方案和移动过程之间的联系。一个比较显然的观察是摆放方案和移动过......
  • 2024牛客寒假算法基础集训营2个人补题题解（K、D）
    比赛链接：2024牛客寒假算法基础集训营2K、TokitsukazeandPassword(easy)题面看着很难实际上只要暴力的东西，赛时看了眼题面就溜了血亏爆搜，枚举\(abcd\)和_可能的值，枚举的情况只有\(9*8*7*6*9=27216\)种。判断按照枚举出的对应值排列出的密码是否满足条件，满足就\(ans++\)写完......
  • Atcoder Educational DP Contest 题解
    比赛链接：Atcoderr或者题单A：Frog1常规线性dp，注意到对于每个落点来说，青蛙只能由第\(i-1\)个石头或者第\(i-2\)个石头转移得到，那么我们让\(dp[i]\)为当跳到第\(i\)个石头上的最小费用。此时显然有：\[dp_i=\min(dp_{i-1}+\left|h_i-h_{i-1}\right|,dp_{i-2}+\left|h_......
  • JOISC 2018 题解
    JOISC2018loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1简单题。根据颜色段均摊的结论，每个点到根的路径上颜色段的总和是\(O(n\logn)\)的，于是直接每次暴力找颜色段即可。复杂度\(O(n\log^2n)\)。提交记录D1T2又是计算几何。我们需要画出一条闭合折线，并且......
  • JOISC 2017 题解
    JOISC2017loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1开场放大。首先，对于一个点，它最后覆盖的一定是一个矩形，这就意味着如果我们知道了\(u,d,l,r\)操作各用了多少次，他们之间的顺序是不重要的，我们可以直接当做把一种操作做完再做剩下的操作，这样就可以做到\(O(......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99