传送门：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

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; }

HDU_5141 LIS again(线段树 lis）

LIS again