CF 61E 树状数组+离散化求逆序数加强版三个数逆序-白红宇

CF 61E 树状数组+离散化求逆序数加强版三个数逆序

阅读量：6243 次

发布时间：2019-06-22

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

http://codeforces.com/problemset/problem/61/E

题意是求 i<j<k && a[i]>a[j]>a[k] 的对数

会树状数组求逆序数的话，这个推一下就能出结果：

做法：

1、离散化，由于a[i]能够达到1e9

2、插入a[i]的时候，记录x[i]=i-sum(a[i]); a[i]之前比a[i]大的有x[i]个

3、插入完毕后，求a[i] 之后比a[i]小的数的个数y[i]

ans=segma(x[i]*y[i]) 注意x[i]*y[i]会超出int 由于这wa了一次

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               using namespace std;#define ls(rt) rt*2#define rs(rt) rt*2+1#define ll long long#define ull unsigned long long#define rep(i,s,e) for(int i=s;i
               
                >1;const double EPS = 1e-8;const int INF = 100000000;const int MAXN = 1e6+100;ll x[MAXN],y[MAXN];int a[MAXN],tmp[MAXN];ll c[MAXN];int n;inline int lowb(int x) {return x&(-x);}void update(int x, int d){ while(x<=n) { c[x]+=d; x+=lowb(x); }}ll sum(int x){ ll ret=0; while(x>0) { ret+=c[x]; x-=lowb(x); } return ret;}bool cmp(const int i, const int j){ return a[i]