首页 > 其他分享 >U404643 帕鲁大陆染色的一天 题解

U404643 帕鲁大陆染色的一天 题解

时间：2024-02-03 12:14:31浏览次数：21  
标签：typedef U404643 int 题解 void template include 帕鲁 define

题目链接：帕鲁大陆染色的一天

注意到每种颜色是独立的，所以我们能够比较容易地得知每种颜色在一系列操作中的出现和消失时间。我们注意到每个操作加入以后会有两个影响，对它后面的操作显然颜色总数都会 \(+1\)，对前面操作的影响来说，显然会覆盖掉某些颜色，导致某些颜色消失，换句话来讲消除了前面操作对后面操作的影响 \(1\)。

基于上述的过程，其实这是在时间轴的操作影响，并且询问也是基于时间轴，所以我们可以在时间轴上维护一个树状数组用于维护每个操作的影响即：

  1. 前面的操作加入以后会使得当前时间点以后的所有操作对应的时间点颜色数 \(+1\)。

  2. 可能在当前时间点的时候应该去除前面的某个操作对后面操作的影响。

没看懂意思的可以看这个：P8512 [Ynoi Easy Round 2021] TEST_152 题解。

那么基于扫描线离线操作下来，从左往右不断加入某个操作，由于需要考虑颜色何时删除，所以我们需要为每个颜色或者说是时间点维护一个桶表示颜色总数，当清空时它对应的时间点贡献也就没了。而清空一个区间的所有连续颜色段的贡献我们可以考虑 线段树 或者 珂朵莉树 来实现。最后，判断的时候注意判断掉颜色为 \(0\) 的点，不考虑这部分贡献。

线段树做法，具体的维护这个区间是否是连续段，是连续段的话颜色或者说时间点是啥，本题颜色和时间点其实是一致的。然后支持区间覆盖，所以需要一个覆盖标记。当左右子树皆为连续段且颜色相同就能归并为一个新的连续段区间。删除贡献时不为连续段就往下递归就行了，复杂度分析参照珂朵莉树的均摊分析。

线段树做法 
#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 = 1e6 + 10;

int n, m, q;

int cnt[N];
int bit[N];

inline void add(int x, const int val)
{
    while (x <= n)bit[x] += val, x += lowBit(x);
}

inline int query(int x)
{
    int ans = 0;
    while (x)ans += bit[x], x -= lowBit(x);
    return ans;
}

struct Node
{
    bool isSame = true;
    int tim;
    int cov;
} node[N << 2];

#define isSame(x) node[x].isSame
#define tim(x) node[x].tim
#define cov(x) node[x].cov

inline void Cover(const int curr, const int val)
{
    tim(curr) = val;
    cov(curr) = val;
    isSame(curr) = true;
}

inline void push_down(const int curr)
{
    if (cov(curr))
    {
        Cover(ls(curr),cov(curr));
        Cover(rs(curr),cov(curr));
        cov(curr) = 0;
    }
}

inline void push_up(const int curr)
{
    if (isSame(ls(curr)) and isSame(rs(curr)) and tim(ls(curr)) == tim(rs(curr)))
    {
        isSame(curr) = true, tim(curr) = tim(ls(curr));
    }
    else isSame(curr) = false;
}

inline void Del(const int curr, const int l, const int r, const int s = 1, const int e = n)
{
    if (isSame(curr))
    {
        if (tim(curr))
        {
            cnt[tim(curr)] -= min(e, r) - max(s, l) + 1;
            if (!cnt[tim(curr)])add(tim(curr), -1);
        }
        return;
    }
    const int mid = s + e >> 1;
    push_down(curr);
    if (l <= mid)Del(ls(curr), l, r, s, mid);
    if (r > mid)Del(rs(curr), l, r, mid + 1, e);
}

inline void Cov(const int curr, const int l, const int r, const int val, const int s = 1, const int e = n)
{
    if (l <= s and e <= r)
    {
        Cover(curr, val);
        return;
    }
    const int mid = s + e >> 1;
    push_down(curr);
    if (l <= mid)Cov(ls(curr), l, r, val, s, mid);
    if (r > mid)Cov(rs(curr), l, r, val, mid + 1, e);
    push_up(curr);
}

inline void assign(const int Time, const int l, const int r)
{
    Del(1, l, r);
    Cov(1, l, r, Time);
    add(Time, 1);
    cnt[Time] += r - l + 1;
}

int L[N], R[N];
vector<pii> seg[N];
int ans[N];

inline void solve()
{
    cin >> n >> m;
    forn(i, 1, m)cin >> L[i] >> R[i];
    cin >> q;
    forn(i, 1, q)
    {
        int l, r;
        cin >> l >> r;
        seg[r].emplace_back(l, i);
    }
    forn(r, 1, m)
    {
        assign(r, L[r], R[r]);
        for (const auto [l,id] : seg[r])ans[id] = query(r) - query(l - 1);
    }
    forn(i, 1, q)cout << ans[i] << endl;
}

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;
}
珂朵莉树做法 
#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 = 1e6 + 10;

int n, m, q;

struct ODT
{
    int l, r;
    mutable int tim;

    bool operator<(const ODT& other) const
    {
        return l < other.l;
    }
};

set<ODT> node;
int cnt[N];
typedef set<ODT>::iterator iter;
int bit[N];

inline void add(int x, const int val)
{
    while (x <= n)bit[x] += val, x += lowBit(x);
}

inline int query(int x)
{
    int ans = 0;
    while (x)ans += bit[x], x -= lowBit(x);
    return ans;
}

inline iter split(const int pos)
{
    auto it = node.lower_bound(ODT(pos, 0, 0));
    if (it != node.end() and it->l == pos)return it;
    --it;
    if (it->r < pos)return node.end();
    auto [l,r,tim] = *it;
    node.erase(it), node.insert(ODT(l, pos - 1, tim));
    return node.insert(ODT(pos, r, tim)).first;
}

inline void assign(const int Time, const int l, const int r)
{
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; ++it)
    {
        auto [l,r,tim] = *it;
        if (tim)
        {
            cnt[tim] -= r - l + 1;
            if (!cnt[tim])add(tim, -1);
        }
    }
    add(Time, 1);
    cnt[Time] += r - l + 1;
    node.erase(itl, itr), node.insert(ODT(l, r, Time));
}

int L[N], R[N];
vector<pii> seg[N];
int ans[N];

inline void solve()
{
    cin >> n >> m;
    forn(i, 1, m)cin >> L[i] >> R[i];
    cin >> q;
    forn(i, 1, q)
    {
        int l, r;
        cin >> l >> r;
        seg[r].emplace_back(l, i);
    }
    node.insert(ODT(1, n, 0));
    forn(r, 1, m)
    {
        assign(r, L[r], R[r]);
        for (const auto [l,id] : seg[r])ans[id] = query(r) - query(l - 1);
    }
    forn(i, 1, q)cout << ans[i] << endl;
}

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(m\log{n}) \]

标签：typedef,U404643,int,题解,void,template,include,帕鲁,define
From： https://www.cnblogs.com/Athanasy/p/18004512

相关文章

  • P2178 [NOI2015] 品酒大会 题解
    P2178[NOI2015]品酒大会题解纪念一下第一道完全自己想出来的紫NOI题。思路由于r相似有单调性的性质，题目中也提示了这一点，考虑按\(height_i\)从大到小把所有相邻的\(sa\)数组内两个后缀合并，用并查集维护，发现第一问的答案就是\[\sum_{i是并查集的根}\binom{size_i}{2}......
  • 从一键部署热门游戏幻兽帕鲁到探索未来个人元宇宙
    写这个部署体验教程时候，我一直思考作为一个中年程序员，游戏爱好者来说，我到底应该写什么样的内容？以阿里云这种快捷部署游戏服务器的模式，对我们有哪些影响，于是我先起草了一个思维导图，通过思维导图大家可以快速了解下我的创作思路。官方教程详戳：不需要懂技术，1分钟幻兽帕鲁服务器搭建......
  • P10118 『STA - R4』And 题解
    题目看到位运算，直接二进制拆分考虑。首先\(x\operatorname{AND}y=B\)，设\(x=B+m\)，\(y=B+n\)，知道\(x+y=A\)，所以设\(W=n+m=A-2\timesB\)，\(y-x\)等价于\(n-m\)。因为已知\(x\operatorname{AND}y=B\)，所以\(n\operatorname{AND}m=0\)，着意味着在二进制下\(n\)和\(m\)不......
  • P4064 [JXOI2017] 加法 题解
    P4064[JXOI2017]加法题解思路一眼二分答案，这种区间的题很难不排序，可以考虑这个贪心check：区间左端点升序排序之后，每次遇到一个点，判断这个点是否合法，如果不合法就在所有左端点在这个点左边的区间里选择右端点最大的一个。感性证明：这个点之前的点已经保证合法了，所有左端点在......
  • AT_past202107_l 题解
    Solution题目来源：AT_past202107_l（inAtCoder|inluogu）用线段树维护区间最小值。单点修改很好写，我们看怎么区间寻找最小值位置。对于每次询问，我们先求出所查询区间\([x_i,y_i]\)的最小值\(p\)，然后写一个寻找函数。对于当前区间\([l,r]\)，分以下情况来看：如果当前区间长......
  • CF1542E2 题解
    一、题目描述：设$\pi(x)$为全排列$x$的逆序对数。给定$n,m$，求有多少对长度为$n$ 的排列$p,q$，使得$p$的字典序小于$q$，且$\pi(p)>\pi(q)$答案对$m$取模。数据范围：$1\len\le500,1\lem\le10^9$。 二、解题思路：一开始列出计算式个人感觉是......
  • 230718B3-path 题解
    感谢cn_ryh大佬的怂恿（否则我真不会动这个题感谢cszhpdx的指导帮助qwq（让我们膜拜一下场切的浩杨哥orz解决这个题让人很有成就感（题意给定一个基环树，边有长度l、限速v、价值w（每单位时间）已知起点s、终点t、最高速度u，求最小花费边数、询问次数$10^5$解法首先学习一下基......
  • 【幻兽帕鲁教程】一键配置游戏参数
    幻兽帕鲁部署完成之后，如果您想要按照自己的喜好来对游戏世界进行DIY，打造个性化的服务器，那么就需要通过配置游戏参数来完成。最近一段时间，这一步可谓是让众多玩家头疼不已，如何找到配置文件？如何配置死亡不掉落？如何设置游戏房间密码？由于直接编辑配置文件的成本较高，且可能会各种各样......
  • 基于客户真实使用场景的云剪辑Timeline问题解答与代码实操
    本文为阿里云智能媒体服务IMS「云端智能剪辑」实践指南第6期，从客户真实实践场景出发，分享一些Timeline小技巧（AI_TTS、主轨道、素材对齐），助力客户降低开发时间与成本。欧叔｜作者故事的开始要从一条客户的真实反馈说起。  Round1：视频比音频长，怎么办？某天，一位客户加入了智能媒......
  • 盘点那些硬件+项目学习套件：Hi3861鸿蒙开发板及入门常见问题解答
    华清远见20岁了~过去3年里，华清远见研发中心针对个人开发板业务，打造了多款硬件+项目学习套件，涉及STM32单片机、嵌入式、物联网、人工智能、鸿蒙、ESP32、阿里云IoT等多技术方向。今天我们来盘点一下，比较受欢迎几款“硬件+项目”学习套件，以及一些初学者比较关注的问题。盘点二：Hi3861......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99