【Codeforces 722C】Destroying Array (数据结构、set)
2023-09-11 14:19:25 时间
题意
输入一个含有 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,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<ll> ::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<bits/stdc++.h> using namespace std; int x[100002],y[100002],Seg[100002][2]; long long sum[100002],maxm; bool memo[100002]; vector<long long> 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"); }
相关文章
- 【显示执行计划】在普通用户下使用set autot 查看执行计划
- 【Oracle】alter system set events 相关知识
- java笔记四:Set接口
- [Angular 2] Set Values on Generated Angular 2 Templates with Template Context
- ini_set
- [NPM] Set default values for package.json using npm set
- js es6 介绍set,WeakSet
- ES6学习之路7----set数据结构
- Scala集合:Set集合
- set容器之自定义数据类型排序
- SAP BSP set server cache via CL_BSP_UTILITY-SET_BROWSER_CACHE
- CRM Set Type com_commercial的UI界面
- Hive / ClickHouse 行转列函数 collect_set() / groupUniqArray()
- C++之map/set与undered_map/undered_set区别(一百一十八)
- Dart基础第6篇:集合类型List Set Map详解 以及循环语句 forEach map where any every