三维偏序问题【NOI2018模拟3.28】Subset

2024-05-29 02:48

本文主要是介绍三维偏序问题【NOI2018模拟3.28】Subset,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

三维偏序问题请看下面

Description

这里写图片描述

Input

第一行一个正整数 n
第二行 n 个数字,表示排列 a i
第三行 n 个数字,表示排列 b i
第四行 n 个数字,表示排列 c i

Output

一行一个整数,表示答案

Sample Input

8
1 7 5 3 4 8 2 6
3 1 2 7 4 8 5 6
6 3 4 5 8 2 1 7

Sample Output

42

Data Constraint

对于 10% 的数据满足 n ≤ 20
对于 30% 的数据满足 n ≤ 2000
另有 20% 的数据满足 a i = b i
对于 100% 的数据满足 n ≤ 100000

Solution

考虑S只包括了包含了三元组的位置,那么|S|<=3
若|S|=1,则答案为n
若|S|=2,则答案为 C2n 减去不合法的
在这种情况下,不合法的只有当某一列三个数都小于另一列,即这一列是没用的。
这个就是三维偏序问题了,具体怎么做,下面再说。
|S|=3,则答案为 C3n 减去不合法的
不合法的有三个最大值都集中在一列或两列
集中在一列,和上面的一样,三维偏序问题
集中在两列,枚举是哪两个数在同一列,然后变成二维偏序问题。

三维偏序问题

也可以理解为三维数点问题,就以这题中数一个点三维都小于另一个点为例。
二维偏序问题是很简单的:
一维排序,然后第二位用树状数组维护一下。
三维偏序也可以这么做,把树状数组变成树状数组套线段树,也不麻烦。
也可以考虑第二维分治,第三维用树状数组。
具体来说,先按照一维排序,在分治时分成两部分,只考虑左半边对右半边的贡献。
这时,可以左半边和右半边分别按第二维排序,因为保证了第一位左边比右边小。
然后只剩一维了,用树状数组维护一下。
递归做到底层就行了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 101000
#define ll long long
#define lowbit(x) (x&(-x))
using namespace std;
int n,t[N*2];
ll ans,A[N],B=0,X=0;
struct node{int a,b,c,z;
}a[N];
bool cnt1(node a,node b){return a.a<b.a;}
bool cnt2(node a,node b){return a.b<b.b;}
void ins(int x,int y)
{for(;x<=n;x+=lowbit(x)) t[x]+=y;
}
int get(int x)
{int ans=0;for(;x;x-=lowbit(x)) ans+=t[x];return ans;
}
void divide(int l,int r)
{if(l==r) return;int m=(l+r)/2;divide(l,m);divide(m+1,r);sort(a+l,a+r+1,cnt1);sort(a+l,a+m+1,cnt2);sort(a+m+1,a+r+1,cnt2);int j=m+1;fo(i,l,m){ins(a[i].c,1);while(j<=r&&a[j].b<a[i].b) j++;while(j<=r&&a[j].b<a[i+1].b){ll c=get(a[j].c);ans-=c;A[a[j].z]+=c;j++;}}while(j<=r){ll c=get(a[j].c);ans-=c;A[a[j].z]+=c;j++;}fo(i,l,m) ins(a[i].c,-1);
}
void calc()
{memset(t,0,sizeof(t));sort(a+1,a+n+1,cnt1);fo(i,1,n){A[a[i].z]+=get(a[i].b);ins(a[i].b,1);}
}
int main()
{freopen("subset.in","r",stdin);freopen("subset.out","w",stdout);scanf("%d",&n);fo(i,1,n) scanf("%d",&a[i].a);fo(i,1,n) scanf("%d",&a[i].b);fo(i,1,n) scanf("%d",&a[i].c),a[i].z=i;ans=n;ans=ans+ans*(ans-1)/2+ans*(ans-1)*(ans-2)/3/2;sort(a+1,a+n+1,cnt1);divide(1,n);fo(i,1,n) X+=A[i]*(A[i]-1)/2;ans-=X;memset(A,0,sizeof(A));calc();fo(i,1,n) B+=A[i]*(A[i]-1)/2;fo(i,1,n) swap(a[i].b,a[i].c),A[i]=0;calc();fo(i,1,n) B+=A[i]*(A[i]-1)/2;fo(i,1,n) swap(a[i].a,a[i].c),A[i]=0;calc();fo(i,1,n) B+=A[i]*(A[i]-1)/2;ans=ans-B+3*X;printf("%lld\n",ans);
}

这篇关于三维偏序问题【NOI2018模拟3.28】Subset的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012428

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模

SpringBoot+Redis防止接口重复提交问题

《SpringBoot+Redis防止接口重复提交问题》:本文主要介绍SpringBoot+Redis防止接口重复提交问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录前言实现思路代码示例测试总结前言在项目的使用使用过程中,经常会出现某些操作在短时间内频繁提交。例