[洛谷 P1637]三元上升子序列

danihao123 posted @ 2016年9月13日 12:46 in 题解 with tags 树状数组 洛谷 , 156 阅读
转载请注明出处:http://danihao123.is-programmer.com/

这个明显是用树状数组进行统计……然而是树状数组统计第一题……so sad

答案很有可能就超int,建议开long long(反正我这么做了)。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=30005;
int n;
struct BIT{
    int C[maxn];
    inline int lowbit(int x){
        return x&-x;
    }
    inline void Add(int p,int v){
        while(p<=n){
            C[p]+=v;
            p+=lowbit(p);
        }
    }
    inline int Sum(int x){
        register int ans=0;
        while(x>0){
            ans+=C[x];
            x-=lowbit(x);
        }
        return ans;
    }
    inline int Query(int l,int r){
        return Sum(r)-Sum(l-1);
    }
};

BIT T1,T2;
int A[maxn],A2[maxn];
int siz;
inline void InitLsh(){
    register int i;
    sort(A2+1,A2+n+1);
    siz=unique(A2+1,A2+n+1)-A2-1;
}
inline int GetLsh(int i){
    return lower_bound(A2+1,A2+siz+1,A[i])-A2;
}

int main(){
    register int i,left,right,temp;
    register long long ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        A2[i]=A[i];
    }
    InitLsh();
    for(i=1;i<=n;i++){
        T2.Add(GetLsh(i),1);
    }
    for(i=1;i<=n;i++){
        temp=GetLsh(i);
        T2.Add(temp,-1);
        left=T1.Sum(temp-1);
        right=T2.Query(temp+1,siz);
        ans+=((long long)left)*((long long)right);
        T1.Add(temp,1);
    }
    printf("%lld\n",ans);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter