首页 > 其他分享 >CDQ分治

CDQ分治

时间：2024-08-13 10:27:40浏览次数：15  
标签：sort ++ 分治 mid long int CDQ define

image

P3810 【模板】三维偏序（陌上花开）

CDQ模板题，考虑先按\(a\)排序，减掉一位，然后再\(CDQ\)分治一维，用树状数组维护最后一维
还有本题特殊,去重操作不要忘记

点击查看代码 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pb push_back
using namespace std;
const int N = 2E5+5;
int n,k;
struct Bit
{
	int c[N];
	int lowbit(int x){return (x&(-x));}
	void add(int x,int val)
	{
		while(x<=k)
		{
			c[x]+=val;
			x+=lowbit(x);
		}
	}
	int ask(int x)
	{
		int ans=0;
		while(x)
		{
			ans+=c[x];
			x-=lowbit(x);
		}
		return ans;
	}
}T;
struct ac
{
	int a,b,c,w,ans;
}a[N],b[N];
int ans[N];
bool cmp(ac a,ac b)
{
	if(a.a==b.a)
	{
		if(a.b==b.b)
			return a.c<b.c;
		return a.b<b.b;
	}
	return a.a<b.a;
}
bool cmpy(ac a,ac b)
{
	if(a.b==b.b)
	{
		return a.c<b.c;
	}
	return a.b<b.b;
}
void cdq(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq(l,mid);cdq(mid+1,r);
	sort(b+l,b+mid+1,cmpy);sort(b+mid+1,b+r+1,cmpy);
	int i=mid+1,j=l;
	for(;i<=r;i++)
	{
		while(b[j].b<=b[i].b&&j<=mid)
			T.add(b[j].c,b[j].w),j++;
		b[i].ans+=T.ask(b[i].c);
	}
	for(int i=l;i<j;i++)
		T.add(b[i].c,-b[i].w);
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].a>>a[i].b>>a[i].c;
	}
	sort(a+1,a+1+n,cmp);
	int cnt=0,num=0;
	for(int i=1;i<=n;i++)
	{
		cnt++;
		if(a[i].a!=a[i+1].a||a[i].b!=a[i+1].b||a[i].c!=a[i+1].c)
			b[++num]=a[i],b[num].w=cnt,cnt=0;
	}
	cdq(1,num);
	for(int i=1;i<=num;i++)
	{
		ans[b[i].ans+b[i].w-1]+=b[i].w;
	}
	for(int i=0;i<n;i++)cout<<ans[i]<<endl;
	return 0;
}

关于优化,每次排个序太慢了
我们可以用归并排序，具体的就是把\(CDQ\)中两个排序去了，然后新开一个数组备用，然后调用\(merge\)函数,传\(5\)个参\(merge(l_1,r_1,l_2,r_2,num[])\)
就是把两个排过序的数组合并为一个排过序的数组

点击查看代码 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pb push_back
using namespace std;
const int N = 2E5+5;
int n,k;
struct Bit
{
    int c[N];
    int lowbit(int x){return (x&(-x));}
    void add(int x,int val)
    {
        while(x<=k)
        {
            c[x]+=val;
            x+=lowbit(x);
        }
    }
    int ask(int x)
    {
        int ans=0;
        while(x)
        {
            ans+=c[x];
            x-=lowbit(x);
        }
        return ans;
    }
}T;
struct ac
{
    int a,b,c,w,ans;
    friend bool operator < (const ac& a,const ac& b)
    {
        if(a.b==b.b)
        {
            return a.c<b.c;
        }
        return a.b<b.b;
    }
}a[N],b[N],q[N];
int ans[N];
bool cmp(ac a,ac b)
{
    if(a.a==b.a)
    {
        if(a.b==b.b)
            return a.c<b.c;
        return a.b<b.b;
    }
    return a.a<b.a;
}
bool cmpy(ac a,ac b)
{
    if(a.b==b.b)
    {
        return a.c<b.c;
    }
    return a.b<b.b;
}
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    // sort(b+l,b+mid+1,cmpy);sort(b+mid+1,b+r+1,cmpy);
    int i=mid+1,j=l;
    for(;i<=r;i++)
    {
        while(b[j].b<=b[i].b&&j<=mid)
            T.add(b[j].c,b[j].w),j++;
        b[i].ans+=T.ask(b[i].c);
    }

    for(int i=l;i<j;i++)
        T.add(b[i].c,-b[i].w);
     merge(b+l,b+mid+1,b+mid+1,b+r+1,q+l);
     for(int i=l;i<=r;i++)b[i]=q[i];
}
int main()
{
    speed();
    // freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].a>>a[i].b>>a[i].c;
    }
    sort(a+1,a+1+n,cmp);
    int cnt=0,num=0;
    for(int i=1;i<=n;i++)
    {
        cnt++;
        if(a[i].a!=a[i+1].a||a[i].b!=a[i+1].b||a[i].c!=a[i+1].c)
            b[++num]=a[i],b[num].w=cnt,cnt=0;
    }
    for(int i=1;i<=num;i++)q[i]=b[i];
    cdq(1,num);
    for(int i=1;i<=num;i++)
    {
        ans[b[i].ans+b[i].w-1]+=b[i].w;
    }
    for(int i=0;i<n;i++)cout<<ans[i]<<endl;
    return 0;
}

P4390 [BalkanOI2007] Mokia 摩基亚

其实也是三维偏序，第一维时间，二三维\(x,y\)

点击查看代码 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
// #pragma GCC optimize(3)
using namespace std;
const int N=2e6+6; 
int n,ans[N],w;
struct ac
{
	int tim,x,y,w,id;
}q[N];
bool cmp(ac a,ac b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
bool cmptim(ac a,ac b)
{
	return a.tim<b.tim;
}
struct Bit
{
	int c[N];
	int lowbit(int x){return x&-x;}
	void add(int x,int v)
	{
		while(x<=w)
		{
			c[x]+=v;
			x+=lowbit(x);
		}
	}
	int query(int x)
	{
		int ans=0;
		while(x)
		{
			ans+=c[x];
			x-=lowbit(x);
		}
		return ans;
	}
}T;
void cdq(int l,int r)
{
	if(l==r)return;
	// cout<<l<<" "<<r<<endl;
	int mid=(l+r)>>1;
	cdq(l,mid);cdq(mid+1,r);
	sort(q+l,q+mid+1,cmp);sort(q+mid+1,q+r+1,cmp);
	int i=mid+1,j=l;
	for(;i<=r;i++)
	{
		// cout<<i<<endl;
		while(q[j].x<=q[i].x&&j<=mid)
		{
			if(q[j].id==0)T.add(q[j].y,q[j].w);
			j++;
			// cout<<j<<" "<<mid<<endl;
		}
		if(q[i].id==1)q[i].w+=T.query(q[i].y);
	}
	for(int i=l;i<j;i++)
	{
		if(q[i].id==0)T.add(q[i].y,-q[i].w);
	}
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	int op,x,y,a,b;
	while(1)
	{
		cin>>op;
		if(!op)
		{
			cin>>w;
			w++;
		}else if(op==1)
		{
			cin>>x>>y>>a;
			++n;x++;y++;
			q[n]={n,x,y,a,0};
		}else if(op==2)
		{
			cin>>x>>y>>a>>b;
			a++;b++;
			q[++n]={n,x,y,0,1};
			q[++n]={n,a,b,0,1};
			q[++n]={n,x,b,0,1};
			q[++n]={n,a,y,0,1};
			// sort(q+1,q+1+n,cmp);
		}else if(op==3)break;
	}
	// cout<<"*****"<<endl;
	cdq(1,n);
	sort(q+1,q+1+n,cmptim);
	for(int i=1;i<=n;i++)
	{
		if(q[i].id)
		{
			cout<<q[i].w+q[i+1].w-q[i+2].w-q[i+3].w<<endl;
			i+=3;
		}
	}
	return 0;
}

P4169 [Violet] 天使玩偶/SJY摆棋子

我们可以转换为求四次\(cdq\),使点翻转分别在左上角左下角右上角右下角即可
注意判断\(l>r\)以及树状数组查询到\(0\)的情况

点击查看代码 
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
using namespace std;
const int N =1e6+5;
int n,m,ans[N];
int lx,rx,ly,ry;
struct ac
{
	int x,y,t;bool f;
	bool operator < (const ac& A)const
	{
		return x<=A.x;
	}
}a[N],p[N],q[N];
bool cmp(ac a,ac b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
struct Bit
{
	int c[N];
	int lowbit(int x){return x&-x;}
	inline void clear(int x)
	{
		if(!x)return;
		while(x<=ly)
		{
			if(c[x])c[x]=0;
			else break;
			x+=lowbit(x);
		}			
	}
	inline void add(int x,int v)
	{
		if(!x)
		{
			// c[0]=max(c[0],val);
			return;
		}
		while(x<=ly)
		{
			c[x]=max(v,c[x]);
			x+=lowbit(x);
		}
	}
	inline int query(int x)
	{
		if(!x)return 0;
		int ans=0;
		while(x)
		{
			// cout<<x<<endl;
			ans=max(c[x],ans);
			x-=lowbit(x);
		}
		return ans;
	}
}T;
inline void cdq(int l,int r)
{
	if(l>r)return;
	if(l==r)return;
	// cout<<l<<" "<<r<<endl;
	int mid=(l+r)>>1;
	cdq(l,mid);cdq(mid+1,r);
	// sort(p+l,p+1+mid,cmp);sort(p+mid+1,p+r,cmp);
	int i=mid+1,j=l;
	for(;i<=r;i++)
	{
		if(p[i].f)continue;
		while(p[j].x<=p[i].x&&j<=mid)
		{
			// cout<<j<<endl;
			if(p[j].f)T.add(p[j].y,p[j].y+p[j].x);
			j++;
		}
		int tmp=T.query(p[i].y);
		if(tmp)ans[p[i].t]=min(ans[p[i].t],p[i].x+p[i].y-tmp);
	}
	for(int i=l;i<j;i++)
		if(p[i].f)T.clear(p[i].y);

	merge(p+l,p+1+mid,p+mid+1,p+r+1,q+l);

	for (int i = l; i <= r; ++i) p[i] = q[i];
	// for(int i=l;i<=r;i++)
}
inline void Delete()
{
	rx=ry=m=0;
	for(int i=1;i<=n;i++)
	{
		if(!p[i].f)rx=max(rx,p[i].x),ry=max(ry,p[i].y);
	}
	for(int i=1;i<=n;i++)
		if(p[i].x<=rx&&p[i].y<=ry)q[++m]=p[i];
	for(int i=1;i<=m;i++)p[i]=q[i];
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>m;
	memset(ans,0x3f,sizeof ans);
	int k,x,y;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;x++;y++;
		a[i]={x,y,i,1};
		lx=max(lx,x);ly=max(ly,y);
	}
	while(m--)
	{
		cin>>k>>x>>y;x++;y++;
		++n;a[n]={x,y,n,bool(k&1)};
		lx=max(lx,x);ly=max(ly,y);
	}
	++lx;++ly;
	for(int i=1;i<=n;i++)p[i]=a[i];
	Delete();cdq(1,m);
	for(int i=1;i<=n;i++)
		p[i]=a[i],p[i].x=lx-p[i].x;
	Delete();cdq(1,m);
	for(int i=1;i<=n;i++)
		p[i]=a[i],p[i].y=ly-p[i].y;
	Delete();cdq(1,m);
	for(int i=1;i<=n;i++)
		p[i]=a[i],p[i].x=lx-p[i].x,p[i].y=ly-p[i].y;
	Delete();cdq(1,m);
	for(int i=1;i<=n;i++)
		if(!a[i].f)cout<<ans[i]<<endl;
	return 0;
}

标签：sort,++,分治,mid,long,int,CDQ,define
From： https://www.cnblogs.com/wlesq/p/18356302

相关文章

  • CDQ分治
    CDQ分治的思想最早由IOI2008金牌得主陈丹琦在高中时整理并总结，它也因此得名。CDQ分治的思想常用于离线解决点对之间的问题，最经典的如三维偏序。解决这类问题的过程为：将序列$(l,r)$分为。递归处理序列$(l,mid)$和$(mid+1,r)$中的答案。设计算法处理......
  • cdq分治总结
    \(cdq\)分治是一种离线分治算法，可以将动态问题改变为静态问题，不适用于强制在线。其实现时通常将需要进行的操作存进一个结构体，然后对这些操作进行分治。打\(cdq\)分治时一个直观的感受就是很好想思路，但就是不知道怎么打。。。它一共有三个需要干的1找到范围中点\(mid\)......
  • 【CDQ分治】三元环
    三元环HDU-7439思路考虑\(3\)个点的有向图，要么成环，要么有一个点入度为\(2\)，假设第个点的入度为\(d_i\)，答案为\(C_n^3-\sum\limits_{i=1}^nC_{d_i}^2\)。根据题目关系，\(i\rightarrowj\)当且仅当\(i<j\and\f_i<f_j\and\g_i<g_j\)，否则就是\(j\rightarrowi......
  • 【CDQ分治】【模板】三维偏序（陌上花开）
    P3810【模板】三维偏序（陌上花开）-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;template<typenameT>structBIT{#ifndeflowbit#definelowbit(x)(x&(-x));#endifintn;vector<T&......
  • 【CDQ分治】[P5094 [USACO04OPEN] MooFest G 加强版
    P5094[USACO04OPEN]MooFestG加强版-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;vecto......
  • [算法] 一些分治
    普通分治其实没啥，每次只计算跨越分治中心的区间的贡献，剩下的递归到左右两边进行分治；时间复杂度：分治树高度为$\Theta(\logn)$，乘上其他操作的复杂度即可；例题一：现在有一个$n$阶排列$a$，计算：\[\sum^{n}_{i=1}\sum^{n}_{j=i}\min(a_i,a_{i+1},...,a_j)\]......
  • 20240806：点分治，虚树选做
    POJ-1741Tree题意：给定一棵树，求多少无序对\((u,v)\)满足\(\text{dist}(u,v)\lek\)。对于树上的路径进行分类：经过根；不经过根。第二类路径点可以通过递归子树求出。对于经过根的路径，可以一遍dfs求出每个点到根的距离\(\text{dis}(u)\)。问题转化为求\(\text{dis}(u)......
  • CDQ分治
    CDQ分治CDQ分治是一种思想而不是具体的算法，与动态规划类似。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：解决和点对有关的问题。1D动态规划的优化与转移。通过CDQ分治，将一些动态问题转化为静态问题。解决和点对有关的问题这类问题多数类似于「给定一......
  • 根号分治（待补充）
    最近有根号分治的题都没那么熟悉，想到了方向感也很差，故写一点题解。LCA查询看到题目中的条件\(\sumk\le10^5\)说明\(k\leS\)的个数很多，\(S\lek\)的个数很少。那么对于前者，考虑一开始最朴素的\(O(S^2)\)的暴力，枚举集合中的两个点，求\(LCA\)总时间复杂度\(O(\fra......
  • 「Day 2—贪心问题&分治&前缀和」
    贪心问题定义顾名思义，越贪越好。。。习题P1094[NOIP2007普及组]纪念品分组思路简单来说：最少的+最多的，利用双指针。代码#include<algorithm>#include<iostream>usingnamespacestd;intw,n;intp[30005];intmain(){cin>>w;cin>>n;for(inti=1;i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99