湘潭1247 Pair-Pair(树状数组)

时间:2022-08-28 09:40:40

分析:

给定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(树状数组)的更多相关文章

  1. 2016 大连网赛---Weak Pair&lpar;dfs&plus;树状数组&rpar;

    题目链接 http://acm.split.hdu.edu.cn/showproblem.php?pid=5877 Problem Description You are given a rooted ...

  2. HDU - 5877 Weak Pair &lpar;dfs&plus;树状数组&rpar;

    题目链接:Weak Pair 题意: 给出一颗有根树,如果有一对u,v,如果满足u是v的父节点且vec[u]×vec[v]<=k,则称这对结点是虚弱的,问这棵树中有几对虚弱的结点. 题解: 刚开 ...

  3. HDU 5877 Weak Pair(树状数组)

    [题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=5877 [题目大意] 给出一棵带权有根树,询问有几对存在祖先关系的点对满足权值相乘小于等于k. [题 ...

  4. HDU 5877 Weak Pair(树状数组&plus;dfs&plus;离散化)

    http://acm.hdu.edu.cn/showproblem.php?pid=5877 题意: 给出一棵树,每个顶点都有权值,现在要你找出满足要求的点对(u,v)数,u是v的祖先并且a[u]*a ...

  5. HDU 5877 Weak Pair DFS &plus; 树状数组 &plus; 其实不用离散化

    http://acm.hdu.edu.cn/listproblem.php?vol=49 给定一颗树,然后对于每一个节点,找到它的任何一个祖先u,如果num[u] * num[v] <= k.则 ...

  6. 树形DP&plus;树状数组 HDU 5877 Weak Pair

    //树形DP+树状数组 HDU 5877 Weak Pair // 思路:用树状数组每次加k/a[i],每个节点ans+=Sum(a[i]) 表示每次加大于等于a[i]的值 // 这道题要离散化 #i ...

  7. hdu&lowbar;5877&lowbar;Weak Pair&lpar;离散&plus;DFS&plus;树状数组&rpar;

    题目链接:hdu_5877_Weak Pair 题意: 给你一棵树,让你找有多少对满足那两个条件的weak pair 题解: 有人用Treap,我不会,然后我用树状数组+离散来替代Treap,用DFS ...

  8. HDU 5877 2016大连网络赛 Weak Pair&lpar;树状数组,线段树,动态开点,启发式合并,可持久化线段树&rpar;

    Weak Pair Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Tota ...

  9. hdu 5877 Weak Pair dfs序&plus;树状数组&plus;离散化

    Weak Pair Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Prob ...

  10. HDU5877 Weak Pair dfs &plus; 线段树&sol;树状数组 &plus; 离散化

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5877 题意: weak pair的要求: 1.u是v的祖先(注意不一定是父亲) 2.val[u]*va ...

随机推荐

  1. Linux 获取本机IP、MAC地址用法大全

    getifaddrs()和struct ifaddrs的使用,获取本机IP ifaddrs结构体定义如下: struct ifaddrs { struct ifaddrs *ifa_next; /* ...

  2. 记录一下对swiper4&period;x&period;js在H5单页中的滑动优化

    应用场景 仅仅应用于单页应用的滑动操作,用swiper4.x接管页面的滚动操作.用来支持顶部和尾部的回弹效果,进一步来支持常见那种下拉刷新动画效果.不适用于轮播图那种应用场景. 虽然只是针对swipe ...

  3. jsp导入数据库数据写法(模板)

    1.导入表格模板 <%@ page language="java" contentType="text/html; charset=utf-8" page ...

  4. Microsoft Active Directory(LDAP)连接常见错误代码

    接下来显示的认证错误类似于这样: "The exception is [ LDAP: error code 49 - 80090308: LdapErr: DSID-0Cxxxxxx, co ...

  5. MFC图形编辑器

    前言 vs2015竟然可以完美打开工程,哈哈可以直接生成类图了.由于内容较多,所以根据内容的重要性会安排详略. https://github.com/bajdcc/GraphEditor/releas ...

  6. APUE&lpar;unix环境高级编程&rpar;第三版---first day---部署书中实例的运行环境&lpar;apue&period;h&rpar;

    操作环境:RHEL7.0 部署apue.h实例运行环境 1.下载头文件src.3e.tar.gz 2.解压 tar zxvf src.3e.tar.gz 3.创建普通用户(我仿照书上创建的sar用户) ...

  7. hihocoder1310 岛屿

    hihocoder1310 岛屿 题意: 中文题意 思路: dfs,面积和数量都很好求,问题在岛屿形状上,感觉让人比较麻烦,用vector保存各个点,只要两个岛之间每个点距离一样就好了,这里的形状的定 ...

  8. Android数据库代码优化&lpar;2&rpar; - 从SQLite说起

    从SQLite说起 如果没有SQLite的基础,我们只是从Android封装的SQLite API去学习的话,难免思路会受到限制.所以,我们还是需要老老实实从头开始学习SQLite. 当我们有一身的S ...

  9. 当AVPlayer在被释放之后&comma;Player一直监听的时间没有被移除&comma;提示错误的解决办法

    Xcode Consolu打印出来的提示: An instance 0x156608c0 of class AVPlayer was deallocated while key value obser ...

  10. Jsp上传组件Smartupload介绍

    <form action="UploadServlet" enctype="multipart/form-data" method="post& ...