Find the nondecreasing subsequences
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1182 Accepted Submission(s): 408
Problem Description
How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, ...., sn} ? For example, we assume that S = {1, 2, 3}, and you can find seven nondecreasing subsequences, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
Input
The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, ...., sn}, 1 <= n <= 100000, 0 <= si <= 2^31.
Output
For each test case, output one line containing the number of nondecreasing subsequences you can find from the sequence S, the answer should % 1000000007.
Sample Input
3
1 2 3
Sample Output
7
Author
8600
Recommend
lcy
題意：
給你一個有序序列, 求有多少個不下降子序列
結果對 10^9+7 取模
注意：不下降【相等也可以】
每個元素本身也算一個
算法：離散化+樹樁數組+簡單dp 思想
思路：
這道題目的數據比較大 1 <= n <= 100000 0 <= si <= 2^31 如果數據比較小直接 DP就可以解決了。當然這些比賽的時候都沒有想到, 找題解的時候突然看到了奮斗青春 的 DP 思想，然後去神牛 Maxtri67 那兒學了下什麼是離散化 , 後來kuangbin 大神又給我說了另外一種離散化的思想的兩種實現方法。
012
我們先分析一下假設數據比較小的情況：
dp[a[j]]=sum( dp[a[i]] )+1; (i>=1 && i<j && a[j]>=a[i]) //單獨的a[j]也算一個
//a[] 存序列中的元素值, dp[i] 表示值為 i 結尾形成的子序列的個數
int ans = 0; // 暫且不考慮對 10^9+7 取模的情況
for(int i = 1; i <= n; i++)
{
for(int j = 1; j < i; j++) //如果 a[i] 出現在 a[j] 後面而又不比 a[j] 小, 那麼可以直接加在 a[j] 後面,形成新的子序列
{
if(a[i] >= a[j])
dp[a[i]] += dp[a[j]];
}
dp[a[i]]++; //自己單獨也是一個
ans += dp[a[i]];
}
printf("%d\n", ans);
但是 a[i] 的值最大到了 2^31 , 明顯不可能開一個這麼大的數組
如是需要離散化一下, 把結果映射到 1-n 這個區間,等下我會詳細的解釋下我對這題的離散化的理解, 第一個離散化題目Orz
說的這麼高深, 其實一般的離散化簡單排序下再做些小處理就可以了。
現在我們先拋下離散化, 看下這個 DP 的結構, 就是對前面滿足條件的求和有木有, 考慮到 n 比較大, 更新的次數比較多, 那麼我們是否可以想到一個快速求和的方法, 樹狀數組正好能快速求一段序列的和的, 那麼我們是否可以把這道題目往樹樁數組上想。
至於關於樹狀數組的理解, 我是看的 lrj 《訓練指南》P194-P196 上的介紹了,網上也有很多資料,自認為還沒有辦法說的特別清楚,這裡不再仔細介紹, 你只需要記住樹樁數組能夠快速的求一段序列的和,並且能夠快速更新每一個點的值那麼就可以往下看了。
推薦樹狀數組入門題目：hdu 1166 敵兵布陣 我的代碼：點擊打開鏈接
如果實在不了解的：先記住下面這句話, 然後再繼續往下看。看過樹狀數組的可以直接忽略。。。
樹樁數組的下標從 1 開始到 N , 數組 a[] 記錄序列的值 c[i] 記錄以 a[i] 結束的某段 a[j]到 a[i] 的連續和
ＰＳ：具體是那一段，這裡我一句兩句也說不清楚，先記住好了，對下面的思想的分析沒有太大的影響
有兩個函數： add(int i , int val) // 把a[i] 更新加上 val ,同時更新相應的一段 c[]
sum(int i) // 求 a[1] +a[2] +...+ a[i] 的連續和
如何轉換成樹樁數組求解？
什麼是離散化？關於這題如何離散化？
開始准備分開寫，但是感覺說不清楚，就先放一起了。有興趣的童鞋可以先去看下 Maxtri67 離散化的筆記 離散化
這題求的是不下降子序列的個數。
也就是說符合要求的序列元素的後面的一個的值總是大於或等於前一個元素的【廢話一句可以忽略Orz】
那麼我們可以先對輸入的元素 a[i] 按照從小到大做一個排序處理。
這樣排序後前面的數字肯定小於等於後面的數字是不是。那麼依次遍歷的時候,直接把當前的數字插入到前面已經處理過的數字所形成所
有子序列後面那麼就可以形成新的子序列了。那麼排序後,我們只要弄個數組把每一個以 a[i] 結尾的對應的序列個數記錄
下來就可以了, 【順序打亂了,後面會說怎麼處理,這裡先不管】假設記錄個數的數組是 num[] 那麼最後就把每一個 num[] 相加是不是就是最後
的結果了。中間注意下取模。
好像有點樹狀數組的感覺了，不過還是沒什麼用的樣子，繼續往下看。。。
但是這樣嵌入了離散化的思想：把原來的應該開到 2^31 的數組 dp [] 優化到了長度為 100000 num[] 直接映射到 1 到 N 求解
又裝逼了, 不就是個排序處理還說的這麼高深。
下面以類似於樣例中的已經排序好了的解釋下上一段關於離散化的思想：
3
100 200 300
對於第一個數 100 ：以 1 結尾形成一個不下降子序列就是他自己 num[1] = 1
對於第二個數 200 ：以 2 結尾形成的不下降子序列： (1) 加到 1 後面 num[2] += num[1] = 1
(2) 自己單獨成一個子序列 num[2]++ = 2
對於第三個數 300： 以 3 結尾形成的不下降子序列： (1) 加到前面形成的子序列的後面 num[3] = num[1] + num[2] = 3
(2) 自己單獨成一個 num[3]++ = 4
那麼最後的結果就是 7
是否體會到原來要開到的數組 dp[300]， 現在 num[3] 就解決了, 這就是傳說中的離散化。。。
PS :其實這個思路並不嚴謹,稍微改下數據就會有很多錯誤的地方，只是為了清楚離散化就先用了。。。嚴謹看後面。
因為我排序後,忽略了每一個元素在原來的序列中出現的位置就直接把大的插入到了小的後面。
這樣就會陷入這樣一個誤區：變成了子序列的個數 = 元素個數的非空子集個數，照成最後的結果變成 pow(2, n) - 1而這樣是錯的。
解決這樣的先後處理問題就必須用到樹狀數組的思想，先不管這個問題，直接考慮對於這題如何離散化。
對於這題如何離散：
離散化就是排序下，再隨便處理下就 O 了。
思路一：
定義一個結構體, 記錄每一個元素的初始下標 index 和元素的值 value
等我先寫完思路了再具體介紹為何還要定義下標【這裡先提一下, 方便後面嵌入樹狀數組】
對元素的值 value 從小到大排序【前面已經分析過】
對於 value 一樣的按照 index由小到大排序 【這一點下面會解釋】
還是以上面的 num[] 數組記錄的思想來解釋：
3
1 3 3
如果只對 value 排序
那麼排序後原來的元素的下標的排列可能會出現兩種情況：
情況一： 1 2 3 【這樣是正確的】
num[1] = 1
num[2] = num[1]+1 = 1 + 1 = 2
num[3] = num[1] + num[2] + 1 = 1+2 +1 = 4
最後的結果為 1 + 2 + 4 = 7
情況二： 1 3 2 【錯誤】
num[1] = 1
num[2] = num[1] + 1 = 1 + 1 = 2
num[3] = num[1] + 1 = 2
最後的結果為 1 + 2 + 2 = 5 WA
為什麼對於情況一的 num[3] 要加上 num[2] 但是情況二的 num[3] 卻沒有 ？
這裡就要說下為何用樹樁數組? 如何用樹樁數組了?,而不是直接的簡單相加就好了.
再次強調一下樹樁數組的作用:快速更新每一個元素的值, 快速求出任意一段連續子序列的和。
為了應用於樹樁數組：每次求 num[i] 應該轉換成 num[i] = num[1] + ... +num[i-1] +1
從而借用樹狀數組快速求前綴和的思想求出 num[i] ,
但是如果僅僅是這樣，好像無法體現到樹樁數組的優越性而且也陷入了上面解釋離散化的映射時出現的誤區
不要忘了，樹樁數組還有一個優越性：快速更新每個元素的值。
如果排序後,我們遍歷到第 i 個元素時求的不是 num[i] 而是 a[i] 原來對應的編號 index 的 num[index] 來記
錄以 a[i] 結尾的不下降子序列的個數是不是就解決了前面的誤區問題。
直接對元素的 a[i] 原來未排序時的編號做 num 處理。
3
1 7 5
排序後： 1 5 7
對應原來的編號：1 3 2
依次遍歷排序後的元素： 對於元素 1 ：num[1] = 1;
對於元素 5 ：num[3] = num[1]+num[2] + 1 = 1+0 + 1 = 2
對於元素 2 ：num[2] = num[1] + 1 = 1 + 1 = 2
ans = num[1]+num[2]+num[3] = 5
這樣就解決了元素出現的先後問題,而且也是離散化後把要處理的問題映射到了 1 到 N 這個區間,
但是還是沒有說明元素的值一樣卻要對出現的順序也排序。
其實到了這裡，自己也應該想明白了，我還是再寫下好了。
注意到：處理的過程不斷的更新相應的 num[] 對應於樹樁數組中快速更新元素值的思想。
num[index] = num[1]+...+num[index-1] + 1對應於樹狀數組快速求前綴和的思想。
對於情況一: 排序前後並未影響原來的順序,所以可以直接把大的元素插在前面所有出現過的元素後面形成新的不下降子序列.
對於情況二: 加入了樹狀數組的思想其實是這樣算的
num[1] = 1;
num[3] = num[1]+num[2] + 1 = 1+0+1 = 2;
num[2] = num[1] + 1 = 2 ;
ans = 1+2+2 = 5
所以：對於一樣的元素, 先出現的一定要先處理
思路二：
不用定義結構體, 按照元素的值從小到大排序 ,然後對於重復元素的下標定義成一樣的就可以了
比如說樣例：
3
1 3 3
排序後的下標是： 1 2 2
而不是原來的：1 2 3 那麼就不用糾結什麼元素一樣的時候,是先排前面的還是後面的問題了。
這樣有兩種方法處理, 但是效率沒有思路一的高。具體看程序實現。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 100000+10;
const int mod = 1000000007;
int c[maxn];
int n;
struct Node{
int value; //對應元素的值
int index; //元素初始編號
}node[maxn];
bool cmp(Node a, Node b) //先按元素值從小到大排序,元素值一樣，再按照 編號從小到大排序
{
if(a.value == b.value) return a.index < b.index;
else return a.value < b.value;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int index, int value) //快速更新 ：節點 index 增加 value
{
while(index <= n)
{
c[index] = (c[index]+value) % mod;
index += lowbit(index);
}
}
int sum(int index) //快速求前綴和
{
int ret = 0;
while(index > 0)
{
ret = (ret+c[index])%mod;
index -= lowbit(index);
}
return ret; //勿忘
}
int main()
{
while(scanf("%d", &n) != EOF)
{
memset(node, 0, sizeof(node));
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; i++)
{
scanf("%d", &node[i].value);
node[i].index = i;
}
sort(node+1, node+n+1, cmp); //排序
int tmp = 0;
for(int i = 1; i <= n; i++)
{
tmp = sum(node[i].index)+1; //求處理過後的前綴和相當於思路中的 num[index]
tmp %= mod;
add(node[i].index, tmp); // 相當於思路中給 num[index]增加 tmp
}
printf("%d\n", sum(n));
}
return 0;
}
