首页 > 其他分享 >CDQ分治学习笔记

CDQ分治学习笔记

时间:2024-09-29 21:35:31浏览次数:6  
标签:偏序 p1 int 分治 mid 笔记 cdq CDQ

CDQ分治学习笔记

k维偏序问题

求满足条件的二元组个数

题意描述

每个元素有 \(k\) 个值,要求满足(以 \(k=2\) 为例 ) \(a_j\le a_i,b_j\le b_i\) 的点对个数 。

分析

这实际上就是我们熟悉的逆序对问题,回忆一下我们是怎么处理的,首先来说,当 \(a,b\) 其中一个的含义是下标的时候可以直接树状数组,因为这个时候第一维已经是有序的了。

然后,对于更一般的情况,可以用归并,这其实就是 CDQ 思想的体现,将待处理的区间不断地分为小区间,直到区间长度满足可以比较为止,这时候统计答案 并且 排序,然后再递归回大区间解决问题。

思考一下,我们实际上是在消除了第一维 \(b_i,b_j\) 的影响的条件下,对 \(a_i,a_j\) 做进一步的比较。

处理到后面的维度的时候再排序可能会改变已经排序完毕的前面的维度,但是很容易地就能够想到,我们只会对于每个元素统计它左边的所有符合条件的元素,所以这不会对答案产生什么影响。

拓展

那么如何解决三维偏序 \(a_j\le a_i,b_j\le b_i,c_j\le c_i\) 呢?仍然应用上面的思想,考虑先消除 \(a\) 这一维度带来的影响,于是我们首先按照 \(a\) 的大小进行 CDQ (或者说是排序);然后再对 \(b\) 的大小进行 CDQ ;然后再对 \(c\) 的大小进行 CDQ ,这个时候我们就可以顺便开始统计答案了。

更加取巧的写法来说的话,第一维实际上可以换成一个 Sort ,最后一维可以直接用树状数组进行统计 ,那么仅仅对于三维偏序来说的话,我们可以只用写一个 CDQ 。

同理,由于在经典的 “逆序对” 问题中,第一维下标是已经有序了的,那么我们可以直接在第二维(或者说最后一维)使用一次 CDQ ,或者直接使用树状数组就把答案统计出来。

例题 三维偏序

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
	T f=1;x=0;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	x*=f;
}

const int N=2e5+10;
int c[N],n,recn,k;
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int v)
{
	for(;x<=k;x+=lowbit(x))c[x]+=v;
}
inline int query(int x)
{
	int ans=0;
	for(;x;x-=lowbit(x))ans+=c[x];
	return ans;
}
int f[N],ans[N];
struct T
{
	int a,b,c,idx,num=1;
}q[N],tmp[N],tmpt[N];
inline bool cmp(T x,T y)
{
	return x.a!=y.a?x.a<y.a:(x.b!=y.b?x.b<y.b:x.c<y.c);
}
inline void debug()
{
	for(register int i=1;i<=n;++i)
		printf("%d %d %d %d %d\n",q[i].a,q[i].b,q[i].c,q[i].num,q[i].idx);
}
inline void cdq(int l,int r)
{
	if(l==r)return ;
	int mid=l+r>>1;
	cdq(l,mid),cdq(mid+1,r);
	int cnt=l-1,p1=l,p2=mid+1;
	while(p1<=mid&&p2<=r)
	{
		if(q[p1].b<=q[p2].b)
		{
			tmpt[++cnt]=q[p1];
			add(q[p1].c,q[p1].num);
			p1++;
		}
		else
		{
			tmpt[++cnt]=q[p2];
			f[q[p2].idx]+=query(q[p2].c);
			p2++;
		}
	}
	while(p1<=mid)
	{		
		tmpt[++cnt]=q[p1];
		add(q[p1].c,q[p1].num);
		p1++;
	}	
	while(p2<=r)
	{
		tmpt[++cnt]=q[p2];
		f[q[p2].idx]+=query(q[p2].c);
		p2++;	
	}
	for(register int i=l;i<=mid;++i)add(q[i].c,-q[i].num); 
	for(register int i=l;i<=r;++i)q[i]=tmpt[i];
}
inline void pre()	
{
	cin>>n>>k;
	recn=n;
	for(register int i=1;i<=n;++i)
		re(tmp[i].a),re(tmp[i].b),re(tmp[i].c);
	sort(tmp+1,tmp+n+1,cmp);
	int tmpn=1;
	for(register int i=1;i<=n;++i)
	{
		if(tmp[i].a==tmp[i+1].a&&tmp[i].b==tmp[i+1].b&&tmp[i].c==tmp[i+1].c)q[tmpn].num++;
		else
		{
			q[tmpn].a=tmp[i].a,q[tmpn].b=tmp[i].b,q[tmpn].c=tmp[i].c;
			q[tmpn].idx=tmpn,f[tmpn]=q[tmpn].num-1;
			tmpn++;
		}
	}
	n=tmpn-1;
//	debug(); 
}
inline void solve()
{
	cdq(1,n);
	for(register int i=1;i<=n;++i)ans[f[q[i].idx]]+=q[i].num;//应该访问的是idx,因为上面加的时候也是对下标idx进行操作 
	for(register int d=0;d<recn;++d)
		printf("%d\n",ans[d]);
}
int main()
{
	pre();
	solve(); 
	return 0;
} 
/*
5 2
1 2 2
2 1 1
1 2 1
2 2 1
2 1 1

2 2 0 1 0
*/

这个题写了还是有挺久的,主要是要注意去重的问题,还要注意访问的下标。

总结

对于 K维偏序 的问题来说,我们要做的就是一维一维地消除其对答案统计的影响,直到可以直接统计答案为止。

其中:

第一维可以换成 sort。

最后一维可以放在倒数第二维的时候用树状数组顺便统计。

具体嵌套流程如下 :

void cdq(int l,int r,int x)//x代表维度
{
    if(l==r)return ;
    int mid=l+r>>1;
    if(x==k)
    {
        cdq(l,mid,x),cdq(mid+1,r,x);
        //sort the array and meanwhile calculate the answer
        return ;
    }
    else
    {
         cdq(l,mid,x),cdq(mid+1,r,x);
		//sort the array and do some other work
    	cdq(l,r,x+1)
    }
}
int main()
{
    input();
    cdq(1,n,1);
    output();
}

带有偏序性质的统计答案问题

问题

P5094 Moofest G

分析

题目要求所有 \(\sum\max(v_i,v_j)\times dis(x_i,x_j)\) ,其中两个值实际上都带有偏序的性质。

比如 \(\max\) 就与大小有关,如果一个序列按照 \(v\) 有序,那对于每一个元素我们就只用统计它左边的元素的贡献了;

如果要让一个序列按照坐标大小 \(x\) 有序,那我们就可以在归并 \(x\) 的过程中同时计算答案了。

所以算法流程就很明显了,我们先对于第一维 \(v\) 进行归并(或者直接sort),然后再对第二维进行归并,同时统计答案即可。

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;
	int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
int n;
const int N=5e4+10;
struct cow
{
	int v,x;
}a[N],tmp[N];
inline bool cmp(cow a,cow b)
{
	return a.v!=b.v?a.v<b.v:a.x<b.x;
}
inline bool cmp1(cow a,cow b)
{
	return a.x<b.x;
}
long long ans=0;
int sumx[N];
inline void cdq(int l,int r)
{
	if(l==r)return;
	int mid=l+r>>1;
	cdq(l,mid),cdq(mid+1,r);
	int p1=l,p2=mid+1;
	int cnt=l-1;sumx[cnt]=0;
	for(int i=l;i<=mid;++i)sumx[i]=sumx[i-1]+a[i].x;
	while(p1<=mid&&p2<=r)
	{
		if(a[p1].x>a[p2].x)
		{
			tmp[++cnt]=a[p2];
			ans+=a[p2].v*((p1-l)*a[p2].x-sumx[p1-1]  +  sumx[mid]-sumx[p1-1]-(mid-p1+1)*a[p2].x);
			p2++;
		}
		else
			tmp[++cnt]=a[p1++];
	} 
	while(p1<=mid)tmp[++cnt]=a[p1++];
	while(p2<=r)
	{
		tmp[++cnt]=a[p2];
		ans+=a[p2].v*((mid-l+1)*a[p2].x-sumx[mid]);
		p2++;
	}
	for(int i=l;i<=r;++i)a[i]=tmp[i];
} 
inline void pre()
{
	cin>>n;
	for(register int i=1;i<=n;i++)re(a[i].v),re(a[i].x);
	sort(a+1,a+n+1,cmp); 
}
signed main()
{
	pre();
	cdq(1,n);
	cout<<ans;
	return 0;
}

CDQ优化DP转移

这里是指把 DP 的下标当做其中的一维,但是我还没学到那个程度,所以暂时挖个坑,以后来填。

标签:偏序,p1,int,分治,mid,笔记,cdq,CDQ
From: https://www.cnblogs.com/Hanggoash/p/18440789

相关文章

  • .NET|--WPF|--笔记合集|--依赖项属性|--5.附加属性
    前言附加属性是一个ExtensibleApplicationMarkupLanguage(XAML)概念。附加属性允许为派生自DependencyObject的任何XAML元素设置额外的属性/值对,即使该元素未在其对象模型中定义这些额外的属性。额外的属性可进行全局访问。附加属性通常定义为没有常规属性包装......
  • 树分治
    点分治点分治适合处理大规模的树上路径信息问题。本质思想是选择一点作为分治中心,将原问题划分为几个相同的子树上的问题,进行递归解决。常见的用于统计树上有关路径的信息。假设当前选定根节点为\(rt\),则符合条件的路径必然是以下两种之一:经过\(rt\)或一段在\(rt\)上;在......
  • Windows下绿色安装PostgreSQL笔记
    介绍PostgreSQL,Postgres,以下简称为PG,是一款关系型数据库,本地安装支持两种方式,一键安装和绿色解压安装两种方式下载、解压安装版:https://www.enterprisedb.com/downloads/postgres-postgresql-downloads绿色解压版:https://www.enterprisedb.com/download-postgres......
  • prometheus学习笔记之alertmanager告警配置
    一、安装alertmanager项目地址:https://github.com/prometheus/alertmanager帮助文档:https://prometheus.io/docs/alerting/latest/alertmanager/配置文档:https://prometheus.io/docs/alerting/latest/configuration/wgethttps://github.com/prometheus/alertmanager/releas......
  • Pytorch学习笔记--搭建神经网络以及Sequential的使用
    首先,搭建一个如下图所示的神经网络: 分析图片,inputs输入图片的inchannels=3,尺寸是32*32,经过kernel_size=5的卷积操作后out_channels=32,尺寸32*32,套用下方公式可算出padding=2(默认dilation=1,stride=1):self.conv1=Conv2d(3,32,5,padding=2)  之后再进行池化操作Max-poolin......
  • 扫描线-学习笔记
    扫描线-学习笔记引言:扫描线算法用于解决给出多个矩形组成的图形求解其面积、周长等问题。时间复杂度常见为\(O(n\log_2^n)\)级别,空间复杂度略大于\(O(n)\),属于线段树的一种运用。一、求面积题目:P5490【模板】扫描线&矩形面积并求\(n\)个四边平行于坐标轴的矩形的面积......
  • MySQL数据库初级学习笔记---第一章-数据库概述
    第一章-数据库概述聊聊数据库数据库是一门独立的学科,只要是做软件开发的,数据库都要学。数据库(电子化的文件柜)是“按照数据结构来组织、存储和管理数据的仓库”。是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合。它的存储空间很大,可以存放百万条......
  • 【Qt笔记】QFrame控件详解
    目录引言一、QFrame的基本特性二、QFrame的常用方法2.1边框形状(FrameShape)2.2阴影样式(FrameShadow)2.3线条宽度(LineWidth)2.4 样式表(styleSheet)三、QFrame的应用场景四、应用示例 4.1代码4.2实现效果4.3代码解析与注意事项代码解析注意事项结语......
  • 小迪安全课程笔记-2024-十九-
    小迪安全课程笔记2024(十九)P53:第53天:XSS跨站&SVG&PDF&Flash&MXSS&UXSS&配合上传&文件添加脚本-逆风微笑的代码狗-BV1Mx4y1q7Ny好看看今天的内容啊,今天呢是这个继续讲这个夸张,那呃上节课呢已经讲了一下夸张的啊,今天呢继续讲啊,在今天讲的讲30个夸张啊,三四个其实是五个,但是有两......
  • 小迪安全课程笔记-2024-二十四-
    小迪安全课程笔记2024(二十四)P65:第66天:Java安全&SPEL表达式&SSTI模版注入&XXE&JDBC&MyBatis注入-逆风微笑的代码狗-BV1Mx4y1q7Ny没有挂机上课了啊,今天讲一下这个60由天啊,这个java安全,这个java安全的这一个系列的课程呢,大概,五六次直播吧对吧,嗯前面因为这些漏洞呢有些是讲过......