传送门
题意：给一个数组，要你找到三元上升子序列，三元上升子序列的定义是对任意\( i \le j \le k \)有\( a_i \le a_j \le a_k \)，数据规模\( 1 \leq n \leq 30000 \)，\( 1 \leq a_i \leq 10^{18} \)
解答：范围太大需要离散化，离散化后\( dp[i][j] \)表示k=j的位置的i元上升子序列有多少个，使用树状数组维护前面i-1元上升子序列个数即可
状态转移方程：\( dp[i][j] = \Sigma_{x=1}^{i-1} dp[x][j-1](a[x]<a[i]) \)
|
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 12/30/2019 11:03:37 PM *************************************************************************/ //#pragma GCC optimize(2) //#pragma GCC diagnostic error "-std=c++11" #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define endl '\n' #define ALL(x) x.begin(),x.end() #define MP(x,y) make_pair(x,y) #define ll long long #define ull unsigned long long #ifdef WindCry1 #define DEBUG(x) cout<<#x<<" : "<<x<<endl; #endif #define lowbit(x) x&(-x) #define ls u<<1 #define rs u<<1|1 using namespace std; template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;} template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;} template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);} template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);} typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<double,double> pdd; const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; ll n,m,bit[30010],a[30010],dp[30010][4],s[30010]; inline ll val(ll x){ return lower_bound(s+1,s+1+m,x)-s; } inline void edit(int pos,ll data){ for(int i=pos;i<=m;i+=lowbit(i)) bit[i]+=data; } inline ll query(int pos){ ll res=0; for(int i=pos;i;i-=lowbit(i)) res+=bit[i]; return res; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #ifdef WindCry1 freopen("C:/Users/LENOVO/Desktop/in.txt","r",stdin); #endif cin>>n; for(int i=1;i<=n;i++) cin>>a[i],s[i]=a[i]; sort(s+1,s+1+n); m=unique(s+1,s+1+n)-s-1; for(int i=1;i<=n;i++) dp[i][1]=1,a[i]=val(a[i]); for(int j=2;j<=3;j++){ memset(bit,0,sizeof bit); for(int i=1;i<=n;i++){ dp[i][j]=query(a[i]-1); edit(a[i],dp[i][j-1]); } } ll res=0; for(int i=1;i<=n;i++) res+=dp[i][3]; cout<<res<<endl; return 0; } |
0 条评论