http://acm.hdu.edu.cn/showproblem.php?pid=2227&&树状数组+离散化+dp

http://acm.hdu.edu.cn/showproblem.php?pid=2227

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define N 100005
#define M  1000000007
using namespace std;
typedef long long L;
int kp[N];
int a[N];
int s[N];
int n;
int tot;
inline int lowbit(int x)
{return x&(-x);}
void update(int x,int v)
{ 
	while(x<N)
   {  s[x]+=v;
	 if(s[x]>=M)
		 s[x]%=M;
	  x+=lowbit(x);
   }
}
L Quary(int x)
{  L sum=0;
   while(x>0)
   { sum+=s[x];
     if(sum>=M)
		 sum%=M;
     x-=lowbit(x);
   }
   return sum;
}
int lisan(int x)
{ int l=1,r=tot;
  while(l<=r)
   {  int mid=(l+r)>>1;
     if(a[mid]==x) return mid;
	 else if(a[mid]>x) r=mid-1;
	 else if(a[mid]<x) l=mid+1;
   }
   return -1;
}

int main()
{  
	while(~scanf("%d",&n))
	{   memset(s,0,sizeof(s));
		tot=0;
		for(int i=1;i<=n;++i)
			{
				scanf("%d",&kp[i]);
		        a[i]=kp[i];
		    }
		 sort(a+1,a+n+1);
		 for(int i=1;i<=n;++i)
		  if(i==1||(a[i]!=a[i-1]))
			  a[++tot]=a[i];
		 L res=0;
		  for(int i=1;i<=n;++i)
		  { int num=lisan(kp[i]);
		    L k=Quary(num);
			res+=k+1;
			if(res>=M)
			   res%=M;
			update(num,k+1);
		  }
		  printf("%d\n",res);
}return 0;
}
//这道题算是树状数组题中比较难的一个题，不但需要离散化思想还要有动态规划思想
//首先说一下这一题的题意：给你一串数让你求其中有多少个非递减子串。这里用到树状数组
//主要是用来统计第i个位置共找到多少个非递减子串。动态规划思想dp[i]={sum[dp[1]......dp[j] j<i,a[j]<=a[i]]}
//dp[1]=0+1;
//dp[2]=dp[1]+1;
//dp[3]=dp[1]+dp[2]+1;
//下面在说一下为什么要离散化，因为给定串中的数最大不超过2^31,这样不能进行树状数组的操作，因此需要把所有的数映射到1……n这个区间。。。