当前位置: 首页 > news >正文

The 2023 ICPC Asia Shenyang Regional Contest K. Maximum Rating

K.Maximum Rating


原题链接

题意简述

给定一个长为 \(n\) 的序列,通过重排操作后,记从 1到 i 的前缀和为 \(pre_i\),判断通过重排能产生多少可能的值 $ \sum_{j=1}^n [pre_j > \max_{i=1}^{j-1} pre_i]$.

解题思路

注意到:
1.可能的最大值就是正数的个数。
2.可能的最小值是把正数从小到大往后排,负数全插最前面去到的。
3.贪心的把负数看成一个集合,正数从大到小排列,然后把负数集合从后往前插入每个位置,这样可以得到最大值和最小值中间每一种数字。
4.所以答案就是询问正数的个数减去不可以被负数绝对值之和抵消的正数的个数
把正数和负数分开,
对于每个查询就是快速询问小于等于负数绝对值和的正数前缀的最大位置是多少?
单点修,区间查,考虑离散化后建一棵权值树状数组 or 权值线段树,每次二分找出一个合法的位置
时间复杂度 \(\mathcal{O}(n \log n \log n)\)

AC code

//Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define lc (p<<1)
#define rc (p<<1|1)
#define dbg(...) cout<<"usedchang"<<endl
const int N=4e5+2;
int n,m;
namespace Seg{struct node{int l,r;ll sum,add;ll num,laz;}tree[N<<2];void pushup(int p){tree[p].sum=tree[lc].sum+tree[rc].sum;tree[p].num=tree[lc].num+tree[rc].num;}void pushdown(int p){if(tree[p].add==0) return;tree[lc].sum+=1LL*(tree[lc].r-tree[lc].l+1)*tree[p].add;tree[lc].num+=1LL*(tree[lc].r-tree[lc].l+1)*tree[p].laz;tree[lc].add+=tree[p].add;tree[rc].sum+=1LL*(tree[rc].r-tree[rc].l+1)*tree[p].add;tree[rc].num+=1LL*(tree[rc].r-tree[rc].l+1)*tree[p].laz;tree[rc].add+=tree[p].add;tree[p].add=tree[p].laz=0;}void build(int l=1,int r=n+m+1,int p=1){int mid=l+r>>1;tree[p]={l,r,0,0,0,0};if(l==r) return;build(l,mid,lc);build(mid+1,r,rc);pushup(p);}void upd(int x,int y,ll k,int w=1,int p=1){if(x<=tree[p].l&&y>=tree[p].r){tree[p].sum+=1LL*k*(tree[p].r-tree[p].l+1);tree[p].add+=k;tree[p].num+=1LL*w*(tree[p].r-tree[p].l+1);tree[p].laz+=w;return;}int mid=tree[p].l+tree[p].r>>1;pushdown(p);if(x<=mid) upd(x,y,k,w,lc);if(y>mid) upd(x,y,k,w,rc);pushup(p);}ll qry(int x,int y,int p=1){if(x>y) return 0;if(x<=tree[p].l&&y>=tree[p].r){return tree[p].sum;}pushdown(p);ll ans=0;int mid=tree[p].l+tree[p].r>>1;if(x<=mid) ans+=qry(x,y,lc);if(y>mid) ans+=qry(x,y,rc);return ans;}int asknums(int x,int y,int p=1){if(x>y) return 0;if(x<=tree[p].l&&y>=tree[p].r){return tree[p].num;}pushdown(p);int ans=0;int mid=tree[p].l+tree[p].r>>1;if(x<=mid) ans+=asknums(x,y,lc);if(y>mid) ans+=asknums(x,y,rc);return ans;}
}
int main(){cin.tie(0)->ios::sync_with_stdio(false);cin>>n>>m;Seg::build();vector<int>a(n),b;ll sum=0;for(int i=0;i<n;i++) {cin>>a[i];b.emplace_back(a[i]);}vector< pair<int,int> >q(m);for(int i=0;i<m;i++){int x,k;cin>>x>>k;--x;q[i]={x,k};b.emplace_back(k);}auto c=b;sort(b.begin(),b.end());auto Idx=[&](int k){return lower_bound(b.begin(),b.end(),k)-b.begin()+1;};for(auto &x:a) {if(x<0) sum+=-x;Seg::upd(Idx(x),Idx(x),x);}for(auto &[x,y]:q){int Old=Idx(a[x]);Seg::upd(Old,Old,-a[x],-1);if(a[x]<0) sum-=-a[x];a[x]=y;int New=Idx(a[x]);Seg::upd(New,New,a[x],1);if(a[x]<0) sum+=-a[x];int st=Idx(1),ed=b.size();int l=st,r=ed;if(l>r){cout<<1<<endl;continue;}while(l<=r){int mid=l+r>>1;if(Seg::qry(st,mid)<=sum) l=mid+1;else r=mid-1;}ll ans=Seg::asknums(st,l-1)+1;ll rem=sum-Seg::qry(st,l-1);ll k=(l<b.size()&&b[l]>0)?rem/b[l]:0;cout<<ans+k<<endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=31691

相关文章:

  • 用积木思维搞定TCP/IP——LuatOS快速上手指南
  • 2025 年江门办公室装修公司最新推荐排行榜:助力企业避开装修陷阱,精选优质服务品牌
  • WPF自动弹出软件键盘
  • 【碎片化学习】JMeter中常用的设置优化
  • win10系统以太网未识别网络 没有有效ip配置怎么办?
  • 怎么考PostgreSQL PG中级认证证书
  • 大学本科及研究生金融专业题库数据集:109157条高质量中文金融教育题库数据,涵盖银行证券保险投资理财等全领域,支持智能教育系统与机器学习算法训练的专业数据集
  • 【比赛记录】2025CSP-S模拟赛61
  • 基于Rokid CXR-S SDK的智能AR翻译助手技术拆解与实现指南
  • VRED 2025:专业三维可视化与虚拟现实领域的高效设计工具
  • 2025年办公与商业空间软膜天花系统推荐榜:办公室/酒店/展厅/商场/汽车4S店软膜天花厂家,专注光环境与装饰一体化解决方案
  • SZMS 251009 订题赛 题解
  • Debian 12安装docker的正确方法
  • 【流量网关】k8s与apisix统一的流量入口方案(内网版)
  • 基于STM32F4系列MCU和CS5530 24位SDADC的称重传感器系统实现
  • 2025 年环保板材厂家最新推荐榜:硬包板 / 竹木纤维板等全品类 企业深度解析
  • kong 网关下集成 Consul服务注册与发现
  • cad圆滑连接两段线:blend
  • 在 gitea 服务器端查询 lfs 文件占用情况
  • HDR图像生成算法详解
  • Introduction: Why Optimization?
  • 基于MATLAB的二自由度机械臂PID控制仿真
  • Spring AOP原理
  • Ventoy引导Kali live USB持久化
  • 知识库管理工具深度测评:ONES、Confluence 等10款工具全面对比
  • 好的测试数据管理,到底要怎么做?
  • 【面试题】人工智能工程师高频面试题汇总:循环神经网络篇(题目+答案)
  • 做了个手机上的“视频播放器”,获益匪浅
  • CEF关闭流程
  • AI一周资讯 251005-251015