题意一个序列的LIS为MAX， 求连续子序列的LIS为MAX的个数。
先求出LIS，记录以a[i]结尾的LIS的长度，以及LIS起始位置（靠右的起始位置）。
然后线性扫一遍，，线段树与树状数组的差距还是蛮大的，，线段树900+MS，险些超时，而树状数组仅仅400+MS
代码里注释部分为线段树做法。
1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 typedef unsigned long long ull; 16 typedef long long ll; 17 const int inf = 0x3f3f3f3f; 18 const double eps = 1e-8; 19 const int maxn = 1e5+10; 20 int seg[maxn<<2],pt[maxn<<2],a[maxn],vec[maxn],idx,n; 21 int pos1[maxn],pos2[maxn]; 22 void hash_() 23 { 24 sort(vec,vec+idx); 25 idx = unique(vec,vec+idx) - vec; 26 for (int i = 0; i < n ;i++) 27 a[i] = lower_bound(vec,vec+idx,a[i]) - vec + 1; 28 } 29 int ans,pp; 30 /* 31 void update(int l,int r,int pos,int x,int val,int s) 32 { 33 if (l == r) 34 { 35 if (val == seg[pos] && s > pt[pos]) 36 pt[pos] = s; 37 if (val > seg[pos]) 38 { 39 pt[pos] = s; 40 seg[pos] = val; 41 } 42 return ; 43 } 44 int mid = (l + r) >> 1; 45 if (x <= mid) 46 update(l,mid,pos<<1,x,val,s); 47 else 48 update(mid+1,r,pos<<1|1,x,val,s); 49 seg[pos] = max(seg[pos<<1],seg[pos<<1|1]); 50 if (seg[pos<<1] > seg[pos<<1|1]) 51 pt[pos] =pt[pos<<1]; 52 if (seg[pos<<1] < seg[pos<<1|1]) 53 pt[pos] = pt[pos<<1|1]; 54 if (seg[pos<<1] == seg[pos<<1|1]) 55 pt[pos] = max(pt[pos<<1],pt[pos<<1|1]); 56 } 57 void query(int l,int r,int pos,int ua,int ub) 58 { 59 if (ub < ua) 60 return ; 61 if (ua <= l && ub >= r) 62 { 63 if (ans < seg[pos]) 64 { 65 ans = seg[pos]; 66 pp = pt[pos]; 67 } 68 if (ans == seg[pos] && pp < pt[pos]) 69 pp = pt[pos]; 70 return ; 71 } 72 int mid = (l + r) >> 1; 73 if (ua <= mid) 74 query(l,mid,pos<<1,ua,ub); 75 if (ub > mid) 76 query(mid+1,r,pos<<1|1,ua,ub); 77 }*/ 78 inline int lowbit (int x) 79 { 80 return x & -x; 81 } 82 int c[2][maxn]; 83 void add(int x,int d,int s) 84 { 85 while (x <= idx) 86 { 87 if (c[0][x] < d) 88 { 89 c[0][x] = d; 90 c[1][x] = s; 91 } 92 if (c[0][x] == d && c[1][x] < s) 93 { 94 c[1][x] = s; 95 } 96 x += lowbit(x); 97 } 98 } 99 void query(int x) 100 { 101 while (x) 102 { 103 if (ans < c[0][x]) 104 { 105 pp = c[1][x]; 106 ans = c[0][x]; 107 } 108 if (ans == c[0][x] && pp < c[1][x]) 109 { 110 pp = c[1][x]; 111 } 112 x -= lowbit(x); 113 } 114 } 115 int dp[maxn]; 116 int main(void) 117 { 118 #ifndef ONLINE_JUDGE 119 freopen("in.txt","r",stdin); 120 #endif 121 while (~scanf ("%d",&n)) 122 { 123 //memset(seg,0,sizeof(seg)); 124 //memset(pt,0,sizeof(pt)); 125 memset(c,0,sizeof(c)); 126 idx = 0; 127 for (int i = 0; i < n; i++) 128 { 129 scanf("%d",a+i); 130 vec[idx++] = a[i]; 131 } 132 hash_(); 133 int LIS = 0; 134 for (int i = 0; i < n; i++) 135 { 136 ans = 0; 137 //query(1,n,1,1,a[i]-1); 138 query(a[i]-1); 139 dp[i] = ans + 1; 140 if (ans == 0) 141 pos1[i] = i; 142 else 143 pos1[i] = pp; 144 // update(1,n,1,a[i],dp[i],pos1[i]); 145 add(a[i],dp[i],pos1[i]); 146 LIS = max(dp[i],LIS); 147 } 148 int pre = n; 149 for (int i = n -1; i >= 0; i--) 150 { 151 if (dp[i] != LIS) 152 continue; 153 pos2[i] = pre-1; 154 pre = i; 155 } 156 ll cnt = 0; 157 for (int i = 0; i < n; i++) 158 { 159 if (dp[i] != LIS) 160 continue; 161 cnt += (ll)(pos1[i] + 1) * (pos2[i]+1-i); 162 } 163 printf("%I64d ",cnt); 164 } 165 return 0; 166 }