首页 > 代码库 > 501D Misha and Permutations Summation 数据结构+打脸题
501D Misha and Permutations Summation 数据结构+打脸题
都快退役啦,小白书上的例题还不会。
给出一个序列S,则S的字典序为 sigma(dp[i] * (n-i)!) (1 <= i <= n)。dp[i] 表示[i,n]这一段S的子序列内比num[i]小的数字的个数。
对于两个序列A,B,(ord(A) + ord(B))%n!可以转化成 sigma( (A_dp[i] + B_dp[i] + (A_dp[i+1]+B_dp[i+1])/(n-i+1))%(n-i+1) )( 1 <= i <= n ,可以认为dp[n+1] == 0)。
解码部分和编码部分为逆操作,详见代码。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #include <ctime> #include <iomanip> #pragma comment(linker,"/STACK:1024000000"); #define EPS (1e-6) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 1000000007 #define mod 1000000007 /** I/O Accelerator Interface .. **/ #define g (c=getchar()) #define d isdigit(g) #define p x=x*10+c-'0' #define n x=x*10+'0'-c #define pp l/=10,p #define nn l/=10,n template<class T> inline T& RD(T &x) { char c; while(!d); x=c-'0'; while(d)p; return x; } template<class T> inline T& RDD(T &x) { char c; while(g,c!='-'&&!isdigit(c)); if (c=='-') { x='0'-g; while(d)n; } else { x=c-'0'; while(d)p; } return x; } inline double& RF(double &x) //scanf("%lf", &x); { char c; while(g,c!='-'&&c!='.'&&!isdigit(c)); if(c=='-')if(g=='.') { x=0; double l=1; while(d)nn; x*=l; } else { x='0'-c; while(d)n; if(c=='.') { double l=1; while(d)nn; x*=l; } } else if(c=='.') { x=0; double l=1; while(d)pp; x*=l; } else { x=c-'0'; while(d)p; if(c=='.') { double l=1; while(d)pp; x*=l; } } return x; } #undef nn #undef pp #undef n #undef p #undef d #undef g using namespace std; int st[800100]; int num[200100]; int ans[200100]; int Update(int site,int l,int r,int x,int val) { if(l == r) return st[site] = val; int mid = (l+r)>>1; if(x <= mid) Update(site<<1,l,mid,x,val); else Update(site<<1|1,mid+1,r,x,val); return st[site] = st[site<<1] + st[site<<1|1]; } int Query(int site,int L,int R,int l,int r) { if(L == l && R == r) return st[site]; int mid = (L+R)>>1; if(r <= mid) return Query(site<<1,L,mid,l,r); if(mid < l) return Query(site<<1|1,mid+1,R,l,r); return Query(site<<1,L,mid,l,mid) + Query(site<<1|1,mid+1,R,mid+1,r); } int BS(int s,int e,int x) { int ans,mid,site,n = e; while(s <= e) { mid = (s+e)>>1; ans = Query(1,1,n,1,mid); if(ans <= x) s = mid+1; else site = mid,e = mid-1; } return site; } int main() { int n,i,j,site; while(scanf("%d",&n) != EOF) { memset(ans,0,sizeof(ans)); for(i = 1;i <= n; ++i) scanf("%d",&num[i]),++num[i]; memset(st,0,sizeof(st)); for(i = n;i >= 1; --i) { Update(1,1,n,num[i],1); ans[i] += Query(1,1,n,1,num[i])-1; } for(i = 1;i <= n; ++i) scanf("%d",&num[i]),++num[i]; memset(st,0,sizeof(st)); for(i = n;i >= 1; --i) { Update(1,1,n,num[i],1); ans[i] += Query(1,1,n,1,num[i])-1; } for(i = n;i >= 1; --i) if(ans[i] >= n-i+1) ans[i-1] += 1,ans[i] %= (n-i+1); for(i = 1;i <= n; ++i) { printf("%d%c",(site = BS(1,n,ans[i]))-1,i == n ? '\n' : ' '); Update(1,1,n,site,0); } } return 0; }
501D Misha and Permutations Summation 数据结构+打脸题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。