【Codeforces 722C】Destroying Array (数据结构、set)-白红宇的个人博客

【Codeforces 722C】Destroying Array (数据结构、set)

发布日期：2021-06-24 18:19:20 浏览次数：2 分类：技术文章

本文共 2348 字，大约阅读时间需要 7 分钟。

题意

输入一个含有 n（1≤n≤100000）个非负整数的 a 数组和一个 1～n 的排列 p 数组，求每次删除 a[p[i]] 后，最大连续子段和（不能跨越被删除的）是多少？

分析

因为都是非负整数，答案一定是尽量长的区间和。

s[i] 表示 a 的前缀和，区间(l,r]的和就是s[r]-s[l]。

我们用 STL 里的 set 存区间，一开始只有(0,n]区间，删去第一个数后，就要去掉(0,n]区间，加上(0,p[1]-1]和(p[1],n]区间，类似地每次删除一个数，就要去掉包含它的区间，加上两个新区间，同时用 multiset 储存下区间和，每次输出最大的区间和，删除时也删除掉对应的区间和。

需要注意的细节：

set 和 multiset 默认是按从小到大排序，输出最大的只要输出最后一个就可以了；

删除区间和时，因为 multiset 的 erase(value) 会把等于value的元素都删除，只删除一个的话，要先find，再erase；

存区间 make_pair(终点，起点)这样就可以按终点从小到大排序

包含第p个数的区间就是 lower_bound (make_pair(p,0))

增加完对应的区间再删去原来的区间（就是代码里的it）。

URL:

代码：

#include
     
      #define ll long long#define N 100005using namespace std;int n;ll s[N];set< pair
      
        > seg;multiset
       
         sum;void erase(int p){    set< pair
        
          > ::iterator it=seg.lower_bound(make_pair(p,0));    sum.erase(sum.find(s[it->first]-s[it->second]));    seg.insert(make_pair(p-1,it->second)),sum.insert(s[p-1]-s[it->second]);    seg.insert(make_pair(it->first,p)),sum.insert(s[it->first]-s[p]);    seg.erase(it);}ll max(){    multiset
         
           ::reverse_iterator mit=sum.rbegin();    return *mit;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        int a;        scanf("%d",&a);        s[i]=s[i-1]+a;    }    seg.insert(make_pair(n,0));    sum.insert(s[n]);    for(int i=1;i<=n;i++){        int p;        scanf("%d",&p);        erase(p);        printf("%I64d\n",max());    }}

看到一个不用set且更快的代码，大概思路是，倒过来依次放上删除的数，然后找最大连续和。

#include
     
      using namespace std;int x[100002],y[100002],Seg[100002][2];long long sum[100002],maxm;bool memo[100002];vector
      
        ans;int main(){    int n,i; scanf("%d",&n);    for(i=1;i<=n;i++) scanf("%d",&x[i]);    for(i=1;i<=n;i++) scanf("%d",&y[i]);    for(i=1;i<=n;i++)        sum[i] = x[i] + sum[i-1];    for(i=n;i>0;i--)    {        // y[i] == ME ( element to be built )        Seg[y[i]][0] = y[i];        Seg[y[i]][1] = y[i];        memo[y[i]] = 1;        if(memo[y[i]-1])            Seg[y[i]][0] = Seg[y[i]-1][0];        if(memo[y[i]+1])            Seg[y[i]][1] = Seg[y[i]+1][1];        Seg[Seg[y[i]][0]][1] = Seg[y[i]][1];        Seg[Seg[y[i]][1]][0] = Seg[y[i]][0];        maxm = max(maxm,sum[Seg[y[i]][1]] - sum[Seg[y[i]][0]-1]);        ans.push_back(maxm);    }    for(i=ans.size()-2;i>=0;i--)        printf("%I64d\n",ans[i]);    printf("0\n");}

转载地址：https://blog.csdn.net/weixin_34248258/article/details/86394241 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Java虚拟机学习（5）：类加载器(ClassLoader

下一篇：白话debounce和throttle

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题意

分析

发表评论

最新留言

关于作者

推荐文章