分析:
给定n个二元组,求选出两个二元组(可以是同一个)组成一序列其LIS为1,2,3,4的方法数。
分别记为s1, s2, s3, s4
s1,s4对应的情形为a >= b >= c >= d, a < b < c < d,易求
长度为3时,先求得s3 + s4的值,分解为两种情况的和减去两种情况的并,min(a, b) < c < d, a < b < max(c, d),减去a < min(b, c) <= max(b, c) < d的方法数(使用二位树状数组,只考虑x[i] < y[i]),此时方法数为s3 + s4,减去s4得s3
总数为n * n,减去其他情况即为s2
若有更好的解法请指出!
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 100008;
int C[1018];
int x[N], y[N]; inline int lowbit(int x){
return x&-x;
}
void add(int x, int n){//将第x个数增加val,从1计数
for(int i=x;i<=n;i+=lowbit(i)){
C[i]++;
}
}
int sum(int x){//求1到x的和
int ret = 0;
for(int i=x;i>0;i-=lowbit(i)){
ret+=C[i];
}
return ret;
}
namespace bit{ int C[1008][1008];
inline int lowbit(int x){
return x&-x;
}
void add(int x,int y,int n){
for(int i=x;i<=n;i+=lowbit(i)){
for(int j=y;j<=n;j+=lowbit(j)) {
C[i][j]++;
}
}
} int sum(int x,int y){
int ret=0;
for(int i=x;i>0;i-=lowbit(i)) {
for(int j=y;j>0;j-=lowbit(j)) {
ret+=C[i][j];
}
}
return ret;
}
LL solve(int n){
LL ans = 0;
for(int i = 1; i <= n; i++){
if(x[i] < y[i]){
ans += sum(x[i] - 1, y[i] - 1);
}
}
return ans;
} } int main(){
int n, m;
while(~scanf("%d %d", &n, &m)){
memset(bit::C, 0, sizeof(bit::C));
int tot = 0;
for(int i = 1; i <= n; i++){
scanf("%d %d", &x[i], &y[i]);
if(x[i] < y[i]){
bit::add(x[i], y[i], m);
}
}
LL s1 = 0, s2 = 0, s3 = 0, s4 = 0;
//s4
memset(C, 0, sizeof(C));
for(int i = 1; i<= n; i++){
if(x[i] < y[i]){
add(y[i], m);
}
}
for(int i = 1; i <= n; i++){
if(x[i] < y[i]){
s4 += sum(x[i] - 1);
}
}
//s3 + s4
memset(C, 0, sizeof(C));
for(int i = 1; i <= n; i++){
add(min(x[i], y[i]), m);
}
for(int i = 1; i <= n; i++){
if(x[i] < y[i]){
s3 += sum(x[i] - 1);
}
} memset(C, 0, sizeof(C));
for(int i = 1; i <= n; i++){
add(max(x[i], y[i]), m);
}
for(int i = 1; i <= n; i++){
if(x[i] < y[i]){
s3 += n - sum(y[i]);
}
} s3 -= bit::solve(n);
s3 -= s4; //s1
memset(C, 0, sizeof(C));
tot = 0;
for(int i = 1; i <= n; i++){
if(x[i] >= y[i]){
tot++;
add(y[i], m);
}
}
for(int i = 1; i <= n; i++){
if(x[i] >= y[i]){
s1 += tot - sum(x[i] - 1);
}
}
s2 = (LL)n * n - s1 - s3 - s4;
printf("%I64d %I64d %I64d %I64d\n", s1, s2, s3, s4);
} return 0;
}
湘潭1247 Pair-Pair(树状数组)的更多相关文章
-
2016 大连网赛---Weak Pair(dfs+树状数组)
题目链接 http://acm.split.hdu.edu.cn/showproblem.php?pid=5877 Problem Description You are given a rooted ...
-
HDU - 5877 Weak Pair (dfs+树状数组)
题目链接:Weak Pair 题意: 给出一颗有根树,如果有一对u,v,如果满足u是v的父节点且vec[u]×vec[v]<=k,则称这对结点是虚弱的,问这棵树中有几对虚弱的结点. 题解: 刚开 ...
-
HDU 5877 Weak Pair(树状数组)
[题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=5877 [题目大意] 给出一棵带权有根树,询问有几对存在祖先关系的点对满足权值相乘小于等于k. [题 ...
-
HDU 5877 Weak Pair(树状数组+dfs+离散化)
http://acm.hdu.edu.cn/showproblem.php?pid=5877 题意: 给出一棵树,每个顶点都有权值,现在要你找出满足要求的点对(u,v)数,u是v的祖先并且a[u]*a ...
-
HDU 5877 Weak Pair DFS + 树状数组 + 其实不用离散化
http://acm.hdu.edu.cn/listproblem.php?vol=49 给定一颗树,然后对于每一个节点,找到它的任何一个祖先u,如果num[u] * num[v] <= k.则 ...
-
树形DP+树状数组 HDU 5877 Weak Pair
//树形DP+树状数组 HDU 5877 Weak Pair // 思路:用树状数组每次加k/a[i],每个节点ans+=Sum(a[i]) 表示每次加大于等于a[i]的值 // 这道题要离散化 #i ...
-
hdu_5877_Weak Pair(离散+DFS+树状数组)
题目链接:hdu_5877_Weak Pair 题意: 给你一棵树,让你找有多少对满足那两个条件的weak pair 题解: 有人用Treap,我不会,然后我用树状数组+离散来替代Treap,用DFS ...
-
HDU 5877 2016大连网络赛 Weak Pair(树状数组,线段树,动态开点,启发式合并,可持久化线段树)
Weak Pair Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Tota ...
-
hdu 5877 Weak Pair dfs序+树状数组+离散化
Weak Pair Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Prob ...
-
HDU5877 Weak Pair dfs + 线段树/树状数组 + 离散化
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5877 题意: weak pair的要求: 1.u是v的祖先(注意不一定是父亲) 2.val[u]*va ...
随机推荐
-
Linux 获取本机IP、MAC地址用法大全
getifaddrs()和struct ifaddrs的使用,获取本机IP ifaddrs结构体定义如下: struct ifaddrs { struct ifaddrs *ifa_next; /* ...
-
记录一下对swiper4.x.js在H5单页中的滑动优化
应用场景 仅仅应用于单页应用的滑动操作,用swiper4.x接管页面的滚动操作.用来支持顶部和尾部的回弹效果,进一步来支持常见那种下拉刷新动画效果.不适用于轮播图那种应用场景. 虽然只是针对swipe ...
-
jsp导入数据库数据写法(模板)
1.导入表格模板 <%@ page language="java" contentType="text/html; charset=utf-8" page ...
-
Microsoft Active Directory(LDAP)连接常见错误代码
接下来显示的认证错误类似于这样: "The exception is [ LDAP: error code 49 - 80090308: LdapErr: DSID-0Cxxxxxx, co ...
-
MFC图形编辑器
前言 vs2015竟然可以完美打开工程,哈哈可以直接生成类图了.由于内容较多,所以根据内容的重要性会安排详略. https://github.com/bajdcc/GraphEditor/releas ...
-
APUE(unix环境高级编程)第三版---first day---部署书中实例的运行环境(apue.h)
操作环境:RHEL7.0 部署apue.h实例运行环境 1.下载头文件src.3e.tar.gz 2.解压 tar zxvf src.3e.tar.gz 3.创建普通用户(我仿照书上创建的sar用户) ...
-
hihocoder1310 岛屿
hihocoder1310 岛屿 题意: 中文题意 思路: dfs,面积和数量都很好求,问题在岛屿形状上,感觉让人比较麻烦,用vector保存各个点,只要两个岛之间每个点距离一样就好了,这里的形状的定 ...
-
Android数据库代码优化(2) - 从SQLite说起
从SQLite说起 如果没有SQLite的基础,我们只是从Android封装的SQLite API去学习的话,难免思路会受到限制.所以,我们还是需要老老实实从头开始学习SQLite. 当我们有一身的S ...
-
当AVPlayer在被释放之后,Player一直监听的时间没有被移除,提示错误的解决办法
Xcode Consolu打印出来的提示: An instance 0x156608c0 of class AVPlayer was deallocated while key value obser ...
-
Jsp上传组件Smartupload介绍
<form action="UploadServlet" enctype="multipart/form-data" method="post& ...