Heap Partition Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge A sequence S = {s1, s2, ..., sn} is called heapable if there exists a binary tree T with 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 < i hold. 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, ..., PiCi in 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 Author: LIN, Xi Source: The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple /** 题目：Heap Partition 链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5595 题意：给一个序列，将其划分成尽量少的序列，使每一个序列满足按照顺序构造二叉树，父母的值<=孩子的值。 思路：对初始序列讨论，如果某个值a[i],位置为i;要插入到别的二叉树上，那么就要在前面找一个a[j]<=a[i]且孩子少于两个的最接近a[i]的值a[j],位置为j。 那么j的孩子加一。 如果j的孩子有两个，那么以后不能再让别人成为它的孩子。如果找不到，那么i这个位置的值作为一颗新的二叉树的根。 我们要维护value，所属二叉树编号，该节点的孩子数。所以用一个set来维护。具体需要注意地方看下面反思。 反思：当时我没有做出来，没有考虑到set把重复的给去掉了。我一直以为set是按照内容来判重的。 原来是通过排序规则来判重（我傻了），所以如果排序规则只判断了return value<k.value； 那么只要value=k.value;这个就会被判重去掉。哪怕cnt,value,last不同。 解决这种问题，要么用multiset；要么set的排序规则所有情况都排一下序，为了保证唯一，所以新增一个id表示这个值在初始序列的下标位置。 */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #include<set> #include<cmath> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int inf = 0x3f3f3f3f; const int maxn = 1e5+100; struct node { int value; int cnt; int last; node(){} node(int v,int c,int l):value(v),cnt(c),last(l){} bool operator < (const node&k) const{ return value<k.value; } }t; vector<int> v[maxn]; multiset<node>se; int a[maxn]; int main() { int T, n; cin>>T; while(T--) { scanf("%d",&n); for(int i = 0; i<n; i++){ scanf("%d",&a[i]); } se.clear(); for(int i = 0; i <= n; i++){ v[i].clear(); } int ans = 0; t.value = a[0]; t.cnt = 0; t.last = 0; se.insert(t); ans = 1; v[t.last].push_back(0); multiset<node>::iterator it; for(int i = 1; i < n; i++){ t.value = a[i]; it = se.upper_bound(t); if(it==se.begin()){ t.cnt = 0; t.last = i; t.value = a[i]; se.insert(t); v[i].push_back(i); ans++; }else { it--; t = *it; t.cnt++; se.erase(it); if(t.cnt<2){ se.insert(t); } t.value = a[i]; t.cnt = 0; v[t.last].push_back(i); se.insert(t); } } printf("%d ",ans); for(int i = 0; i < n; i++){ int len = v[i].size(); if(len==0) continue; printf("%d",len); for(int j = 0; j < len; j++){ printf(" %d",v[i][j]+1); } printf(" "); } } return 0; } /* struct node { int id; int value; int cnt; int last; node(){} node(int i,int v,int c,int l):id(i),value(v),cnt(c),last(l){} bool operator < (const node&k) const{ if(value!=k.value) return value<k.value; if(cnt!=k.cnt) return cnt<k.cnt; if(last!=k.last) return last<k.last; return id<k.id; } }t; vector<int> v[maxn]; set<node>se; int a[maxn]; int main() { int T, n; cin>>T; while(T--) { scanf("%d",&n); for(int i = 0; i<n; i++){ scanf("%d",&a[i]); } se.clear(); for(int i = 0; i <= n; i++){ v[i].clear(); } int ans = 0; t.value = a[0]; t.cnt = 0; t.last = 0; t.id = 0; se.insert(t); ans = 1; v[t.last].push_back(0); set<node>::iterator it; for(int i = 1; i < n; i++){ t.value = a[i]; t.id = inf; t.last = inf; t.cnt = inf; it = se.upper_bound(t); if(it==se.begin()){ t.cnt = 0; t.last = i; t.value = a[i]; t.id = i; se.insert(t); v[i].push_back(i); ans++; }else { it--; t = *it; t.cnt++; se.erase(it); if(t.cnt<2){ se.insert(t); } t.id = i; t.value = a[i]; t.cnt = 0; v[t.last].push_back(i); se.insert(t); } } printf("%d ",ans); for(int i = 0; i < n; i++){ int len = v[i].size(); if(len==0) continue; printf("%d",len); for(int j = 0; j < len; j++){ printf(" %d",v[i][j]+1); } printf(" "); } } return 0; } */