当前位置:网站首页>P1637 ternary ascending subsequence (DP + discrete weight tree array)

P1637 ternary ascending subsequence (DP + discrete weight tree array)

2021-08-10 07:40:12 wx6110fa547fd20

P1637 Ternary ascending subsequence (DP+ Discretized weight tree array )

  Portal

Ideas : d p + dp+ dp+ Discretized weight tree array .

It is obvious that d p [ i ] [ j ] dp[i][j] dp[i][j] For a length of i i i With a [ j ] a[j] a[j] The number of subsequences at the end .

There's a transfer equation : d p [ i ] [ j ] = ∑ k < j , a [ k ] < a [ j ] d p [ i − 1 ] [ k ] dp[i][j]=\sum\limits_{k<j,a[k]<a[j]} dp[i-1][k] dp[i][j]=k<j,a[k]<a[j]dp[i1][k]

Obviously, the time complexity of violence : O ( n 2 m ) O(n^2m) O(n2m)

because a [ i ] ≤ 2 63 a[i]\leq2^{63} a[i]263, but n ≤ 3 e 4 n\leq 3e4 n3e4 Consider discretization a [ i ] a[i] a[i], Then turn to the weight segment tree to store d p [ i − 1 ] [ k ] dp[i-1][k] dp[i1][k].

First initialize the unary ascending subsequence , Then traverse from front to back ,

There's a transfer equation : d p [ i ] [ j ] + = q u e r y ( a [ j ] − 1 ) dp[i][j]+=query(a[j]-1) dp[i][j]+=query(a[j]1)

Update again u p d a t e ( a [ j ] , d p [ i − 1 ] [ j ] ) update(a[j],dp[i-1][j]) update(a[j],dp[i1][j]).

Time complexity : O ( n m l o g n ) O(nmlogn) O(nmlogn), m m m It is a sequence of ascending subsequences .

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
typedef long long ll;
const int N=3e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int n,m;
ll a[N],b[N],tr[N];
ll dp[4][N];
#define lowbit(x) x&(-x)
void update(int x,int k){
	while(x<=m){
		tr[x]+=k;
		x+=lowbit(x);
	}
}
ll query(int x){
	ll ans=0;
	while(x){
		ans+=tr[x];
		x-=lowbit(x);
	}
	return ans;
}
int main(){	
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]),b[i]=a[i];
		dp[1][i]=1;
	}
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	for(int i=2;i<=3;i++){
		mst(tr);
		for(int j=1;j<=n;j++)
		{
			dp[i][j]+=query(a[j]-1);
			update(a[j],dp[i-1][j]);
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=dp[3][i];
	printf("%lld\n",ans);
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810073742598j.html