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

分治

这是一些可以让你身败名裂的东西。

点分治

有人已经发现了这个恐怖的事实,事实就是我现在看半年前的点分治代码根本看不懂。
好吧,事实上今天上午也没讲点分治。

cdq分治

这个东西吧,我觉得吧,建议别学,过于困难。其实寒假学过,但是没有一个字是自己写的。

前置知识之求逆序对个数

给定 \(n\) 个数,每个数都有一个权值 \(a_i\),求满足 \(i\le j\) 同时 \(a_i\geq a_j\) 的点对个数。

显然,我们只需按顺序遍历一遍,用树状数组或者线段树维护一下在当前点之前,大于等于当前 \(a_i\) 的点个数即可。
至于它为什么对吧,显然你按顺序遍历就一定满足 \(i\neq j\),同时你维护的就是 \(a_j \geq a_i\),所以正确性十分显然啊。

正文

给定 \(n\) 个数,每个数有3个值 \(u_i,v_i,w_i\),求满足 \(u_i\le u_j,v_i\le v_j,w_i\le w_j\)的点对个数。

假如令 \(w_i=1\),那么答案就很显然了,我们只需要把它当成逆序对来算就可以。
同时,我们灵光一现,发现还有一个东西叫做归并排序,同时,归并排序前对 \(u\) 排序,就一定可以保证左半边的 \(u_i\) 值是小于等于右半边的,同时,归并排序本身就可以维护使 \(v\) 有序,因此,我们只需要再用树状数组维护一下 \(w\) 的顺序即可。
所以 cdq分治的思路就很显然了,分三层维护其有序性,首先在外面对 \(u\) 排个序,然后再使用归并排序,通过合并维护 \(v\) 的顺序,最后在归并排序过程中,我们考虑用个什么东西维护最后一维就好了。

#include<bits/stdc++.h>
#define int long long 
#define lowbit(x) (x&(-x))
using namespace std;
int n,k,ans=0;
const int N=2e5+100;
int c[N],sum[N];
struct node {int x,y,z,ans,cnt;friend bool operator <(node a,node b) {if(a.x!=b.x) return a.x<b.x;if(a.y!=b.y) return a.y<b.y;return a.z<b.z;}
}a[N],b[N];
map<node,int>mp;
int read(){int x;cin>>x;return x;}
void insert(int x,int d){if(x==0) return ;while(x<=k){c[x]+=d;x+=lowbit(x);}
}
int ask(int x){int t=0;while(x){t+=c[x];// if(c[x]<0) cerr<<"GGGGG "<<x<<endl;x-=lowbit(x);}	return t;
}
void merge(int l,int r) {if(l==r) return ;int mid=(l+r)>>1;merge(l,mid);merge(mid+1,r);int i=l,j=mid+1,now=l;for(;i<=mid&&j<=r;now++) {if(a[i].y<=a[j].y) {b[now]=a[i];insert(a[i].z,a[i].cnt);i++;}else {b[now]=a[j];b[now].ans+=ask(a[j].z);j++;}} for(;i<=mid;) {b[now]=a[i];insert(a[i].z,a[i].cnt);i++,now++;}for(;j<=r;j++,now++) {b[now]=a[j];b[now].ans+=ask(a[j].z);}for(int i=l;i<=mid;i++) {insert(a[i].z,-a[i].cnt);}for(int i=l;i<=r;i++) a[i]=b[i];return ;
}
signed main() {freopen("flower.in","r",stdin);freopen("flower.out","w",stdout);memset(c,0,sizeof(c));n=read();k=read();int x,y,z;for(int i=1;i<=n;i++) {x=read();y=read();z=read();mp[{x,y,z,0,0}]++;}int cnt=0;for(auto y:mp) {cnt++;node t=y.first;t.cnt=y.second;a[cnt]=t;a[cnt].ans=0;}sort(a+1,a+1+cnt);merge(1,cnt);for(int i=1;i<=cnt;i++) {a[i].ans=a[i].ans+a[i].cnt-1ll;sum[a[i].ans]+=a[i].cnt;}for(int i=0;i<n;i++) {cout<<sum[i]<<"\n";}return 0;
}

线段树分治

容易注意到,三个月之前我开过这一篇总结,但是那个摘要里面的只有标题至今都还是只有标题。

分治

就是,你考虑,对于一些求什么什么区间的问题,我们就把这个问题递归下去做,然后做一做左区间的,做一做右区间的,然后合并一下,就做完了。

例题

消失之物

容易想到,这题可以退背包来写,但是我们今天学分治,所以我们考虑分治,你考虑你每次往下走的时候,都把另一个区间的点给加进来,然后你走到最下面叶子的时候,一定就只有这个点还没有被加进来,然后直接统计答案就好。
然后考虑时间复杂度,显然,每个点最多会被加入 \(\log n\) 次,所以总时间复杂度 \(O(nmlogn)\) 可以接受。

http://www.hskmm.com/?act=detail&tid=27284

相关文章:

  • qwen3:0.6b模型的基本参数存在的价值应用场景分析
  • Gitee Insight领航研发效能工具市场:国产化与智能化双轮驱动下的技术突围
  • 【大数据】AI就业影响数据可视化分析系统 计算机毕业设计项目 Anaconda+Django+Spark+Hadoop环境调整 附源码+文档+讲解
  • 2026 航空航天、智能感知与控制国际学术会议
  • Trae 或 vscode无法在vue文件中自动跳转解决
  • 实用指南:小白也能学会的大模型构建:DeepSeek实战教程+代码解析
  • 安徽京准:NTP网络时间服务器技术应用方案
  • 2025工矿灯厂家TOP5推荐:高光效与耐用性深度评测
  • ​​无源探头与高压差分探头的技术比较与应用选择​​
  • PKDV5351高压差分探头在氢燃料电池堆电压均衡监测中的实战应用案例
  • 2025秋_8
  • react的依赖项数组 - 实践
  • 25年人教版一年级资料汇总!(一年级数学上册典型练习题)(解决问题共150道)电子版可打印(共6页)!可打印可下载
  • 第十天
  • VSCode万能Debug任何执行python文档命令的详细教程
  • 专业的用户反馈管理分析工具,能帮企业节省多少开支?
  • Kotlin-微服务实用指南-全-
  • 外设知识学习笔记
  • “你好BOE”再度携非遗与当代设计亮相米兰 以科技之力向世界展现东方美学
  • 个人微信机器人开发指南!API接口轻松上手
  • AI大模型项目三连炸:多模态监控平台+RAG推荐系统+智能体智驾系统
  • 10.9
  • PWN手的成长之路-13-jarvisoj_level0
  • 计算机毕设 java 基于 Java 的题库管理强大的系统 基于 SSM+JavaWeb 的题库全流程管理平台 Java+MySQL 的题库服务一体化系统
  • 微信最新协议API上线!个人号快速接入
  • Firefox火狐浏览器插件下载、安装路径、备份插件、手动安装插件
  • 2025.10.9午后有感
  • Firefox火狐浏览器插件下载、安装路径
  • 实用指南:PyTest框架学习
  • PWN手成长之路-12-pwn1_sctf_2016