題面

傳送門

題解

我的做法似乎非常復雜啊……

首先最長上升子序列長度就等于把它反過來再接到前面求一遍，比方說把\(2134\)變成\(43122134\)，實際上變化之后的求一個最長上升子序列和方案數就是答案了

最長上升子序列隨便求求，主要是這個方案數很麻煩啊……我的做法是對每一個長度開一個動態開點線段樹，然后每次在對應的長度里二分跑前綴和

其實這里完全不用動態開點線段樹的，直接把權值離散一下然后一棵線段樹就夠了，跑得飛快

其實這里連線段樹都不需要直接樹狀數組就可以維護前綴最大值和方案之和了

然后沒有然后了

//minamoto #include<bits/stdc++.h> #define R register #define inline __inline__ __attribute__((always_inline)) #define fp(i,a,b) for(int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(int i=(a),I=(b)-1;i>I;--i) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } const int N=4e5+5,P=1e9+7,M=(N<<5)+5; inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;} inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;} inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;} int ksm(R int x,R int y){R int res=1;for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;return res; } int sum[M],lc[M],rc[M],rt[N],tot; int a[N],f[N],g[N],b[N],m,n,res,mx,lim; void query(int p,int l,int r,int x){if(!p||l==r)return res=add(res,sum[p]),void();int mid=(l+r)>>1;if(x<=mid)query(lc[p],l,mid,x);else res=add(res,sum[lc[p]]),query(rc[p],mid+1,r,x); } void ins(int &p,int l,int r,int x,int val){if(!p)p=++tot;sum[p]=add(sum[p],val);if(l==r)return;int mid=(l+r)>>1;x<=mid?ins(lc[p],l,mid,x,val):ins(rc[p],mid+1,r,x,val); } int main(){ // freopen("testdata.in","r",stdin);n=read();fp(i,1,n)a[i]=b[i]=read();sort(b+1,b+1+n),lim=unique(b+1,b+1+n)-b-1;fp(i,1,n)a[i]=lower_bound(b+1,b+1+lim,a[i])-b;reverse(a+1,a+1+n);fp(i,1,n)a[(n<<1)-i+1]=a[i];n=(n<<1),m=0,b[0]=0;fp(i,1,n){if(a[i]>b[m])f[i]=++m,b[m]=a[i];else{int k=lower_bound(b+1,b+1+m,a[i])-b;f[i]=k,b[k]=a[i];}if(f[i]==1)g[i]=1;else res=0,query(rt[f[i]-1],1,lim,a[i]-1),g[i]=res;if(i>(n>>1)&&f[i]==f[n-i+1])g[i]=dec(g[i],g[n-i+1]);ins(rt[f[i]],1,lim,a[i],g[i]);cmax(mx,f[i]);}res=0;fp(i,(n>>1)+1,n)if(f[i]==mx){res=add(res,g[i]);if(f[n-i+1]==mx)res=add(res,g[n-i+1]);}res=mul(res,ksm(2,(n>>1)-mx));printf("%d %d\n",mx,res);return 0; }

轉載于:https://www.cnblogs.com/bztMinamoto/p/10712142.html

總結

以上是生活随笔為你收集整理的LOJ#6048. 「雅礼集训 2017 Day10」数列（线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。