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

· · 题解

诶,题解里的大佬都是用乘法原理吗?

那我怎么没想到呢? 太菜了想不到

思路

看到这题与逆序对有关,我就先设数组aa[i]表示这一个数字前比他小的数的个数(以这个数字为结尾的 逆序对/二元上升子序列 个数)

归并一下就可以得出aa的值

但这道题要求三元上升子序列,,,我就想到对原数组再进行一次归并

跟求逆序对类似,只不过合并前要统计左半部分对应的aa的和.合并时如果右半部分的要合并的那个数字比左半部分的对应数字要大,就把答案加上左半部分剩余数字对应的aa之和(就相当于求以这个数字为结尾的三元上升子序列个数);否则把aa的和减去左半部分并过来的数对应的aa值.

拿着样例手玩几下,还是比较好理解的

code

//注:此代码在linux下的emacs写成,格式丑轻喷
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<cmath>
#define il inline
using namespace std;
struct nn
{
  int x,n;
}a[30010],b[30010],c[30010];    //x为数字值 n为数字在原数组中的下标
int n;
long long aa[30010],ans;
il void s1(int l,int r) //第一次归并算出aa
{
  if(l==r) return;
  int mid=(l+r)>>1;
  s1(l,mid);s1(mid+1,r);
  int i1=l,i2=mid+1,ii=l;
  while(i1<=mid&&i2<=r)
    {
      if(a[i1].x>=a[i2].x)
        {
        c[ii++]=a[i1++];
        }
      else
        {
         aa[a[i2].n]+=mid-i1+1;
          c[ii++]=a[i2++];
     }
    }
  while(i1<=mid) c[ii++]=a[i1++];
  while(i2<=r) c[ii++]=a[i2++];
  for(register int i=l;i<=r;i++) a[i]=c[i];
}
il int s2(int l,int r)
{
  if(l==r) return aa[b[l].n];
  int mid=(l+r)>>1;
  long long s=0,ss=0;   //s为这段区间左半部分的aa和,ss为这段区间的aa和
  s=ss=s2(l,mid); ss+=s2(mid+1,r);
  int i1=l,i2=mid+1,ii=l;
  while(i1<=mid&&i2<=r)
    {
      if(b[i1].x>=b[i2].x)
        {
         s-=aa[b[i1].n];
          c[ii++]=b[i1++];
     }
      else
      {
        ans+=s;
       c[ii++]=b[i2++];
     }
    }
  while(i1<=mid) c[ii++]=b[i1++];
  while(i2<=r) c[ii++]=b[i2++];
  for(register int i=l;i<=r;i++) b[i]=c[i];
  return ss;    //返回区间的aa和
}
int main()
{
  scanf("%d\n",&n);
  for(register int i=1;i<=n;i++)
    {
      scanf("%d",&a[i].x);
      a[i].n=i;
      b[i]=a[i];
    }
  s1(1,n);
  s2(1,n);
  printf("%lld\n",ans);
  return 0;
}