【题意概述】

给出三个n的排列,求有多少个数对在三个排列中顺序相同

【题解】

考虑用补集转化的方法,答案为总对数-不满足的对数

一对数不满足条件,当且仅当这对数在两个排列中顺序相同,在另一个排列中的顺序不同。

统计两两之间不满足偏序条件的数对的个数,那么每对数都被统计了两次

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn=200010;
int n,a[4][maxn],b[maxn],t[maxn];
LL ans,tmp;
void read(int &k){
k=0; int f=1; char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
k*=f;
}
void add(int x){for(;x<=n;x+=(x&-x)) t[x]++;}
int query(int x){int ret=0; for(;x>0;x-=(x&-x)) ret+=t[x]; return ret;}
int main(){
read(n);
for (int j=1;j<=3;j++)
for (int i=1;i<=n;i++) read(a[j][i]);
for (int i=1;i<3;i++)
for (int j=i+1;j<=3;j++){
memset(t,0,sizeof(t)); tmp=0;
for (int k=1;k<=n;k++) b[a[i][k]]=k;
for (int k=1;k<=n;k++) a[j][k]=b[a[j][k]];
for (int k=1;k<=n;k++) tmp+=query(a[j][k]),add(a[j][k]);
ans+=1LL*n*(n-1)/2-tmp;
}
return printf("%lld\n",1LL*n*(n-1)/2-ans/2),0;
}

  

最新文章

  1. Js ==和===的区别
  2. HTTP协议 请求篇
  3. linux环境下配置java WEB项目运行环境,jdk8+tomcat8+mysql5.7.11 新手向
  4. 微软发布独立Android模拟器 为开发者提供测试
  5. BZOJ3073 : [Pa2011]Journeys
  6. RESEACH PAPER
  7. HDU 4599 概率DP
  8. 设计模式之单例模式(Singleton Pattern)
  9. PHP漏洞全解(二)-命令注入攻击
  10. 自定义复选框 checkbox 样式
  11. 在word 中复选框划勾或叉的方法
  12. [Usaco2008 Dec]Patting Heads 轻拍牛头[筛法]
  13. POJ 3659 Cell Phone Network / HUST 1036 Cell Phone Network(最小支配集,树型动态规划,贪心)-动态规划做法
  14. javaWeb学习之tomcat服务器
  15. eclipse新建工作空间后的常用设置
  16. Django--cookie(登录用)
  17. COMS3200 The RUSH protocol
  18. Spring MVC 请求映射 (二)
  19. 异步时代-java的协程路在何方
  20. Confluence 6 &quot;Duplicate Key&quot; 相关问题解决

热门文章

  1. SVG可伸缩矢量图形
  2. bzoj2216
  3. bzoj3661
  4. nginx初相识
  5. PCB genesis短槽加引导孔实现方法
  6. Is the Information Reliable?(差分约束系统)
  7. SpringBoot入门之HelloWorld
  8. ibatis 基类生成
  9. ACM_出题人这样不好吧
  10. 355 Design Twitter 设计推特