题解 P1637 【三元上升子序列】

· · 题解

非离散化树状数组写法

乘法原理大家都懂,树状数组求逆序对大家也都知道.但是这个题

为什么非要离散化?

当时我们存的是数字的大小,现在我们存位置不行吗?

详细分析

我们先给它按数字大小排个序.

第一遍:找数字比他小而且编号比它小的数的个数.

第二遍:找数字比他大而且编号比它大的数的个数.

于是预处理为↓

struct Node{int num,pos;}sf[30010];
bool comp(Node u,Node v){return u.num<v.num;}
for(int i=1;i<=n;++i){
    scanf("%d",&sf[i].num);
    sf[i].pos=i;
}
sort(sf+1,sf+n+1,comp);

然后第一遍

for(int vc=1,i=1;i<=n;++i){
    if(sf[i].num!=sf[i-1].num)
    while(vc<i)add1(sf[vc++].pos);
    cnts[i]=qy1(sf[i].pos-1);
}

核心在vc上,因为相等的数是不会算到里面的,所以我们引入一个vc记录的是上一个相等的数的位置.

因为这一遍我们需要从小往大找,所以vc=1.

注:

add1为在第一个树状数组里面在某个位置+1.

qy1为在第一个树状数组里面查询某个位置及之前的数的个数.

下文add2和qy2同理

第二遍:

for(int vc=n,i=n;i;--i){
    if(sf[i].num!=sf[i+1].num)
    while(vc>i)add2(sf[vc--].pos);
    ens+=cnts[i]*(qy2(n)-qy2(sf[i].pos));
}

因为排序是从大到小,这一遍就得从后往前.

Code

#include<bits/stdc++.h>
#define l(p)    (p&(-p))
using namespace std;
int BIT1[30010],BIT2[30010],n,ans;
long long cnts[30010],ens;
struct Node{int num,pos;}sf[30010];
bool comp1(Node u,Node v){
    return u.num<v.num;
}
void add1(int p){
    for(;p<=n;p+=l(p))
        ++BIT1[p];
}
void add2(int p){
    for(;p<=n;p+=l(p))
        ++BIT2[p];
}
int qy1(int p){
    ans=0;
    for(;p;p-=l(p))
        ans+=BIT1[p];
    return ans;
}
int qy2(int p){
    ans=0;
    for(;p;p-=l(p))
        ans+=BIT2[p];
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&sf[i].num);
        sf[i].pos=i;
    }
    sort(sf+1,sf+n+1,comp1);
    for(int vc=1,i=1;i<=n;++i){
        if(sf[i].num!=sf[i-1].num)
            while(vc<i)
                add1(sf[vc++].pos);
        cnts[i]=qy1(sf[i].pos-1);
    }
    for(int vc=n,i=n;i;--i){
        if(sf[i].num!=sf[i+1].num)
            while(vc>i)
                add2(sf[vc--].pos);
        ens+=cnts[i]*(qy2(n)-qy2(sf[i].pos));
    }
    printf("%lld",ens);
    return 0;
}