선분 트 리 역순 수 구하 기 (단일 업데이트)
1488 단어 데이터 구조
abcde... 의 역순 수가 k 라면 bcde... a 의 역순 수 는 얼마 입 니까?우 리 는 abcde... a 보다 작은 개 수 는 t 라 고 가정 합 니 다. 그러면 a 보다 큰 개 수 는 n - t - 1 입 니 다. a 를 가장 오른쪽 으로 이동 할 때 원래 a 보다 많 습 니 다.
큰 것 은 현재 모두 a 의 역순 이 되 었 다. 즉, 역순 수가 n - t - 1 증가 하 는 것 이다. 그러나 원래 a 보다 작은 역순 대 를 구성 하 는 수 는 지금 은 모두 순서 가 되 었 기 때문에 역순 대 는 t 를 감소 하기 때문에 새로운 서열 의 역순 수 는 k + = 이다.
n - t - t - 1, 즉 k + = n - 1 - 2 * t, 그래서 우 리 는 계속 자 리 를 옮 긴 다음 에 최소 값 을 업데이트 하면 됩 니 다.
#include
#define maxn 55555
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[maxn<<2];
int x[maxn];
int min(int a,int b)
{
return a>1;
Build(lson);
Build(rson);
}
void Update(int p,int l,int r,int rt)
{
if(l==r)
{
sum[rt]++;
return;
}
int m=(l+r)>>1;
if(p<=m)
Update(p,lson);
else
Update(p,rson);
PushUP(rt);
}
int Query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
return sum[rt];
int m=(l+r)>>1;
int ret=0;
if(L<=m) ret+=Query(L,R,lson);
if(R>m) ret+=Query(L,R,rson);
return ret;
}
int main()
{
int n,i;
while(~scanf("%d",&n))
{
Build(0,n-1,1);
int sum=0;
for(i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
