题解 CF1208D 【Restore Permutation】

foreverlasting

2019-08-30 17:05:14

Solution

[推销博客](https://foreverlasting1202.github.io/2019/08/27/CF1208%E9%A2%98%E8%A7%A3/) ### D Restore Permutation 题意:未知一个长度为$n$的排列,对于位置$i$,假设在上面的数是$a_i$,给出$\sum_{j<i,a_j<a_i} a_j$,求这个排列。$1\leq n\leq 2\ast 10^5$。 做法:从后往前递推,显然最后一个未知的都可以二分出来,只需要动态维护前缀和,树状数组即可。复杂度$O(nlog^2n)$。 code: ```cpp //2019.8.24 by ljz //email [email protected] //if you find any bug in my code //please tell me #include<bits/stdc++.h> using namespace std; #define res register int #define LL long long #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f #define unl __int128 #define eps 5.6e-8 #define RG register #define db double #define pc(x) __builtin_popcount(x) typedef pair<int,int> Pair; #define mp make_pair #define fi first #define se second #define pi acos(-1.0) #define pb push_back #define ull unsigned LL #define gc getchar //inline char gc() { // static char buf[100000],*p1,*p2; // return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; //} inline int read() { res s=0,ch=gc(); while(ch<'0'||ch>'9')ch=gc(); while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc(); return s; } //inline int read() { // res s=0,ch=gc(),w=1; // while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();} // while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc(); // return s*w; //} inline LL Read() { RG LL s=0; res ch=gc(); while(ch<'0'||ch>'9')ch=gc(); while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc(); return s; } //inline LL Read() { // RG LL s=0; // res ch=gc(),w=1; // while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();} // while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc(); // return s*w; //} //inline void write(RG unl x){ // if(x>10)write(x/10); // putchar(int(x%10)+'0'); //} inline void swap(res &x,res &y) { x^=y^=x^=y; } //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //clock_t start=clock(); //inline void ck(){ // if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0); //} const int N=2e5+10; namespace MAIN{ int n; #define lowbit(x) (x&-x) LL tr[N]; LL a[N]; inline void modify(const res &x,const res &y){ for(res i=x;i<=n;i+=lowbit(i))tr[i]+=y; } inline LL query(const res &x){ RG LL ret=0; for(res i=x;i;i-=lowbit(i))ret+=tr[i]; return ret; } int A[N]; inline void MAIN(){ // printf("%d\n",0^2^4^11); // printf("%d\n",19^55^11^39^32^36^4^52); n=read(); for(res i=1;i<=n;i++)a[i]=Read(),modify(i,i); for(res i=n;i;i--){ res l=1,r=n,ret=0; while(l<=r){ res mid=(l+r)>>1; if(query(mid-1)<=a[i])l=mid+1,ret=mid; else r=mid-1; } A[i]=ret; modify(ret,-ret); } for(res i=1;i<=n;i++)printf("%d ",A[i]); } } int main(){ // srand(19260817); // freopen("signin.in","r",stdin); // freopen("signin.out","w",stdout); MAIN::MAIN(); return 0; } ```