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;
}

原文链接:https://www.cnblogs.com/Sxy_Limit/p/12158295.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有