블록 세그먼트

소개: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
각종 난잡 한 데이터 구조의 본질: 몇 가지 정규 집합 을 정의 하고 그들 을 특정한 적당 한 구조 로 구성 하 는 것 이다. 검색 알고리즘 은 검색 결 과 를 몇 개의 정규 집합 으로 구분 한 다음 에 모든 정규 집합 에서 매 거 진 방식 으로 찾 는 것 이다.
블록 을 나 누 는 것 은 사실 가장 간단 한 조직 형식 인 hash 이다.
 
처리 할 구간 N 에 대해 서 는 Size = sqrt (N) 블록 으로 나 눕 니 다.각 블록의 크기 에 대응 하면 Size 입 니 다.
블록 에 있 는 표현 형식 을 (i, j) 로 정 하고 그 중에서 i 는 블록 번호 로 어디 에 있 는 지 지정 합 니 다.j 는 블록 의 번호 로 이 블록 에 있 는 구체 적 인 위 치 를 지정 하 는 데 사 용 됩 니 다.
원래 번호 가 id 인 수 는 hash 에 대응 한 후 (id / size, id% Size) PS: 컴퓨터 메모리 와 같은 블록 입 니 다.
응용 1: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
처리 대상: [l, r] 구간 지정, 최대 값 구하 기
　　[ 0 , Size ) [ Size , 2Size )....[ xSize , (x+1)Size )...
l 은 [Size, 2Size) 에 속 하고 r 는 [xSize, (x + 1) Size 에 속한다)
 
생각:
각 내부 의 최대 값 을 미리 처리 합 니 다.
[l, r] 구간 에 포 함 된 모든 블록, 즉 해당 블록 번호 2 - (x - 1) 를 옮 겨 다 니 며 비교 값 을 가 져 옵 니 다.
폭력 검색 [l, r] 양쪽 의 수치, 즉 원 id 구간 에 대응: [l, 2Size) & [xSize, r]
 
 
증거 교환:
사전 처리 복잡 도 O (N);
검색 복잡 도 O (sqrt (N))

//   ：
#define maxn 10005
int num[maxn];
int maxnum[Size+5];
int n,Size;
void init()
{    
    for(int i=0;i<n;i++)
        if(i%Size==0 || num[i]>maxnum[i/Size] ) 
            max[i/Size]=num[i];    
}

 

//  ：
int query(int l,int r) 
{
    int ret=num[l];
    for(int j=l;j<=r;)
    {
        if(j%Size==0 && j+Size-1<=r) 
        {
            if(maxnum[j/Size]>ret) ret=maxnum[j/Size];
            j+=Size;
        }
        else 
        {
            if(num[j]>ret) ret=num[j];
            j++;
        }
    }
    return ret;
}

 
응용 2: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
처리 대상: 응용 1 을 바탕 으로 업데이트 기능 을 추가 하여 임의의 값 을 수정 할 수 있 습 니 다.
사고: 이 값 을 수정 한 후에 변경 점 이 있 는 블록 내 데 이 터 를 동기 화하 면 다른 응용 1 을 할 수 있 습 니 다.
복잡 도 O 업데이트 (1)
코드: 생략 ~
응용 3: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
응용 대상: 구간 K 대
생각:
블록 마다 내부 정렬 하기
2 분 경계 제한 값 X 는 지 정 된 구간 에 < X 의 수의 개 수 를 찾 습 니 다. 구간 에 전체 블록 이 포함 되 어 있 으 면 2 분 입 니 다. 그렇지 않 으 면 폭력 적 입 니 다.
X 가 지 정 된 조건 을 만족 시 킬 때 까지 (즉, 얻 은 < X 의 값 의 개수 = K)
복잡 도: log (r - l)× （N/Size x log（Size）+Size×2）
즉, log (N) sqrt (N) 정도, 상수 가 약간 크다.
코드: 생략 ~
 
이전의 이론 에 따 르 면 복잡 도 는 log (r - l) 이다.× （N/Size x log（Size）+Size×2）
그 중 (N / size x log (Size) + Size×2) 부분
Size 의 값 은 너무 크 거나 너무 작 을 수 없고 sqrt (N) 정도 만 정 해 지지 않 을 수 있 습 니 다. 그렇지 않 으 면 극단 적 인 데이터 가 걸 릴 수 있 기 때문에 이 부분의 복잡 도 는 평균 sqrt (N) 입 니 다.
조회 횟수 가 너무 많 으 면 분 T 로 떨 어 집 니 다. 최적화 해 야 합 니 다!
 
 
만약 에 매번 조회 하 는 경계 가 제 Size 의 구간 점 이 라면 저 는 직접 2 분 에 찾 아서 양쪽 의 폭력 과정 을 없 앨 수 있 습 니 다.
이 를 통 해 구간 을 세그먼트 로 나 누 는 것 을 생각 합 니 다. 즉, 길이 가 다른 블록 으로 나 눌 수 있 습 니 다. 서로 다른 데이터 에 대해 가장 좋 은 세그먼트 방법 은 반드시 같 지 않 습 니 다. 우 리 는 모든 세그먼트 방법 을 보존 하 는 것 이 좋 습 니 다. 그러나 이렇게 하면 메모리 가 부족 합 니 다.
 
한 수 는 반드시 2 진법 으로 표시 할 수 있 으 며, 2 진수 에 대응 하 는 길이 도 그리 길지 않 을 것 이다.
이 를 통 해 연상 되 는 것 은 임의의 구간 에 대해 서 는 여러 개의 크기 가 2 인 차 멱 의 블록 으로 나 눌 수 있다.
우 리 는 모든 크기 가 2 인 차 멱 의 블록 을 미리 처리 해 야 하 며, 매번 조회 할 때마다 각 블록 내부 에서 2 분 동안 찾 는 것 이다.
입력 데이터 크기 에 따라 충분 한 층 을 얻 고 각 층 은 고정 크기 의 블록 에 대응 합 니 다. 각 블록 내 부 는 스스로 정렬 하면 됩 니 다.
전체 복잡 도:
전처리: 층수 * Nlog (N)
검색: log (N) ^ 2
　　POJ 2104：

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100005
const int X = 18;
int n,m;
int arr[maxn];
int sorted[20][maxn];
int countfind(int x,int l,int r,int val)
{//    x ，   l,r        < val
    int *sorted = ::sorted[x];
    if(sorted[l]>=val) return 0;
    if(sorted[r]<val) return r-l+1;
    int st=l;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(sorted[mid]<val) l=mid;
        else r=mid;
    }
    return r-st;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);

    for(int j=0;j<X;j++)
    for(int i=0;i<n;i++)
    sorted[j][i]=arr[i];
//          2,4,8,16...   
    for(int j=1;j<X;j++)
    {
        int step=1<<j;
        for(int i=0;i+step-1<n;i+=step)
        sort(sorted[j]+i,sorted[j]+i+step);
    }
    while(m--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        l--;
        r--;
        int mi=-1e9-1;
        int ma=1e9+1;
        while(mi+1<ma)
        {
            int ans=0;
            int mid=(mi+ma)>>1;
            for(int i=l;i<=r;)
            {//           2    
                for(int j=X;j>=0;j--)
                {
                    int step=1<<j;
                    if(i%step==0 && i+step-1<=r)
                    {
                        ans+=countfind(j,i,i+step-1,mid);
                        i+=step;
                        break;
                    }
                }
            }
            if(ans<k) mi=mid;
            else ma=mid;
        }
        printf("%d
",mi);
    }
    return 0;
}

신비 링크 수정:http://www.cnblogs.com/sweetsc/archive/2012/08/15/2639395.html