首页 > 其他分享 >P3157 (cdq分治思想)

P3157 (cdq分治思想)

时间:2024-02-27 10:15:16浏览次数:26  
标签:sort cmp2 P3157 分治 mid long cdq

难度2

eeeeeeeee比较有意思的一道题目。一开始看到删除,有一个很经典的trick,就是将删除变成插入,倒序处理。然后发现不会做了。然后巨佬lyc说可以用cdq分治,将时间变为第三个关键字,这样也就不用倒序处理了。考虑求出删除某个数后对逆序对个数产生的贡献,在加入了时间戳之后i,j为逆序对的条件变为

所以用两个cdq分治处理即可

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long a,b,c,ans;
}a[100005]; 
long long n,m,x,d[100005],mp[100005],sum=0;
bool cmp1(node x,node y){
	return x.a<y.a;
}
bool cmp2(node x,node y){
	return x.b<y.b;
}
bool cmp3(node x,node y){
	return x.c<y.c;
}
long long lowbit(long long x){
	return x&(-x);
}
void update(long long x,long long ad){
	while(x<=n){
		//cout<<x<<endl;
		d[x]+=ad;
		x+=lowbit(x);
	}
} 
long long getsum(long long x){
	long long ans=0;
	while(x){
		ans+=d[x];
		x-=lowbit(x);
	}
	return ans;
}
void cdq1(long long l,long long r){
	if(l==r) return;
	long long mid=(l+r)>>1;
	cdq1(l,mid);cdq1(mid+1,r);
	sort(a+l,a+mid+1,cmp2);
	sort(a+mid+1,a+r+1,cmp2);
	long long i,j=mid+1;
	for(i=l;i<=mid;i++){
		while(j<=r&&a[i].b>a[j].b){
			update(a[j].c,1);
			j++;
		}
		a[i].ans+=(getsum(m+1)-getsum(a[i].c));
	}
	for(i=mid+1;i<j;i++) update(a[i].c,-1); 
}
void cdq2(long long l,long long r){
	if(l==r) return;
	long long mid=(l+r)>>1;
	cdq2(l,mid);cdq2(mid+1,r);
	sort(a+l,a+mid+1,cmp2);
	sort(a+mid+1,a+r+1,cmp2);
	long long i,j=mid;
	for(i=r;i>=mid+1;i--){
		while(j>=l&&a[i].b<a[j].b){
			update(a[j].c,1);
			j--;
		}
		a[i].ans+=(getsum(m+1)-getsum(a[i].c));
	}
	for(i=mid;i>j;i--) update(a[i].c,-1); 
}
int main(){
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		cin>>x;
		a[i].a=i;
		a[i].b=x;
		a[i].c=m+1;
		mp[x]=i;
	}
	for(long long i=1;i<=m;i++){
		cin>>x;
		a[mp[x]].c=i;
	}
	for(long long i=1;i<=n;i++){
		sum+=(getsum(n)-getsum(a[i].b));
		update(a[i].b,1);
	}
	memset(d,0,sizeof(d));
	cdq1(1,n);
	sort(a+1,a+n+1,cmp1);
	cdq2(1,n); 
	sort(a+1,a+n+1,cmp3);
	for(long long i=1;i<=m;i++){
		cout<<sum<<"\n";
		sum-=a[i].ans;
	}
	
	return 0;
} 

标签:sort,cmp2,P3157,分治,mid,long,cdq
From: https://www.cnblogs.com/wuhupai/p/18036266

相关文章

  • cdq分治个人理解
    \([l,mid]\),跨越\(mid\),\([mid+1,r]\)此时要考虑区间之间的影响。像拦截导弹和三维偏序就是不一样。因为不同区间的影响不一样。然后看代码动态二维偏序,三维偏序,1D/1D动态规划#include<bits/stdc++.h>usingnamespacestd;structnode{ inta,b,c,sum,ans;}b[100005],a[......
  • sol CF587F AC 自动机 根号分治
    注意下文中fail树和trie树的不同。考虑给询问离线,然后差分成\([1,r]-[1,l-1]\)的前缀询问来做。先对于\(s_{1\dotsn}\)建立AC自动机。从左到右扫描询问,当扫描到\(i\)时就对fail树上的子树\(i\)全体\(+1\),使用树状数组维护即可。答案即为\(s_k\)在trie树......
  • 根号分治与莫队算法
    1.根号分治与分块在预处理与询问的复杂度之间寻找平衡的一个算法,通常以根号为分界线。属于智慧的暴力。1.1.根号平衡使用数学不等式对于阈值取一个值,使得复杂度最优。如果有阈值\(B\),若问题有一部分暴力可以\(O(B)\)解决,另一部分可以\(O(\frac{n}{B})\)解决。那么根据基......
  • 自己卷自己的分治 NTT
    考虑如下卷积:\[f_i=\sum\limits_{j=1}^{i-1}f_jf_{i-j}\]仍然可以cdq分治计算。考虑当前在\([l,r]\),希望计算\([l,mid]\)贡献到\([mid+1,r]\)。若\(r-l<l\)那么\([1,r-l]\)都被算出,直接用\([1,r-l]\)和\([l,mid]\)卷两遍即可;否则\(l......
  • 猫树分治
    就是说,对于分治区间\([l,r]\),记\(mid=\lfloor\dfrac{l+r}{2}\rfloor\),对于\([l,mid]\)和\([mid+1,r]\)内的询问继续递归,把跨越两边的询问用左右的信息合并处理。P6240好吃的题目物品\(i\)有体积\(w_i\)和价值\(c_i\),多次询问,对\([l,r]\)做01背包,问体积\(\let......
  • 猫树分治
    就是说,对于分治区间\([l,r]\),记\(mid=\lfloor\dfrac{l+r}{2}\rfloor\),对于\([l,mid]\)和\([mid+1,r]\)内的询问继续递归,把跨越两边的询问用左右的信息合并处理。P6240好吃的题目物品\(i\)有体积\(w_i\)和价值\(c_i\),多次询问,对\([l,r]\)做01背包,问体积\(\let......
  • 线段树分治&cdq分治&整体二分
    preface感觉三种分治算法容易搞混并不容易区分它们使用的场景和题目(虽然有些题目根据性质可以使用多种分治),所以还是要归纳一下线段树分治Part1主要是处理一类带有撤回的问题,也就是一次修改只对一段区间生效(这里的区间指的是时间)即区间修改,单点查询流程大致是把区间修改挂在......
  • #根号分治,分块,dfs序#洛谷 7710 [Ynoi2077] stdmxeypz
    题目传送门分析首先把距离变成深度,用dfs序转成区间问题,考虑分块,散块直接改问题是整块,如果模数比较大,可以以深度为第一维下标差分标记,这样查询时就可以前缀和知道答案如果模数比较小,那么给该块打标记,查询时枚举模数即可,然后块长取1000,模数阈值取300,就能尽量减少时间代码#in......
  • #根号分治,分块#洛谷 5309 [Ynoi2011] 初始化
    题目传送门分析如果\(x\)比较大那么可以暴力修改,\(x\)比较小的话可以用数组打标记查询的时候对于暴力修改的部分可以分块,暴力修改的同时需要给块打标记如果\(x\)比较小的情况,一段区间相当于是中间很多段周期加上前后缀(当然可以直接区间减但是我被卡常了)我调的块长是160......
  • 三维偏序 cdq
    Describe:有\(n\)个元素,第\(i\)个元素有\(a_i、b_i、c_i\)三个属性,设\(f(i)\)表示满足\(a_j\leqa_i\)且\(b_j\leqb_i\)且\(c_j\leqc_i\)的\(j\)的数量。对于\(d\in\left[0,n\right)\),求\(f(i)=d\)的\(i\)的数量。Solution:终于理解CDQ。首先......