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

liuhongyu

　　http://acm.hdu.edu.cn/showproblem.php?pid=2227
#include<iostream>#include<cstdio>#include<string.h>#include<algorithm>#define N 100005#define M  1000000007using 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);a=kp;}sort(a+1,a+n+1);for(int i=1;i<=n;++i)if(i==1||(a!=a[i-1]))a[++tot]=a;L res=0;for(int i=1;i<=n;++i){ int num=lisan(kp);L k=Quary(num);res+=k+1;if(res>=M)res%=M;update(num,k+1);}printf("%d\n",res);}return 0;}//这道题算是树状数组题中比较难的一个题，不但需要离散化思想还要有动态规划思想//首先说一下这一题的题意：给你一串数让你求其中有多少个非递减子串。这里用到树状数组//主要是用来统计第i个位置共找到多少个非递减子串。动态规划思想dp={sum[dp[1]......dp[j] j<i,a[j]<=a]}//dp[1]=0+1;//dp[2]=dp[1]+1;//dp[3]=dp[1]+dp[2]+1;//下面在说一下为什么要离散化，因为给定串中的数最大不超过2^31,这样不能进行树状数组的操作，因此需要把所有的数映射到1……n这个区间。。。