题意:求1-k的排列中第n大的序列,题目给出n的计算方法:n = si*(k-1)+s2*(k-2)...+sk*0!已知si
分析:
si的含义是剩下没用的数中第(si+1)大的数,用线段树,0,1表示处理情况
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <complex> #include <cassert> #include <utility> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; typedef pair<int,int> PII; typedef long long ll; #define lson l,m,rt<<1 #define pi acos(-1.0) #define rson m+1,r,rt<<1|1 #define All 1,N,1 #define read freopen("in.txt", "r", stdin) const ll INFll = 0x3f3f3f3f3f3f3f3fLL; const int INF= 0x7ffffff; const int mod = 1000000007; int sum[50010*4],n; void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt){ if(l==r){ sum[rt]=1; return; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt); } int query(int p,int l,int r,int rt){ if(l==r){ sum[rt]=0; return l; } int m=(l+r)>>1; int tmp; if(p<=sum[rt<<1]) tmp=query(p,lson); else tmp=query(p-sum[rt<<1],rson); pushup(rt); return tmp; } int main() { int t,a; scanf("%d",&t); while(t--){ scanf("%d",&n); build(1,n,1); for(int i=0;i<n;++i){ scanf("%d",&a); if(i==n-1) printf("%d\n",query(a+1,1,n,1)); else printf("%d ",query(a+1,1,n,1)); } } return 0; }
原文:http://www.cnblogs.com/zsf123/p/4909884.html