CF1208D Restore Permutation

題意：

現(xiàn)在有一個從1到n的一個全排列,但是你不知道這個排列到底是什么,但是你有一個sum[i],其中sum[i]表示${\sum }_{j=1}^{i?1}(a_j<a_i)?a_j:0$,現(xiàn)在給你sum數(shù)組,讓你求出這個排列a

題解：

如果sum[i]為0，說明在位置i前面的所有數(shù)都比他大，因為排列a是1到n的全排列，也就是說對于數(shù)字1來說，其sum[i]一定為0，且在數(shù)字1位置后面的所有數(shù)的sum[i]一定不為0,因為有更小的1在前面。也就是說sum中最后一個0的位置，就是1的位置，找到1之后，我們可以將1刪除，如果1的位置是pos，那么pos+1到n的所有數(shù)都要減1，此時數(shù)字2的sum就會是下一個最右邊的0的位置。也就是說每次找最右邊0的位置pos，那就是第i個數(shù)，然后將[pos+1,n]區(qū)間內(nèi)所有數(shù)減i，相當于把第i個數(shù)給去掉了
線段樹區(qū)間修改，區(qū)間查詢即可維護

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=4e5+9; #define int long long int a[maxn]; struct node{int l,r;int minn;int lazy; }tr[maxn<<1]; void pushup(int rt){tr[rt].minn=min(tr[rt<<1].minn,tr[rt<<1|1].minn); } void pushdown(int rt){if(tr[rt].lazy){tr[rt<<1].minn+=tr[rt].lazy;tr[rt<<1].lazy+=tr[rt].lazy;tr[rt<<1|1].minn+=tr[rt].lazy;tr[rt<<1|1].lazy+=tr[rt].lazy;tr[rt].lazy=0;}return ; } void build(int rt,int l,int r){tr[rt].l=l;tr[rt].r=r;if(l==r){tr[rt].minn=a[l];return ;}int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt); } ll query(ll rt,ll l,ll r){if(tr[rt].l==tr[rt].r)return tr[rt].l;pushdown(rt);if(tr[rt<<1|1].minn==0)return query(rt<<1|1,l,r);else if(tr[rt<<1].minn==0)return query(rt<<1,l,r); } void update(int rt,int l,int r,int val){if(tr[rt].l>r||tr[rt].r<l)return ;if(tr[rt].l>=l&&tr[rt].r<=r){tr[rt].minn+=val;tr[rt].lazy+=val;return ;}pushdown(rt);update(rt<<1,l,r,val);update(rt<<1|1,l,r,val);pushup(rt); } int p[maxn]; signed main() {//rd_test();int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];build(1,1,n);for(int i=1;i<=n;i++){int pos=query(1,1,n);p[pos]=i; // printf("pos=%d\n",pos);update(1,pos,pos,4e10+9);update(1,pos+1,n,-1*i);}for(int i=1;i<=n;i++){cout<<p[i]<<" ";}cout<<endl;return 0;//Time_test(); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的CF1208D Restore Permutation的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。