湘潭1247 Pair-Pair(树状数组)-白红宇

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

阅读量：6451 次

发布时间：2019-06-23

本文共 2352 字，大约阅读时间需要 7 分钟。

分析:

给定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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                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;}

转载于:https://www.cnblogs.com/IMGavin/p/5894370.html

你可能感兴趣的文章