【bzoj 十连测】[noip2016十连测第八场]Problem B: 降雷皇（最长上升子序列+线段树|next数组）

Problem B: [noip2016十连测第八场]降雷皇

Time Limit: 10 Sec   Memory Limit: 512 MB
Submit: 39   Solved: 20
[ Submit][ Status][ Web Board]

Description

降雷皇哈蒙很喜欢雷电，他想找到神奇的电光。哈蒙有n条导线排成一排，每条导线有一个电阻值，神奇的电光只能从一根导线传到电阻比它大的上面，而且必须从左边向右传导，当然导线不必是连续的。哈蒙想知道电光最多能通过多少条导线，还想知道这样的方案有多少。

Input

第一行两个整数n和type。type表示数据类型
第二行n个整数表示电阻。
n<=100000,电阻值不超过100000

Output

第一行一个整数表示电光最多能通过多少条导线。
如果type=1则需要输出第二行，表示方案数，对123456789取模。

Sample Input

5 1
1 3 2 5 4

Sample Output

3
4

HINT

【题解】【最长上升子序列+next数组（好伐，其实本应该是线段树，然而数据辣么弱。。。）】
【O（n log n）求最长上升子序列，用堆来搞】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 123456789
using namespace std;
int f[100010],top,g[100010],ans[100010];
int a[100010],nxt[100010],p[100010],num[100010],tot;
int n,opt;
inline void add(int x,int y,int val)
{
    tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot; num[tot]=val;
}
inline void solve(int x,int val)
{
    if(x==1) {add(x,val,1); ans[x]++; return;}
    int cnt=0;
    for(int i=p[x-1];i!=-1;i=nxt[i])
     if(a[i]>=val) break;
      else cnt+=num[i],cnt%=mod;
    ans[x]+=cnt; ans[x]%=mod;
    add(x,val,cnt%mod);
}
inline void ask(int nm,int len,int x)
{
    int l=1,r=len,mid;
    while(l<=r)
     {
        mid=(l+r)>>1;
        if(f[mid]<x) l=mid+1;
         else r=mid-1;
     }
    f[l]=x; 
    if(opt==1) g[nm]=l,solve(l,x);
}
int main()
{
    //freopen("hamon9.in","r",stdin);
    int i,j;
    memset(p,-1,sizeof(p));
    memset(nxt,-1,sizeof(nxt));
    scanf("%d%d",&n,&opt);
    for(i=1;i<=n;++i)
     {
        int x;
        scanf("%d",&x);
        if(x>f[top]) 
         {
            f[++top]=x;
            if(opt==1) g[i]=top,solve(top,x);
          } 
         else ask(i,top,x);
     }
    if(opt==1) printf("%d\n%d\n",top,ans[top]%mod);
    else printf("%d\n",top);
    return 0;
}