Manthan, Codefest 19 (모두 에 게 열 려 있 음, 정격, Div. 1 + Div. 2) D. Restore Permutation (선분 수)
3185 단어 데이터 구조---선분 트 리
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
Your task is to restore the permutation.
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
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 >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]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hunnu 11460 - 구간 최대 값 구하 기 (선분 트 리 템 플 릿)Problem 11460 : No special judgement 길이 가 N 인 배열 을 지정 하고 q 개의 질문 이 있 습 니 다. 모든 질문 은 배열 의 한 구간 에서 그 요소 의 인자 의 개수 가 가장 큽 니...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.