題干：

A sequence?S?= {s1,?s2, ...,?sn} is called?heapable?if there exists a binary tree?Twith?n?nodes such that every node is labelled with exactly one element from the sequence?S, and for every non-root node?si?and its parent?sj,?sj?≤?si?and?j?<?ihold. Each element in sequence?S?can be used to label a node in tree?T?only once.

Chiaki has a sequence?a1,?a2, ...,?an, she would like to decompose it into a minimum number of heapable subsequences.

Note that a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Input

There are multiple test cases. The first line of input contains an integer?T, indicating the number of test cases. For each test case:

The first line contain an integer?n?(1 ≤?n?≤ 105) — the length of the sequence.

The second line contains?n?integers?a1,?a2, ...,?an?(1 ≤?ai?≤?n).

It is guaranteed that the sum of all?n?does not exceed 2 × 106.

Output

For each test case, output an integer?m?denoting the minimum number of heapable subsequences in the first line. For the next?m?lines, first output an integer?Ci, indicating the length of the subsequence. Then output?Ci?integers?Pi1,?Pi2, ...,?PiCiin increasing order on the same line, where?Pij?means the index of the?j-th element of the?i-th subsequence in the original sequence.

Sample Input

4 4 1 2 3 4 4 2 4 3 1 4 1 1 1 1 5 3 2 1 4 1

Sample Output

1 4 1 2 3 4 2 3 1 2 3 1 4 1 4 1 2 3 4 3 2 1 4 1 2 2 3 5

Hint

題目大意：

用給出的數列a1,a2,a3....an構造二叉樹，滿足對于下標i和j，有i<j 且ai<=aj滿足ai是aj的父節點，問最少需要構造幾棵樹，并輸出每棵樹的元素個數和每個元素對應原數組的下標。

解題報告：

從前往后在線處理，用set維護可用節點的權值val和集合編號id和可用子節點數res，每一次貪心找到小于該值的最大的那個節點，插入到其子節點并且維護set中元素（也就是這個元素的根節點的res值），如果找不到該元素，就新開一個集合記錄就可以了。注意代碼姿勢、、、另外因為這題會有重復的val出現，所以需要multiset不能set。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int f[MAX]; struct Node {int val;int res;int id;Node(){}Node(int val,int res,int id):val(val),res(res),id(id){}bool operator<(const Node & b) const {return val < b.val;} } ; multiset<Node> ss; int main() {int t,n;cin>>t;while(t--) {int tot = 0;ss.clear();scanf("%d",&n);for(int x,i = 1; i<=n; i++) {scanf("%d",&x);auto it = ss.lower_bound(Node(x,0,0));if((int)ss.size()==0 || (it == ss.begin() && (*it).val > x)) { tot++;f[i] = tot;ss.insert(Node(x,2,f[i]));}else {if(it == ss.end()) --it;auto cur = *it;if(cur.val > x) --it;//找到第一個小于等于該值的。 cur = *it;ss.erase(it);f[i] = cur.id;cur.res--;ss.insert(Node(x,2,f[i]));if(cur.res > 0) ss.insert(cur);}}vector<int> vv[tot+1];for(int i = 1; i<=n; i++) {vv[f[i]].push_back(i);}printf("%d\n",tot);for(int i = 1; i<=tot; i++) {int up = (int)vv[i].size();printf("%d ",up);for(int j = 0; j<up; j++) {printf("%d%c",vv[i][j],j == up-1 ? '\n' :' ');}}}return 0 ; }

WA的部分：（這樣寫就WA了，，因為你沒有更新set中的值，只是在外面更改了cur）

else {if(it == ss.end()) --it;auto cur = *it;if(cur.val > x) --it;//找到第一個小于等于該值的。 cur = *it;f[i] = cur.id;cur.res--;ss.insert(Node(x,2,f[i]));if(cur.res == 0) ss.erase(it);}

AC代碼2：（set維護下標）

思路就是先從大到小排序，這樣就不需要考慮值的大小問題了，這樣只需要考慮下標要求的一個小于號，這一點我們可以用set來維護。想法是這樣的，相當于我們每次都插入這一個根結點，然后看set里面能否有節點可以當他的孩子節點，注意因為值是由大到小排好序的，所以set里面理論上拿哪一個值都不影響結果的正確性，但是因為這題還需要下標的關系，所以我們還需要二分查找一下合法的下標（因為我們能用的比我們大的值，要求下標也比我大，所以我需要lower或者upper查詢（其實這里都一樣，因為位置都是unique的），得到我可以用來當孩子結點的下標（一共可以選兩個當孩子，選哪個都無所謂，只需要下標滿足就可以了），如果實在沒有可以當下標的（it == ss.end()），那就只能break掉了，相當于只選擇一個當孩子節點。），并將該下標所屬的集合改成當前遍歷的那個數為根節點的集合。一次類推，最后并查集輸出答案就行了。其實還是相當于一個逆向思維，從葉子結點往上構造。但是較AC代碼1來說，這個比較難想。

相應的set中從大到小排序，pair從小到大排序，應該也可以做。

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; set<int> ss; PII p[MAX]; int f[MAX],tot,n; int main() {int t;cin>>t;while(t--) {scanf("%d",&n);ss.clear();tot=0;for(int i = 1; i<=n; i++) f[i] = i;for(int x,i = 1; i<=n; i++) {scanf("%d",&x);p[i] = pm(x,i);}sort(p+1,p+n+1,greater<PII>());for(int i = 1; i<=n; i++) {int pos = p[i].S;for(int j = 0; j<2; j++) {auto it = ss.lower_bound(pos);if(it == ss.end()) break;f[*it] = pos;ss.erase(it);}ss.insert(pos);}vector<int> vv[n+1];for(int i = 1; i<=n; i++) {if(f[i] != i) f[i] = f[f[i]];//這里因為每一個f[i]一定是前面的值，并且一定已經是更新好的，所以不需要并查集了，只需要一步壓縮就可以了。vv[f[i]].push_back(i);}for(int i = 1; i<=n; i++) {if(vv[i].size()) tot++;}printf("%d\n",tot);for(int i = 1; i<=n; i++) {if(vv[i].empty()) continue;int up = (int)vv[i].size();printf("%d ",up);for(int j = 0; j<up; j++) {printf("%d%c",vv[i][j],j == up-1 ? '\n' :' ');}}}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【ZOJ - 3963】Heap Partition （STLset，二叉树的性质，构造，贪心，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。