题目描述
降雷皇哈蒙很喜欢雷电，他想找到神奇的电光。
哈蒙有$n$条导线排成一排，每条导线有一个电阻值，神奇的电光只能从一根导线传到电阻比它大的上面，而且必须从左边向右传导，当然导线不必是连续的。
哈蒙想知道电光最多能通过多少条导线，还想知道这样的方案有多少。
输入格式
第一行两个整数$n$和$type$。$type$表示数据类型
第二行$n$个整数表示电阻。
输出格式
第一行一个整数表示电光最多能通过多少条导线。
如果$type=1$则需要输出第二行，表示方案数，对$123456789$取模。
样例
样例输入：
5 1
1 3 2 5 4
样例输出：
3
4
数据范围与提示
对于$20\%$的数据，$nleqslant 10$；
对于$40\%$的数据，$nleqslant 1,000$；
对于另外$20\%$的数据，$type=0$；
对于另外$20\%$的数据保证最多能通过不超过$100$条导线；
对于$100\%$的数据$nleqslant 100000$，电阻值不超过$100000$。
题解
不输出方案数就是一个普通的$LCS$。
最经典的做法就是用树状数组做到$Theta(nlog n)$。
对于这道题，无非就是在树状数组统计时再加一个方案数即可。
时间复杂度：$Theta(nlog n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
const int mod=123456789;
int n,type;
int a[100001];
int tr[500000],val[500000],maxn;
pair<int,int> ans;
int lowbit(int x){return x&-x;}
void add(int x,int w,int sz)
{
for(int i=x;i<=500000;i+=lowbit(i))
{
if(w==val[i])tr[i]=(tr[i]+sz)%mod;
else if(w>val[i]){tr[i]=sz;val[i]=w;}
}
}
pair<int,int> ask(int x)
{
pair<int,int> res=make_pair(0,0);
for(int i=x;i;i-=lowbit(i))
if(val[i]>res.first)res=make_pair(val[i],tr[i]);
else if(val[i]==res.first)res.second=(res.second+tr[i])%mod;
return res;
}
int main()
{
scanf("%d%d",&n,&type);
add(1,0,1);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);a[i]+=2;
ans=ask(a[i]-1);
add(a[i],ans.first+1,ans.second);
maxn=max(maxn,a[i]);
}
ans=ask(maxn);
printf("%d
",ans.first);
if(type)printf("%d",ans.second);
return 0;
}
rp++