codeforces - 61E (선분 트 리 3 원 역순 대)
1987 단어 codeforcesacm_데이터 구조
문제 풀이: 중간 수 를 매 거 했 으 면 좋 겠 습 니 다. 그 결 과 는 왼쪽 이 그 수의 개수 보다 많 습 니 다. * 오른쪽 은 그 수의 개수 보다 작 습 니 다. 선분 수 이원 역순 을 구 하 는 방법 과 같 습 니 다.
선분 수 이원 역순 대 방법:
먼저 분 산 된 다음 에 왼쪽 에서 오른쪽으로 한 번 씩 순 서 를 스 캔 하고 매번 검색 구간 (a [i], n) 의 합 을 조회 한 다음 에 a [i] 잎의 값 을 1 로 업데이트 합 니 다.
#include
#include
#include
#include
using namespace std;
int n;
int a[1000010];
int b[1000010];
long long lnum[1000010];
long long rnum[1000010];
struct node{
int l, r;
long long ma;
}s[1000010*4];
void build(int l, int r, int k){
s[k].l = l; s[k].r = r;
if(l == r){
s[k].ma = 0;
return;
}
int mid = (l+r)>>1;
build(l, mid, 2*k);
build(mid+1, r, 2*k+1);
}
long long query(int l, int r, int k){
if(s[k].l == l && s[k].r == r){
return s[k].ma;
}
int mid = (s[k].l+s[k].r)>>1;
if(r<=mid) return query(l, r, 2*k);
else if(l>mid) return query(l, r, 2*k+1);
else return query(l, mid, 2*k)+query(mid+1, r, 2*k+1);
}
void update(int x, int k){
if(s[k].l == s[k].r && s[k].l == x){
s[k].ma++;
return;
}
int mid = (s[k].l+s[k].r)>>1;
if(x<=mid) update(x, 2*k);
else update(x, 2*k+1);
s[k].ma = s[2*k].ma+s[2*k+1].ma;
}
int main(){
scanf("%d", &n);
for(int i = 1; i<=n; i++){
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b+1, b+1+n);
int cnt = unique(b+1, b+1+n)-(b+1);
for(int i = 1; i<=n; i++){
a[i] = lower_bound(b+1, b+1+cnt, a[i])-b;
}
/*for(int i = 1; i<=n; i++){
cout<=1; i--){
rnum[i] = query(1, a[i], 1);
update(a[i], 1);
}
long long res = 0;
for(int i = 1; i<=n; i++){
res += lnum[i]*rnum[i];
}
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
