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

题解:CF1830E Bully Sort

题目:

每 bully swap \(i,j\) 会使得 \(\sum_i \left | i-p_i \right |\) 减少 \((2j-2i)\),使得逆序对数减少 \((2j-2i-1)\)
又因为一个数始终单向移动,所以 bully swap 次数为 \((\sum_i \left | i-p_i \right | - 逆序对数)\)

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int QAQ=5e5+7;
int n,q,p[QAQ],cnt;
ll da[QAQ],ans[QAQ],ans1;
struct xxx {int a,b,c,cnt;} d[QAQ*6];
int s[QAQ];
#define lbd(x) (x&(-x))
void jia(int x,int c)
{for(int i=x;i<=n;i+=lbd(i)) s[i]+=c;
}
int cha(int x)
{int da=0;for(int i=x;i;i-=lbd(i)) da+=s[i];return da;
}
bool cmp1(xxx a,xxx b) {return a.b<b.b;}
void cdq(int l,int r)
{if(l==r) return ;int mid=(l+r)>>1,i=l;cdq(l,mid),cdq(mid+1,r),sort(d+l,d+mid+1,cmp1),sort(d+mid+1,d+r+1,cmp1);for(int j=mid+1;j<=r;j++){while(i<=mid&&d[i].b<=d[j].b) jia(d[i].c,d[i].cnt),i++;ans[d[j].a]+=(ll)d[j].cnt*(cha(n)-cha(d[j].c));}for(int k=l;k<i;k++) jia(d[k].c,-d[k].cnt);i=mid;for(int j=r;j>=mid+1;j--){while(i>=l&&d[i].b>=d[j].b) jia(d[i].c,d[i].cnt),i--;ans[d[j].a]+=(ll)d[j].cnt*cha(d[j].c-1);}for(int k=mid;k>i;k--) jia(d[k].c,-d[k].cnt);
}
signed main()
{cin>>n>>q;for(int i=1;i<=n;i++) cin>>p[i],ans1+=abs(i-p[i]),d[++cnt]={0,i,p[i],1};for(int i=1,x,y;i<=q;i++)cin>>x>>y,d[++cnt]={i,x,p[x],-1},d[++cnt]={i,y,p[y],-1},ans1-=abs(x-p[x]),ans1-=abs(y-p[y]),swap(p[x],p[y]),d[++cnt]={i,x,p[x],1},d[++cnt]={i,y,p[y],1},ans1+=abs(x-p[x]),ans1+=abs(y-p[y]),da[i]=ans1;cdq(1,cnt);for(int i=1;i<=q;i++) ans[i]+=ans[i-1];for(int i=1;i<=q;i++) cout<<da[i]-ans[i]<<'\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=30918

相关文章:

  • 斑马日记2025.10.10
  • 斑马日记2025.10.12
  • Androidify:基于Gemini AI的安卓机器人定制应用
  • 入门指南:使用 Playwright MCP Server 为你的 AI Agent 赋予浏览器自动化能力
  • 实战教程:构建能交互网页的 AI 助手——基于 Playwright MCP 的完整项目
  • popcount 题
  • 2025 年国内卷板机源头厂家最新推荐排行榜:涵盖不锈钢 / 大型 / 锥形 / 数控等多类型设备,助力企业精准采购优质设备
  • mysql5.7 AUTO_INCREMENT 问题
  • Flash游戏浏览器
  • vi/vim 的使用及 CentOS 静态网络配置并链接 Xshell
  • 微信支付
  • 102500410 杜惟真 10月14日作业
  • alpline 构建lnmp
  • 2025 年最新推荐操作台厂家排行榜:覆盖指挥中心 / 控制室 / 中控室 / 监控室 / 调度室场景,为用户选购优质产品提供专业参考
  • NVR设备ONVIF接入平台EasyCVR智慧小区视频监控系统建设方案
  • FPGA开发流程
  • 毕业论文技巧:Word中使用Mathtype对公式自动编号(带章节号)
  • 试验2
  • 浩辰CAD 2025 SP2安装包下载与安装教程
  • 高级程序语言设计第一次作业
  • Java word文档中的图片抽离方法
  • Kerberos认证(Elasticsearch)
  • 2025 年聚氨酯砂浆厂家最新推荐排行榜:聚焦欧洲技术与一站式服务的国内优质企业甄选指南水性聚氨酯砂浆/聚氨酯砂浆自流平厂家推荐
  • 在Anolis OS 8.10 GA上安装和配置VNC系统
  • 钩子(HOOK):改变系统行为的 “隐形抓手”
  • 浅谈InheritableThreadLocal---线程可继承的小书包
  • 2025 年涡街流量计厂家推荐,湖北南控仪表科技有限公司技术创新与行业应用解决方案解析
  • 2025 年超声波流量计厂家推荐,湖北南控仪表科技有限公司产品技术与行业应用解决方案解析
  • ArcGIS 10.2.2 字符串长度为20却仅能输入3个汉字的解决方法
  • 2025 年涡轮流量计厂家推荐:湖北南控仪表科技有限公司设备供应与多行业适配解决方案