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

时间:2022-12-30 16:29:05

题意

输入一个含有 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:http://codeforces.com/contest/722/problem/C

代码:

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

  

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

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

【Codeforces 722C】Destroying Array (数据结构、set)的更多相关文章

  1. Codeforces 722C&period; Destroying Array

    C. Destroying Array time limit per test 1 second memory limit per test 256 megabytes input standard ...

  2. CodeForces - 722C Destroying Array (并查集&sol;集合的插入和删除)

    原题链接:https://vjudge.net/problem/511814/origin Description: You are given an array consisting of n no ...

  3. CodeForces 722C Destroying Array &lpar;并查集&rpar;

    题意:给定 n 个数,然后每次破坏一个位置的数,那么剩下的连通块的和最大是多少. 析:用并查集来做,从后往前推,一开始什么也没有,如果破坏一个,那么我们就加上一个,然后判断它左右两侧是不是存在,如果存 ...

  4. &lbrack;并查集&plus;逆向思维&rsqb;Codeforces Round 722C Destroying Array

    Destroying Array time limit per test 1 second memory limit per test 256 megabytes input standard inp ...

  5. Intel Code Challenge Elimination Round &lpar;Div&period;1 &plus; Div&period;2&comma; combined&rpar; C&period; Destroying Array -- 逆向思维

    原题中需要求解的是按照它给定的操作次序,即每次删掉一个数字求删掉后每个区间段的和的最大值是多少. 正面求解需要维护新形成的区间段,以及每段和,需要一些数据结构比如 map 和 set. map< ...

  6. Intel Code Challenge Elimination Round &lpar;Div&period;1 &plus; Div&period;2&comma; combined&rpar; C&period; Destroying Array 带权并查集

    C. Destroying Array 题目连接: http://codeforces.com/contest/722/problem/C Description You are given an a ...

  7. CF722C&period; Destroying Array&lbrack;并查集 离线&rsqb;

    链接:Destroying Array C. Destroying Array time limit per test 1 second memory limit per test 256 megab ...

  8. Codeforces 482B Interesting Array&lpar;线段树&rpar;

    题目链接:Codeforces 482B Interesting Array 题目大意:给定一个长度为N的数组,如今有M个限制,每一个限制有l,r,q,表示从a[l]~a[r]取且后的数一定为q,问是 ...

  9. Codeforces 1077C Good Array 坑 C

    Codeforces 1077C Good Array https://vjudge.net/problem/CodeForces-1077C 题目: Let's call an array good ...

随机推荐

  1. &lbrack;c&num;&rsqb;一个窗体调用另一个窗体的事件

    StuAddForm a = new StuAddForm(); a.IfStudent(textBox1.Text.Trim()):

  2. Java Socket 编程指南

    Socket,又称为套接字,Socket是计算机网络通信的基本的技术之一.如今大多数基于网络的软件,如浏览器,即时通讯工具甚至是P2P下载都是基于Socket实现的.本文会介绍一下基于TCP/IP的S ...

  3. 序列化和持久化 merge方法和saveOrUpdate方法

    merge方法和saveOrUpdate方法的区别 merge方法是把我们提供的对象转变为托管状态的对象:而saveOrUpdate则是把我们提供的对象变成一个持久化对象:说的通俗一点就是:saveO ...

  4. 修改linux系统时间、rtc时间以及时间同步

    修改linux的系统时间用date -s [MMDDhhmm[[CC]YY][.ss]] 但是系统重启就会从新和硬件时钟同步. 要想永久修改系统时间,就需要如下命令:hwclock hwclock - ...

  5. HTML的有序列表

    针对HTML的有序列表,由于平常使用的不是很多,刚开始使用的时候也是有遇到一些坑,有几个小问题: 1.li的宽度不能设置为100%,这样的话就没办法看到前面的序号 2.如果设置li的颜色字体大小,前面 ...

  6. 自学Zabbix3&period;7-事件Event

    配置item.trigger.都是为发送报警做准备的,什么是事件通知呢?简单的说故障发生了,zabbix会发邮件或者短信给你,告诉你服务器的一些状况. 1. 通知条件 发送通知,需要有如下步骤 定义一 ...

  7. Lua和C的语法差别

    没有main函数 Lua是脚本语言,没有固定入口的main函数.当lua解析器解析某个lua代码文件时,lua解析器一样一行的解析lua脚本. print("Hello lua") ...

  8. Spring Cloud分布式微服务云架构

    分布式.微服务.云架构 JAVA语言开发.跨平台.高性能.高可用.安全.服务化.模块化.組件化.驱动式开发模式 commonservice eurekaNetflix 云端服务发现,一个基于 REST ...

  9. hog cython

    pip安装cython之后,将下面代码写入hogtest2.pyx文件(我通过改文件后缀新建) import numpy as np from PIL import Image cimport num ...

  10. Google Map 形状显示

    添加多段线 Polyline 构造函数带有一组用于指定线的 LatLng 坐标的 PolylineOptions,以及一组用于调整多段线视觉行为的样式. Polyline 对象在地图上绘制为一系列直线 ...