首页 > 其他分享 >ICPC2023沈阳K

ICPC2023沈阳K

时间:2024-10-06 12:49:49浏览次数:7  
标签:ICPC2023 std int 沈阳 sum mid ai auto

https://codeforces.com/gym/104869/problem/K

DS题尽量进一步思考,简化维护过程

权值线段树上二分

首先得出一个显然的转化:对于每次操作,求出此次下所有正数从小到大的前缀和的第一次大于所有负数和的绝对值的位置即为答案。

赛时做法

既然要求每次都求a升序下的前缀和,很显然的想到维护ai的权值线段树,然后对这个位置二分答案,时间复杂度 \(O(n\log n\log n)\)。

其实是完全能过的,但是我没有通过思考来简化维护过程:

  • 错误实现

维护到当前这个正数的总数时想当然的把所有正数的 rank 扔到了 multiset 里面,

然后用 std::distance(S.begin(), S.lower_bound(k)) 来表示。

for (auto&[x, v] : querires) {
    //当前这个下标上对应的数的权值线段树的值
    //不一定就是单点赋值,而是把修改前的那个点减去一次a[x], 然后在新的v对应的上面加一次a=v

    if (a[x] <= 0) {negative_abs_sum -= std::abs(a[x]);}
    else {
        int id{discreter.query(a[x])};
        T.modify(id, {-a[x]});
    }
    if (v <= 0) {
        negative_abs_sum += std::abs(v);
    } else {
        int id{discreter.query(v)};
        T.modify(id, {v});
    }
    int k{n + Q};
    {//第一遍k
        int lo{}, hi{n + Q - 1}; while (lo <= hi) {
            int mid{(lo + hi) / 2}; 
            (T.rangeQuery(0, mid + 1).sum > negative_abs_sum) 
            ? hi = mid - 1, k = mid : lo = mid + 1;
        }
    }

    a[x] = v; 

    if (k == n + Q) {
        std::cout << std::size(S) + 1 << "\n";
        continue ;
    }

    i64 pre_sum{T.rangeQuery(0, k).sum};

    int k_take{}, pre_take{(int)(std::distance(S.begin(), S.lower_bound(k)))};


    {//第二遍找k取了多少个
        auto k_sum{T.rangeQuery(k, k + 1).sum};
        auto k_val{discreter.queryInv(k)};
        i64 lo{1}, hi{k_sum / k_val}; while (lo <= hi) {
            i64 mid{(lo + hi) / 2}; 
            (pre_sum + mid * k_val > negative_abs_sum) ? 
            hi = mid - 1, k_take = mid : lo = mid + 1;
        }
    }

    std::cout << k_take + pre_take << "\n";

}

但是牛魔的,set 类容器都是不可随机访问容器啊,求迭代器距离是 \(o(n)\) 的,牛魔的。

而且一开始写 S.lb(k) - S.begin() 不让过编译其实已经告诉你了,但是我当时居然觉得这是对安全性要求比较严格。。。

知道了这个问题之后,要改就很轻松了。

  • 改进思路

显然正数的个数是可以扔到线段树里一起维护的,然后就结束了。

然后还发现另一个唐氏指出,下面那个找第几个的完全可以推个柿子之后 \(O(1)\) 出来,没必要二分。

struct Info {i64 sum{}, cnt{};};//加一个cnt,维护这个权值上的数量

Info operator + (const Info& a, const Info& b) {return {a.sum + b.sum, a.cnt + b.cnt};}

void solve()
{
    int n, Q; std::cin >> n >> Q; std::vector<int> a(n); for (auto& ai : a) {std::cin >> ai;}
    SegmentTree<Info> T(n + Q);
    std::vector<int> positives; for (auto& ai : a) if (ai > 0) {positives.push_back(ai);}
    std::vector<std::pair<int, int>> querires(Q); for (auto&[x, v] : querires) {
        std::cin >> x >> v; --x; if (v > 0) {positives.push_back(v);} 
    }

    Discreter discreter(positives);

    std::map<int, int> cnt; for (auto& ai : a) if (ai > 0) {cnt[ai] += 1;}
    for (auto&[ai, c] : cnt) {T.modify(discreter.query(ai), {c * ai, c});}

    i64 negative_abs_sum{}; for (auto& ai : a) if (ai <= 0) {negative_abs_sum += -ai;}

    for (auto&[x, v] : querires) {
        if (a[x] <= 0) {negative_abs_sum -= std::abs(a[x]);}
        else {
            int id{discreter.query(a[x])};
            T.modify(id, {-a[x], -1});//很显然
        }
        if (v <= 0) {
            negative_abs_sum += std::abs(v);
        } else {
            int id{discreter.query(v)};
            T.modify(id, {v, 1});//很显然
        }
        int k{n + Q};
        {//第一遍k
            int lo{}, hi{n + Q - 1}; while (lo <= hi) {
                int mid{(lo + hi) / 2}; 
                (T.rangeQuery(0, mid + 1).sum > negative_abs_sum) 
                ? hi = mid - 1, k = mid : lo = mid + 1;
            }
        }

        a[x] = v; 

        if (k == n + Q) {
            std::cout << T.rangeQuery(0, n + Q).cnt + 1 << "\n";
            continue ;
        }

        i64 pre_sum{T.rangeQuery(0, k).sum};

        int k_take{}, pre_take{T.rangeQuery(0, k).cnt};//直接维护出来了 [0, k - 1] 的所有正数个数


        {//第二遍找k取了多少个
            auto k_sum{T.rangeQuery(k, k + 1).sum};
            auto k_val{discreter.queryInv(k)};
            //i64 lo{1}, hi{k_sum / k_val}; while (lo <= hi) {
            //    i64 mid{(lo + hi) / 2}; 
            //    (pre_sum + mid * k_val > negative_abs_sum) ? 
            //    hi = mid - 1, k_take = mid : lo = mid + 1;
            //}
          	k_take = (negative_abs_sum - pre_sum + k_val - 1) / k_val;
        }

        std::cout << k_take + pre_take << "\n";

    }

}

佛了。

权值线段树上二分

https://blog.nowcoder.net/n/90af997f26fe4e9ba18c399139d1607e

  • 板子
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {
    if (l >= y || r <= x) {
        return -1;
    }
    if (l >= x && r <= y && !pred(info[p])) {
        return -1;
    }
    if (r - l == 1) {
        return l;
    }
    int m = (l + r) / 2;
    int res = findFirst(2 * p, l, m, x, y, pred);
    if (res == -1) {
        res = findFirst(2 * p + 1, m, r, x, y, pred);
    }
    return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {
    return findFirst(1, 0, n, l, r, pred);
}

考虑怎么优化掉二分这个 log,可以在线段树上二分。

  • 先解决一个类似且简单的线段树二分问题:

对于 \(a_1...a_n\),求第一个 \(a_i > k\) 的 \(i\),带修

显然维护一个最大值的位置线段树:不优化的做法就是二分右端点,\(check\) T.rangeQuery(0, mid + 1).mx > k

但我们发现这个问题存在一个性质,先左子树后右子树这个顺序找到的第一个解一定是最早出现的。

于是有了下述思路:

每次查找时从根递归向下查找, 对于当前区间 \([l,r]\):

  • 若当前节点为叶子结点, 若结点的值满足 $ > v$ , 返回下标即可;

  • 若左子树最大值大于 \(v\)(约束), 则左子树可能存在解, 递归查找左子树; 若左子树查找到解,则直接返回该解(这是一个重要剪枝,可以大幅优化时间, 显然此时即使右子树存在大于 \(v\) 的元素,也不可能是第一个出现的了,所以没必要再查,否则,若右子树最大值大于 $ v$(约束), 递归查找右子树;

struct Info {int mx{-1};};

Info operator+(const Info& a, const Info& b) {return {std::max(a.mx, b.mx)};}

void solve()
{
#define tests
    SegmentTree<Info> T(7); int idx{};
    for (auto& ai : {6, 3, 2, 10, 7, 9, 13}) {T.modify(idx, {ai}); idx += 1;}
    debug(T.findFirst(0, 7, [&](auto& f){return f.mx > 9;}))
    //输出为3,正确
}
  • 找到权值线段树上第一个前缀和(指的是权值线段树上的前缀和,从零开始)大于 k 的权值

这个问题同于上述问题的地方是我们要找的也是第一个位置。

这个问题不同于上述问题的地方是,这个问题要求的是前缀和。前缀和这个信息显然并不属于叶子节点,所以如果这样写:

T.findFirst(0, n + Q, [&](auto& f){return f.sum > k;})

是不正确的,这实际上是在找第一个大于 \(k\) 的叶子节点的权值,也就是单个值而非前缀和。

struct Info {int sum{-1};};

Info operator+(const Info& a, const Info& b) {return {a.sum + b.sum};}

void solve()
{
#define tests
    SegmentTree<Info> T(7); int idx{};
    for (auto& ai : {6, 3, 2, 10, 7, 9, 13}) {T.modify(idx, {ai}); idx += 1;}
    debug(T.findFirst(0, 7, [&](auto& f){return f.sum > 9;}));
    //输出为3,他实际上想说的是 10 > 9
    debug(T.findFirst(0, 7, [&](auto& f){return f.sum > 13;}));
    //输出为-1,因为没有叶子节点上的sum比13大,但我们想输出的是 (6 + 3 + 2 + 10 > 13) -> 3 
}

要怎么维护前缀和呢?我们发现一个权值线段树上一个叶子节点的前缀和肯定是等于遍历到他之前所有叶子节点的和,也就是左子树是一定会贡献到右子树上的。

那么在操作的时候我们每次遍历左子树失败(也就是左子树的总和还不够大),准备遍历右子树时,就把左子树的贡献算上去,这样到叶子节点的时候就是对应的前缀和了。

int findFirst(int p, int l, int r, int x, int y, i64 tar) {
    if (l >= y || r <= x) {
        return -1;
    }
    if (l >= x && r <= y && (info[p].sum <= tar)) {
        return -1;
    }
    if (r - l == 1) {
        return l;
    }
    int m = (l + r) / 2;
    int res = findFirst(2 * p, l, m, x, y, tar);
    if (res == -1) {
        res = findFirst(2 * p + 1, m, r, x, y, tar - info[2 * p].sum);//把左边的所有贡献加起来,因为是求前缀和,也就是说接下来只要查找到比 tar 减去左边的贡献后还大的值就行了。
    }
    return res;
}
//第一遍线段树二分,找到第一个大于负数绝对值的前缀和的下标
int k{T.findFirst(0, n + Q, negative_abs_sum)};
if (k == -1) {std::cout << T.rangeQuery(0, n + Q).cnt + 1 << "\n"; continue;}
//第二遍找k取了多少个
auto pre_sum{T.rangeQuery(0, k).sum}, pre_take{T.rangeQuery(0, k).cnt}; int k_val{discreter.queryInv(k)};
i64 k_take{(negative_abs_sum - pre_sum) / k_val + 1};

标签:ICPC2023,std,int,沈阳,sum,mid,ai,auto
From: https://www.cnblogs.com/kdlyh/p/18448994

相关文章

  • 2023ICPC 沈阳
    赛时5题xixike仍然是平衡树大神。gxd仍然是计数大神。而我签了三个到下班。c题签到,略J:结论题E:bfs的一个dp,第一次写写了比较久K:xixike平衡树过的。赛后补题的时候我先是写了一个双log动态开点权值线段树,然后别人教我线段树二分到了单log。但是直接离散化不动态开点的......
  • ICPC2021 沈阳站 M String Problem 题解 | 十种做法一网打尽 , 一道题带你回顾字符串科
    题目传送门题意给定一个字符串,求每个前缀的字典最大序子串。注意到:对于每个前缀$s_{[1,i]}$,字典序最大子串的右边界一定是\(i\)。随着着\(i\)的增大,字典序最大子串的左边界一定是单调不减的。解法不分先后。后缀数组SASA&SAM后缀数组&后缀自动机SA对所有......
  • ICPC2023沈阳站(B C D E I J K M)
    本场金牌线为六题前一半,这里提供难度前八题的题解。本场真是个细节场,银牌金牌题细节都相当地多。ICPC2023沈阳站C:作为签到题,对这种赛制熟悉不熟悉直接区分了一血时间。谔谔。#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmat......
  • ICPC2023杭州站题解(B D E F G H J M)
    本场金牌数量较其他场多(45枚),但金牌线题数不多。五题为分水岭,五道简单题过后所有题均为金牌题,其中有四道可做,即ABEF,做出任意一道即可拿金牌。这里提供除A题以外的所有可做题的题解。ICPC2023杭州站:M:加入比当前选择的所有数大的数一定会让平均值上升,因此答案数列中,V图中的......
  • ICPC2023南京站题解(A C D F G I L M)
    本场金牌线为7题前一半。做出8题可稳金牌,这里是难度前8题的题解。ICPC2023南京站I:签到题。#include<bits/stdc++.h>#definelllonglong#defineQWQcout<<"QwQ"<<endl;#defineFOR()llle=e[u].size();for(lli=0;i<le;i++)usingnamespacestd;constllN=501010;......
  • 【沈阳航空航天大学】 <C++ 类与对象计分作业>
    C++类与对象1.设计用类完成计算两点距离2.设计向量类3.求n!4.出租车收费类的设计与实现5.定义并实现一个复数类6.线性表类的设计与实现7.数组求和8.数组求最大值1.设计用类完成计算两点距离【问题描述】设计二维点类Point,包括私有成员:横坐标x,纵坐标y。能够......
  • ICPC2023 陕西邀请赛 题解
    G-PermutationQuestion找到一个排列\(p\),使得\(\prod_{i=1}^nlcm(p_i,p_{(imodn)+1})\)最大Solution考虑到\(x\)和\(x-1\)必然是互质的所以顺序排列即可Code#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;for(inti......
  • ICPC2023 杭州 题解
    M-V-DiagramSolution很显然,连续的子序列的一段肯定是包括最左边或最右边的其中一个点Code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllinf=1ll<<60;intmain(){intt;cin>>t;while(t--){ intn;cin>>n;......
  • 2023ICPC沈阳区域赛I题Three Rectangles补题
    题意有一个(0,0)(左下角)到(H,W)(右上角)的矩形区域,给出3个小矩形的h和w,要求3个矩形盖住矩形区域的放置方案:要求3个矩形不能旋转,只能放到整点上,不能超出矩形区域,可以重叠。mod1e9+7。H,W范围1e9,\(1\leqh_i\leqH,1\leqw_i\leqW\)分析及实现由3个小矩形盖住大矩形,通过思考......
  • BUPT 2024 Spring Training #3(ICPC2023 杭州站)Ag复盘
    D-OperatorPrecedence求一个长度为\(2n\)的序列\(a_{2n}\)满足条件\((a_1×a_2)+(a_3×a_4)+\ldots+(a_{2n-1}×a_{2n})=a_1×(a_2+a_3)×\ldots×(a_{2n-2}+a_{2n-1})×a_{2n}\)solution构造题显然找特殊规律。考虑到乘法构造难度大于加法,可以从乘法开始考虑。......