HDU_5141 LIS again(線段樹 lis）

傳送門：HUD_5141

LIS again

Problem Description A numeric sequence of ai is ordered if a1. Let the subsequence of the given numeric sequence (a1,a2,…,aN) be any sequence (ai1,ai2,…,aiK), where 1≤i1. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, eg. (1, 7), (3, 4, 8) and many others.
S[ i , j ] indicates ( ai,ai+1,ai+2,…,aj) .
Your program, when given the numeric sequence (a1,a2,…,aN), must find the number of pair ( i, j) which makes the length of the longest ordered subsequence of S[ i , j ] equals to the length of the longest ordered subsequence of (a1,a2,…,aN).
Input Multi test cases (about 100), every case occupies two lines, the first line contain n, then second line contain n numbers a1,a2,…,aN separated by exact one space.
Process to the end of file.

[Technical Specification]
1≤n≤100000
0≤ai≤1000000000
Output For each case，.output the answer in a single line.
Sample Input

3
1 2 3
2
2 1

Sample Output

1
3

題意：給你一串數列，其最長遞增序列為lis，統計遞增序列長度等於lis的區間的數目。

思路：線段樹維護以i結尾的最長遞增序列，且要求起點盡量靠右。

代碼：

#include
#include
#include
#include
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
typedef long long LL;
const int N=100010;

int a[N],b[N];
int dp[N];
int sta[N],en[N];
int len,st;
struct node{
    int l,r;
    int len,sta;
}tree[N<<2];


void pushup(int p)
{
    if(tree[ls(p)].len>tree[rs(p)].len)
    {
        tree[p].len=tree[ls(p)].len;
        tree[p].sta=tree[ls(p)].sta;
    }
    else if(tree[rs(p)].len>tree[ls(p)].len)
    {
        tree[p].len=tree[rs(p)].len;
        tree[p].sta=tree[rs(p)].sta;
    }
    else
        tree[p].sta=max(tree[ls(p)].sta,tree[rs(p)].sta);
}

void build(int p,int l,int r)
{
    tree[p].l=l;tree[p].r=r;
    tree[p].len=-1;
    tree[p].sta=-1;
    if(l==r)
        return;
    int m=(l+r)>>1;
    build(ls(p),l,m);
    build(rs(p),m+1,r);
}

void update(int p,int pos,int len,int st)
{
    if(tree[p].l==tree[p].r)
    {
        if(tree[p].len==len&&tree[p].sta>1;
    if(pos<=m) update(ls(p),pos,len,st);
    else update(rs(p),pos,len,st);
    pushup(p);
}


void query(int p,int l,int r)
{
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        if(tree[p].len>len)
        {
            len=tree[p].len;
            st=tree[p].sta;
        }
        else if(tree[p].len==len&&st>1;
    if(l<=m) query(ls(p),l,r);
    if(r>m) query(rs(p),l,r);
}


int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        LL ret=0;
        int cnt;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
            b[i]=a[i];
        }
        if(n==1)
        {
            printf("1\n");
            continue;
        }
        sort(b+1,b+1+n);
        cnt=unique(b+1,b+1+n)-(b+1);
        dp[1]=sta[1]=1;
        build(1,1,cnt);
        int mpp;
        int lest=-1;
        for(int i=1;i<=n;i++)
        {
            len=st=-1;
            mpp=lower_bound(b+1,b+1+cnt,a[i])-b;
            if(mpp==1)
            {
                dp[i]=1;
                sta[i]=i;
            }
            else
                query(1,1,mpp-1);
            if(st==-1)
            {
                dp[i]=1;
                sta[i]=i;
            }
            else
            {
                dp[i]=len+1;
                sta[i]=st;
            }
            //cout<=1;i--)
        {
            if(dp[i]==lest)
            {
                en[i]=last-1;
                last=i;
            }
        }
        for (int i=1;i<=n;++i)
        {
            if (dp[i]==lest)
                ret+=(LL)sta[i]*(LL)(en[i]-i+1);
        }
        printf("%I64d\n", ret);
    }
    return 0;
}