当前位置:网站首页>P3970 [tjoi2014] ascending subsequence (bit & DP)

P3970 [tjoi2014] ascending subsequence (bit & DP)

2021-08-10 09:07:25 wx6110fa547fd20

P3970 [TJOI2014] Ascending subsequence (BIT&DP)

Find a length of at least 2 Different L I S LIS LIS Number .

  • Ignore a length of at least 2, And different conditions .

Make f i f_i fi Said to a i a_i ai Of L I S LIS LIS Number .

Then there are : f i = ( ∑ a j < a i f j ) + 1 , ( j < i ) \large f_i=(\sum\limits_{a_j<a_i} f_j)+1,(j<i) fi=(aj<aifj)+1,(j<i)

a n s = ∑ i = 1 n f i \large ans=\sum\limits_{i=1}^n f_i ans=i=1nfi

Find the prefix and available B I T BIT BIT Optimize to l o g n logn logn.

Time complexity : O ( n l o g n ) O(nlogn) O(nlogn)

because ∣ a i ∣ ≤ 1 0 9 |a_i|\le 10^9 ai109 , Consider discretization .

Next processing Different and ** Length at least 2 2 2** Conditions .

  • Different

We are for each of the same a i a_i ai, Record your last answer .

hypothesis a j = a i , j < i , l a s t a n s = f j \large a_j=a_i,j<i,lastans=f_j aj=ai,j<i,lastans=fj

obviously f i \large f_i fi Include f j \large f_j fj , That is, the answer will repeat .

therefore f i \large f_i fi Should be subtracted f j \large f_j fj.

therefore

f i = ( ∑ a j < a i f j ) + 1 − l a s t a n s , ( j < i ) \large f_i=(\sum\limits_{a_j<a_i} f_j)+1-lastans_{},(j<i) fi=(aj<aifj)+1lastans,(j<i)

l a s t a n s i + = f i \large lastans_{i}+=f_i lastansi+=fi

  • The length is 2

Last ∑ i = 1 m f i − m \large \sum\limits_{i=1}^m f_i-m i=1mfim

m \large m m​ Is the length after discretization , That is, the length is 1 1 1 The answer .


// Problem: P3970 [TJOI2014] Ascending subsequence 
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3970
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2021-07-26 18:05:09
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
int n,lst[N],a[N],b[N],m;
ll s;
struct BIT{
	#define lowbit(x) x&(-x)
	#define il inline
	ll s[N];
	int n;
	il void upd(int x,int v){
		while(x<=m){
			s[x]=(s[x]+v)%mod;x+=lowbit(x);
		}return;
	}
	il ll que(int x){
		ll ans=0;
		while(x){
			ans=(ans+s[x])%mod;x-=lowbit(x);
		}return ans;
	}
}T;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	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;
		ll x=(T.que(a[i]-1)+1-lst[a[i]])%mod;
		T.upd(a[i],x);
		lst[a[i]]+=x;
	}
	printf("%lld\n",(T.que(m)-m+mod)%mod);
	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.
  • 55.
  • 56.
  • 57.
  • 58.

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