首页 > 其他分享 >Solution Set 2023.12.26

Solution Set 2023.12.26

时间：2023-12-26 20:01:18浏览次数：41  
标签：std 26 Set 2023.12 valueType typedef ValueVector id size

[Ynoi Easy Round 2023] TEST_69

发现若一个数被进行了一次有效操作，那么其的值至少会除以 \(2\)，所以一个数至多被操作 \(\mathcal{O}(\log a_i)\) 次。

那么可以通过势能线段树维护操作，考虑什么情况下一个区间不会被操作，即 \(a_i\) 的值不会被改变。即对于区间的任何元素，其值均为 \(x\) 的因子，即区间最小公倍数的值也为 \(x\) 的因子。

那么可以通过线段树维护区间的最小公倍数，然后便可以判定该区间是否会被操作。时间复杂度为 \(\mathcal{O}(n \log n \log a_i)\)。

Code 
#include <bits/stdc++.h>

typedef unsigned long long valueType;
typedef __int128_t bigInt;
typedef std::vector<valueType> ValueVector;
typedef std::vector<bigInt> BigIntVector;

constexpr bigInt MAX = 1ull << 63;
constexpr valueType V = (1ull << 32) - 1;

bigInt lcm(bigInt a, bigInt b) {
    return a == -1 || b == -1 || a / std::__gcd(a, b) * b > MAX ? -1 : a / std::__gcd(a, b) * b;
}

class Tree {
private:
    valueType N;

    ValueVector sum;
    BigIntVector _lcm;

    void update(valueType id) {
        sum[id] = sum[id << 1] + sum[id << 1 | 1];
        _lcm[id] = lcm(_lcm[id << 1], _lcm[id << 1 | 1]);
    }

public:
    explicit Tree(valueType n, ValueVector const &source) : N(n), sum((N << 2) + 10), _lcm((N << 2) + 10) {
        build(1, 1, N, source);
    }

    void update(valueType l, valueType r, bigInt x) {
        update(1, 1, N, l, r, x);
    }

    valueType query(valueType l, valueType r) {
        return query(1, 1, N, l, r);
    }

private:
    void build(valueType id, valueType l, valueType r, ValueVector const &source) {
        if (l == r) {
            sum[id] = source[l];
            _lcm[id] = source[l];

            return;
        }

        valueType const mid = (l + r) >> 1;

        build(id << 1, l, mid, source);
        build(id << 1 | 1, mid + 1, r, source);

        update(id);
    }

    void push(valueType id, valueType l, valueType r, bigInt x) {
        if (_lcm[id] != -1 && x % _lcm[id] == 0)
            return;

        if (l == r) {
            sum[id] = _lcm[id] = std::__gcd(_lcm[id], x);

            return;
        }

        valueType const mid = (l + r) >> 1;

        push(id << 1, l, mid, x);
        push(id << 1 | 1, mid + 1, r, x);

        update(id);
    }

    void update(valueType id, valueType nodeL, valueType nodeR, valueType queryL, valueType queryR, bigInt x) {
        if (queryL <= nodeL && nodeR <= queryR) {
            push(id, nodeL, nodeR, x);

            return;
        }

        valueType const mid = (nodeL + nodeR) >> 1;

        if (queryL <= mid)
            update(id << 1, nodeL, mid, queryL, queryR, x);

        if (queryR > mid)
            update(id << 1 | 1, mid + 1, nodeR, queryL, queryR, x);

        update(id);
    }

    valueType query(valueType id, valueType nodeL, valueType nodeR, valueType queryL, valueType queryR) {
        if (queryL <= nodeL && nodeR <= queryR)
            return sum[id];

        valueType const mid = (nodeL + nodeR) >> 1;

        if (queryR <= mid)
            return query(id << 1, nodeL, mid, queryL, queryR);

        if (queryL > mid)
            return query(id << 1 | 1, mid + 1, nodeR, queryL, queryR);

        return query(id << 1, nodeL, mid, queryL, queryR) + query(id << 1 | 1, mid + 1, nodeR, queryL, queryR);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    ValueVector source(N + 1);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> source[i];

    Tree tree(N, source);

    for (valueType m = 0; m < M; ++m) {
        valueType type;

        std::cin >> type;

        if (type == 1) {
            valueType l, r, x;

            std::cin >> l >> r >> x;

            tree.update(l, r, x);
        } else {
            valueType l, r;

            std::cin >> l >> r;

            std::cout << (tree.query(l, r) & V) << '\n';
        }
    }

    std::cout << std::flush;

    return 0;
}

[Ynoi Easy Round 2023] TEST_90

考虑使用扫描线扫描区间右端点 \(r\)。

若区间向右扩展到 \(r\)，即 \(a_r\) 上一次出现的位置为 \(pre\)，那么对于 \([pre + 1, r]\) 的每个左端点，其对应的区间内的颜色种数奇偶性均会发生改变。

那么可以使用线段树维护当前右端点下左端点对应的区间颜色种数是否为奇数，然后进行区间翻转和历史版本和即可。具体的，对于线段树上每个节点维护出其管辖区间内区间颜色种数为奇数的端点数量，当前的区间版本和，懒标记有三部分，分别是儿子节点是否需要翻转，儿子节点当前状态和翻转状态分别产生了多少次贡献。

总复杂度为 \(\mathcal{O}(n \log n)\)，可以通过。

Code 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<bool> bitset;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;

class Tree {
private:
    valueType N;

    ValueVector weight, sum;
    bitset lazyRev;
    ValueVector lazySum, lazyRevSum;

    void reverse(valueType id, valueType l, valueType r) {
        lazyRev[id] = !lazyRev[id];

        weight[id] = r - l + 1 - weight[id];

        std::swap(lazySum[id], lazyRevSum[id]);
    }

    void insert(valueType id, valueType l, valueType r, valueType add, valueType RevAdd) {
        lazySum[id] += add;
        lazyRevSum[id] += RevAdd;

        sum[id] += weight[id] * add;
        sum[id] += (r - l + 1 - weight[id]) * RevAdd;
    }

    void merge(valueType id) {
        sum[id] = sum[id << 1] + sum[id << 1 | 1];
        weight[id] = weight[id << 1] + weight[id << 1 | 1];
    }

    void push(valueType id, valueType l, valueType r, valueType mid) {
        if (lazyRev[id]) {
            reverse(id << 1, l, mid);
            reverse(id << 1 | 1, mid + 1, r);

            lazyRev[id] = false;
        }

        insert(id << 1, l, mid, lazySum[id], lazyRevSum[id]);
        insert(id << 1 | 1, mid + 1, r, lazySum[id], lazyRevSum[id]);

        lazySum[id] = lazyRevSum[id] = 0;
    }

public:
    explicit Tree(valueType n) : N(n), weight((N << 2) + 10), sum((N << 2) + 10), lazyRev((N << 2) + 10), lazySum((N << 2) + 10), lazyRevSum((N << 2) + 10) {}

    void update(valueType l, valueType r) {
        update(1, 1, N, l, r);
    }

    valueType query(valueType l, valueType r) {
        return query(1, 1, N, l, r);
    }

    void push() {
        insert(1, 1, N, 1, 0);
    }

private:
    void update(valueType id, valueType nodeL, valueType nodeR, valueType queryL, valueType queryR) {
        if (queryL <= nodeL && nodeR <= queryR) {
            reverse(id, nodeL, nodeR);

            return;
        }

        valueType const mid = (nodeL + nodeR) >> 1;

        push(id, nodeL, nodeR, mid);

        if (queryL <= mid)
            update(id << 1, nodeL, mid, queryL, queryR);

        if (queryR > mid)
            update(id << 1 | 1, mid + 1, nodeR, queryL, queryR);

        merge(id);
    }

    valueType query(valueType id, valueType nodeL, valueType nodeR, valueType queryL, valueType queryR) {
        if (queryL <= nodeL && nodeR <= queryR)
            return sum[id];

        valueType const mid = (nodeL + nodeR) >> 1;

        push(id, nodeL, nodeR, mid);

        if (queryR <= mid)
            return query(id << 1, nodeL, mid, queryL, queryR);

        if (queryL > mid)
            return query(id << 1 | 1, mid + 1, nodeR, queryL, queryR);

        return query(id << 1, nodeL, mid, queryL, queryR) + query(id << 1 | 1, mid + 1, nodeR, queryL, queryR);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    ValueVector A(N + 1), prev(N + 1, 0), last(N + 1, 0);

    for (valueType i = 1; i <= N; ++i) {
        std::cin >> A[i];

        prev[i] = last[A[i]] + 1;
        last[A[i]] = i;
    }

    valueType M;

    std::cin >> M;

    PairMatrix query(N + 1);

    for (valueType i = 0; i < M; ++i) {
        valueType l, r;

        std::cin >> l >> r;

        query[r].emplace_back(l, i);
    }

    Tree tree(N);
    ValueVector ans(M);

    for (valueType r = 1; r <= N; ++r) {
        tree.update(prev[r], r);
        tree.push();

        for (auto const &[l, id] : query[r])
            ans[id] = tree.query(l, r);
    }

    for (auto const &x : ans)
        std::cout << x << '\n';

    std::cout << std::flush;

    return 0;
}

[NOI2015] 品酒大会

通过后缀数组可以将问题转化为序列上数对间最小值的贡献问题。

发现在最小值给定的情况下，可以产生贡献的数对会限制在若干区间内。因此可以从大到小枚举最小值，然后使用并查集维护区间的连通性，每次将区间合并后，将区间内的数对贡献加入答案即可。

Code 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::string string;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;

constexpr valueType MIN = std::numeric_limits<valueType>::min();

std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::string const &S) {// 1 - index
    ValueVector SA(2 * N + 1, 0), rank(2 * N + 1, 0), id, count;

    id.reserve(N);

    valueType M = 255;

    count.resize(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        ++count[rank[i] = S[i]];

    std::partial_sum(count.begin(), count.end(), count.begin());

    for (valueType i = N; i >= 1; --i)
        SA[count[rank[i]]--] = i;

    for (valueType w = 1; M != N || w == 1; w <<= 1) {
        id.clear();

        id.push_back(0);

        for (valueType i = N - w + 1; i <= N; ++i)
            id.push_back(i);

        for (valueType i = 1; i <= N; ++i)
            if (SA[i] > w)
                id.push_back(SA[i] - w);

        count.assign(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[id[i]]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[id[i]]]--] = id[i];

        id = rank;

        M = 0;

        for (valueType i = 1; i <= N; ++i)
            rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;
    }

    SA.resize(N + 1);
    rank.resize(N + 1);

    return std::make_pair(SA, rank);
}

template<typename Container_>
ValueVector GetHeight(valueType N, Container_ const &S, ValueVector const &SA, ValueVector const &rank) {
    ValueVector height(N + 1, 0);

    valueType pos = 0;

    for (valueType i = 1; i <= N; ++i) {
        if (rank[i] == 1)
            continue;

        if (pos > 0)
            --pos;

        while (i + pos < S.size() && SA[rank[i] - 1] + pos < S.size() && S[i + pos] == S[SA[rank[i] - 1] + pos])
            ++pos;

        height[rank[i]] = pos;
    }

    return height;
}


template<bool sizeBalanced = true>
class DSU {
private:
    valueType N;

    ValueVector father, size;

    ValueVector min, max;

public:
    explicit DSU(valueType n = 0) : N(n), father(N, 0), size(N, 0), min(N), max(N) {
        std::iota(father.begin(), father.end(), 0);

        std::fill(size.begin(), size.end(), 1);
    }

    void resize(valueType n) {
        N = n;

        father.resize(N, 0);
        size.resize(N);

        std::iota(father.begin(), father.end(), 0);

        std::fill(size.begin(), size.end(), 1);
    }

    void set(valueType n, valueType k) {
        min[n] = max[n] = k;
    }

    valueType find(valueType x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }

    ValuePair unite(int x, int y) {// y -> x if !sizeBalanced
        x = find(x), y = find(y);

        if (x == y)
            return ValuePair(MIN, MIN);

        if (sizeBalanced && size[x] < size[y])
            std::swap(x, y);

        valueType const count = size[x] * size[y];

        father[y] = x;
        size[x] += size[y];

        valueType const value = std::max({max[x] * max[y], min[x] * min[y], max[x] * min[y], min[x] * max[y]});

        min[x] = std::min(min[x], min[y]);
        max[x] = std::max(max[x], max[y]);

        return ValuePair(count, value);
    }

    bool check(valueType x, valueType y) {
        return find(x) == find(y);
    }

    valueType sizeOf(valueType n) {
        return size[find(n)];
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    string S;

    std::cin >> S;

    S = '#' + S;

    auto [SA, rank] = GetSuffixArray(N, S);
    auto height = GetHeight(N, S, SA, rank);

    ValueVector weight(N + 1);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> weight[rank[i]];

    ValueVector ans(N + 1, MIN), count(N + 1, 0);

    DSU<> dsu(N + 1);

    for (valueType i = 1; i <= N; ++i)
        dsu.set(i, weight[i]);

    ValueMatrix bucket(N + 1);

    for (valueType i = 2; i <= N; ++i)
        bucket[height[i]].emplace_back(i);

    for (valueType i = N; i >= 0; --i) {
        for (auto const &x : bucket[i]) {
            auto [count_, value] = dsu.unite(x - 1, x);

            count[i] += count_;
            ans[i] = std::max(ans[i], value);
        }
    }

    for (valueType i = N - 1; i >= 0; --i) {
        count[i] += count[i + 1];
        ans[i] = std::max(ans[i], ans[i + 1]);
    }

    for (auto &iter : ans)
        if (iter == MIN)
            iter = 0;

    for (valueType i = 0; i < N; ++i)
        std::cout << count[i] << ' ' << ans[i] << '\n';

    std::cout << std::flush;

    return 0;
}

[POI2010] ANT-Antisymmetry

直接运行 Manacher 即可，注意不存在长度为奇数的合法串。

Code 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;

std::pair<ValueVector, ValueVector> manacher(const string &data) {
    valueType const size = data.size();

    ValueVector odd(size, 0), even(size, 0);

    for (valueType i = 0, l = 0, r = -1; i < size; ++i) {
        valueType k = (i > r) ? 1 : std::min(odd[l + r - i], r - i + 1);

        while (i - k >= 0 && i + k < size && data[i - k] != data[i + k])
            ++k;

        odd[i] = k--;

        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }

    for (valueType i = 0, l = 0, r = -1; i < size; ++i) {
        valueType k = (i > r) ? 0 : std::min(even[l + r - i + 1], r - i + 1);

        while (i - k - 1 >= 0 && i + k < size && data[i - k - 1] != data[i + k])
            ++k;

        even[i] = k--;

        if (i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }

    return std::make_pair(odd, even);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    string S;

    std::cin >> S;

    auto [odd, even] = manacher(S);

    valueType const ans = std::accumulate(even.begin(), even.end(), (valueType) 0);

    std::cout << ans << std::endl;

    return 0;
}

[SHOI2011] 双倍回文

使用 Manacher 算法可以求出 \(\mathcal{O}(n)\) 种本质不同的回文串，对于每个回文串进行判断即可。

Code 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;

valueType manacher(const string &data) {
    valueType const size = data.size();

    valueType ans = 0;
    ValueVector even(size, 0);

    for (valueType i = 0, l = 0, r = -1; i < size; ++i) {
        valueType k = (i > r) ? 0 : std::min(even[l + r - i + 1], r - i + 1);

        while (i - k - 1 >= 0 && i + k < size && data[i - k - 1] == data[i + k]) {
            ++k;

            if (even[i - k] >= k && even[i - 2 * k] >= k)
                ans = std::max(ans, k);
        }

        if (even[i - k] >= k && even[i - 2 * k] >= k)
            ans = std::max(ans, k);

        even[i] = k--;

        if (i + k > r) {
            for (valueType j = ans + 1; 2 * j <= k + 1; ++j)
                if (even[i - j] >= j)
                    ans = std::max(ans, j);

            l = i - k - 1;
            r = i + k;
        }
    }

    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    string S;

    std::cin >> S;

    valueType const ans = 4 * manacher(S);

    std::cout << ans << std::endl;

    return 0;
}

标签：std,26,Set,2023.12,valueType,typedef,ValueVector,id,size
From： https://www.cnblogs.com/User-Unauthorized/p/2023-12-26.html

相关文章

  • 12.26每日总结1
    今天早上进行了大数据的课堂测试，做完测试后接着做了试验七实验7Spark初级编程实践 1.实验目的（1）掌握使用Spark访问本地文件和HDFS文件的方法（2）掌握Spark应用程序的编写、编译和运行方法2.实验平台（1）操作系统：Ubuntu18.04（或Ubuntu16.04）；（2）Spark版本：2.4.0；（3）Hadoop版本：3.1.3。3.......
  • 12.26每日总结2
    今天下午做了软件企业文化实验大作业公司文化  1.1 公司文化概述我们公司一直坚持以人为本、合作创新、追求卓越的企业文化，这些理念已经深深地融入公司的生产经营之中，成为公司发展的重要动力和核心竞争力。作为软件公司，我们明白员工是最重要的资产，因此我们始终尊重和关爱员......
  • 12.26阅读笔记
    读《需求工程——软件建模与分析》有感今天大致的看了一下这本书，对软件需求分析有了初步的了解，我认为学习软件需求分析需要掌握的内容主要包括五个方面：需求基础与过程、需求获取、需求分析、需求的文档化和验证、需求管理与工程管理。一、需求的基础与过程这一部......
  • 洛谷B3611 【模板】传递闭包 floyd/bitset
    目录floydbitset优化题目链接：https://www.luogu.com.cn/problem/B3611参考题解：https://www.luogu.com.cn/blog/53022/solution-b3611floyd#include<bits/stdc++.h>usingnamespacestd;constintmaxn=101;intn,f[maxn][maxn];intmain(){scanf("%d"......
  • Sqlserver 中的一些SET参数、系统表的查询
    SQL:BatchStarting:是SQLServerProfiler中的一个事件，它指示一个新的SQL批处理正在开始执行。当SQLServer开始执行一个新的批处理时，它会生成此事件。批处理可以包含一个或多个SQL语句，它们将作为一个单独的单元执行。在Profiler或ExtendedEvents中捕获这个事件可以......
  • 百度网盘(百度云)SVIP超级会员共享账号每日更新（2023.12.26）
    合集-网盘(20) 1.百度网盘(百度云)SVIP超级会员共享账号每日更新（2023.11.17）11-182.记录一次自己写的百度网盘不限速下载脚本11-183.百度网盘(百度云)SVIP超级会员共享账号每日更新（2023.11.20）11-214.百度网盘(百度云)SVIP超级会员共享账号每日更新（2023.11.21）11-215.百度网......
  • clearValidate()和resetFields()表单校验的用法和区别
    目标：实现表单重置和清除验证1.整个表单的校验移除<Formref="form"rule={this.rules}><FormItemprop="name"label="姓名"><Input/></FormItem><FormItemprop="age"label="年龄"><Input/></For......
  • 【开源项目推荐】Apache Superset——最优秀的开源数据可视化与数据探索平台
    大家好，我是独孤风。数据可视化是数据领域一个非常重要的应用。而结合了数据可视化和数据探索功能的BI（商业智能）工具，更是被各大公司青睐。但是，由于数据可视化工具的开发成本过高，长期以来一直是商业化的BI工具处于垄断地位。那么，有没有优秀的开源数据可视化与数据探索平台呢？今天......
  • 2023.12.25——每日总结
    学习所花时间（包括上课）：9h代码量（行）：0行博客量（篇）：1篇今天，上午学习，下午学习；我了解到的知识点：1.软件案例分析明日计划：学习......
  • Solution Set 2023.12.25
    【模板】后缀排序考虑首先将所有长度为\(1\)的子串进行排序，然后将所有长度为\(2\)的子串排序，长度不足的以空字符补齐。以此类推，每次排序的子串长度均是上一次排序的子串长度的两倍。最后一次排序后，所有子串均已排序完毕，此时得到的序列即为后缀数组。考虑如何快速进行排序，若......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99