首页 > 代码库 > 湘潭1247 Pair-Pair(树状数组)
湘潭1247 Pair-Pair(树状数组)
分析:
给定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(树状数组)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。