锐客网

  1. 首页 > it技术 > >

Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) D. Restore Permutation(线段树)


time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
An array of integers p1,p2,…,pn is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: [3,1,2],[1],[1,2,3,4,5] and [4,3,1,2]. The following arrays are not permutations: [2],[1,1],[2,3,4].
There is a hidden permutation of length n.
For each index i, you are given si, which equals to the sum of all pj such that j Input
The first line contains a single integer n (1≤n≤2?105) — the size of the permutation.
The second line contains n integers s1,s2,…,sn (0≤si≤n(n?1)2).
It is guaranteed that the array s corresponds to a valid permutation of length n.
Output
Print n integers p1,p2,…,pn — the elements of the restored permutation. We can show that the answer is always unique.
Examples
input
Copy

3 0 0 0

output
Copy
3 2 1

input
Copy
2 0 1

【Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) D. Restore Permutation(线段树)】output
Copy
1 2

input
Copy
5 0 1 1 1 10

output
Copy
1 4 3 2 5

Note
In the first example for each i there is no index j satisfying both conditions, hence si are always 0.
In the second example for i=2 it happens that j=1 satisfies the conditions, so s2=p1.
In the third example for i=2,3,4 only j=1 satisfies the conditions, so s2=s3=s4=1. For i=5 all j=1,2,3,4 are possible, so s5=p1+p2+p3+p4=10.
【思路】
其实这题是个简单线段树，不过根据cf的尿性我一般做不到这来，也就是没有时间看，卡C题，c题玄学题一大堆人过。
每次从最小的一个赋值，然后更新这个点的对后面提供的答案消去，同时消掉这个点
#include #define rep(i,a,b) for(int i=a; i<=(b); ++i) #define mem(a,x) memset(a,x,sizeof(a)) #define pb push_back using namespace std; typedef long long ll; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } const int N=2e5+10; const ll inf=1e11; struct node { ll mn; int i; bool operator <(const node&o)const { return mn<=o.mn; } }a[4*N]; ll lazy[4*N]; int n; void build(int id,int l,int r) { if(l==r) { scanf("%lld",&a[id].mn); a[id].i=l; return ; } int mid=l+r>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); a[id]=min(a[id<<1],a[id<<1|1]); } void pushdown(int id) { if(lazy[id]) { lazy[id<<1]+=lazy[id]; lazy[id<<1|1]+=lazy[id]; a[id<<1].mn+=lazy[id]; a[id<<1|1].mn+=lazy[id]; lazy[id]=0; } } void up(int id,int l,int r,int ql,int qr,ll val) { if(ql<=l&&r<=qr) { lazy[id]+=val; a[id].mn+=val; return ; } pushdown(id); int mid=l+r>>1; if(ql<=mid) up(id<<1,l,mid,ql,qr,val); if(qr>mid) up(id<<1|1,mid+1,r,ql,qr,val); a[id]=min(a[id<<1],a[id<<1|1]); } int ans[N]; int main() { cin>>n; build(1,1,n); rep(i,1,n) { ans[a[1].i]=i; int id=a[1].i; up(1,1,n,id,id,inf); up(1,1,n,id+1,n,-i); } rep(i,1,n) printf("%d ",ans[i]); }


    推荐阅读


    上一篇：简单了解下Java的注释

    下一篇：BZOJ|BZOJ3534: [Sdoi2014]重建【变元矩阵树定理】