P1637 三元上升子序列

暴力是三重循环,枚举三个数判断是否组成三元上升子序列,但是n有30000,o(n^3^)直接枚举肯定是会t的,不难发现当中间的数为a[i]时它所贡献出的三元上升子序列
的个数为1~i-1中比a[i]小的数的个数乘i+1~n中比a[i]大的数的个数.这很容易就会想到逆序对(虽然还是有点不同),逆序对的常用方法归并没法求出每个数的逆序对个数(可能可以只不过我不会),所以就很容易想到线段树.
做法和权值线段树类似

如图1所示,每个叶节点表示一个数,所以就可以在logn的时间复杂度内算出在整颗线段树中比某个数大或小的数的个数.只要对于每个数查询出比他小的数的个数(small[i])并记录下来再把这个数加入这颗线段树.同理,将所有的数倒着放入,查询出在当前线段树中比这个数大的数的个数那么这个数(big)的贡献就是(small[i]*big).
数的个数比较大,没法直接加入线段树,所以需要先离散化.

#include<bits/stdc++.h>
#define rap(i,first,last) for(int i=first;i<=last;++i)
#define sing(i,first,last) for(int i=first;i>=last;--i)
#define lson now*2
#define rson now*2+1
#define middle (left+right)/2
#define left lson,left,middle
#define right rson,middle+1,right
using namespace std;
const int maxn=1e5+7;
int n,m;
int tree[maxn*4];
void pushup(int now)
{
    tree[now]=tree[lson]+tree[rson];
}
void build(int now=1,int left=1,int right=n)//建树,虽然没什么用
{
    if(left==right)
    {
        tree[now]=0;
        return;
    }
    build(left);
    build(right);
    pushup(now);
}
void updata(int num,int now=1,int left=1,int right=n)//修改
{
    if(num<left||right<num)return;
    if(left==right)//当是叶节点时直接修改
    {
        tree[now]++;
        return;
    }
    updata(num,left);
    updata(num,right);
    pushup(now);//不是叶节点时需要在子树修改后修改,其实没有必要,反正都是+1
}
int query_small(int num,int now=1,int left=1,int right=n)//查询当前数中比num小的数的个数
{
    if(left>=num)return 0;//当当前的数的区间的最小值也比num大时自然整个区间都不会有比num小的数了
    if(right<num)//当当前区间的最大值也比num小时整个区间里的数也就比num小了
    {
        return tree[now];
    }
    int result=0;//返回的值为左子树中比num小的数的个数+右子树中比num小的数的个数
    result+=query_small(num,left);
    result+=query_small(num,right);
    return result;
}
int query_big(int num,int now=1,int left=1,int right=n)//与上同理
{
    if(right<=num)return 0;
    if(left>num)
    return tree[now];
    int result=0;
    result+=query_big(num,left);
    result+=query_big(num,right);
    return result;
}
map<int,int>hash;//因为懒所以直接map离散化
int arr[maxn];
int sor[maxn];
int small[maxn];
int main()
{
    scanf("%d",&m);
    rap(i,1,m)
    {
        scanf("%d",&arr[i]);
        sor[i]=arr[i];
    }
    //离散化
    sort(sor+1,sor+1+m);
    int now=1;
    hash[sor[1]]=1;
    rap(i,2,m)
    {
        if(sor[i]!=sor[i-1])
        {
            hash[sor[i]]=++now;
        }
    }
    n=now;//数的大小为不同的数的个数
    long long answer=0;
    build();
    rap(i,1,m)
    {
        small[i]=query_small(hash[arr[i]]);//查询出当前比这个数小的数的个数
        updata(hash[arr[i]]);//插入这个数
    }
    build();
    sing(i,m,1)
    {
        answer+=small[i]*query_big(hash[arr[i]]);//计算这个数的贡献
        updata(hash[arr[i]]);
    }
    printf("%lld",answer);//输出answer,注意long long
    return ~0;
}