'CNOI 2019' 디지털 게임 문제 풀이

요약 제목: 하나의 배열 을 정 하고 여러 번 물 어보 고 한 구간 [l, r] [l, r] [l, r] 의 몇 개의 키 구간 의 값 이 구간 [x, y] [x, y] [x, y] [x, y] [x, y] 안에 있 는 지 물 어보 세 요.
알고리즘 1:
폭력 매 거 진 하위 구간 을 물 어 본 후 폭력 검사 가 조건 을 만족 시 키 는 지, 시간 복잡 도 O (q n 3) O (qn ^ 3) O (qn 3).
ST 표 로 미리 처리 합 니 다. O (1) O (1) O (1) 조회 구간 의 최고 치 는 O (q n 2 + n l o g n) O (qn ^ 2 + nlogn) O (qn 2 + nlogn) 를 할 수 있 습 니 다.
기대 점수: 0 0 0
알고리즘 2:
우리 가 한 구간 을 조회 할 때, 그 중에서 모든 요 소 를 만족 시 키 는 것 은 [x, y] [x, y] [x, y] 내의 극 장자 구간 의 공헌 이 t (t + 1) 2 \ \ frac {t (t + 1)} {2} 2t (t + 1) 이 고, 그 중에서 t t t 는 이 자구 간 의 길이 이다.
따라서 매번 질문 할 때마다 모든 극 장자 구간 을 스 캔 하면 O (qn) O (qn) O (qn) 를 할 수 있 습 니 다.
기대 점수: 0 0 0 ~ 34 34 34
(데이터 카드 를 구 축 했 지만 작은 상수 유저 에 의 해 1 단 계 를 넘 겼 습 니 다)
알고리즘 3:
데이터 구 조 를 사용 하여 유지 해 야 한 다 는 생각 이 들 기 쉬 워 서 우 리 는 모 팀 을 생각 했다. 그러나 당직 구역 [x, y] [x, y] [x, y] 가 계속 변 하고 유지 하기 어 려 운 것 같 아서 우 리 는 생각 을 바 꾸 는 것 을 선택 했다.
제목 이 준 서열 에 하나의 배열 이 있 기 때문에 우 리 는 당직 구역 에서 막 대 를 고려 하고 이동 할 때마다 한 위치 만 바 꾸 는 것 이 효과 적 인지 여 부 를 고려 합 니 다.그리고 정 답 을 지 키 는 것 을 고려 하면 선분 트 리 가 분명 하 다.각 노드 는 왼쪽, 오른쪽 끝 에서 시작 하 는 극 장 유효 구간 의 길 이 를 유지 하고 구간 의 답 과 구간 이 모두 유효 하 는 지 여 부 를 유지 하면 된다.
시간 복잡 도 O  l o g n ) O(n\sqrt{q}\ logn) O(nq ​ logn)
기대 점수: 34 34 34 34
알고리즘 4:
다른 O (q n) O (qn) O (qn) O (qn) 의 방법 을 고려 하여 매번 스캐닝 값 을 물 어 볼 때마다 값 내 각 값 이 구간 내 에 있 는 지 판단 하고 답 을 업데이트 합 니 다.답 을 업데이트 할 때 는 링크 로 모든 유효 구간 을 유지 해 야 합 니 다.
기대 점수
알고리즘 5:
시간 복잡 도 를 발견 한 병목 은 조회 할 때 선분 트 리 가 필요 하고 최 적 화 를 고려 하 는 데 있다.
그래서 우 리 는 서열 에 대해 블록 을 나 누고 알고리즘 4 의 방법 을 결합 하여 각 블록 내 에 하나의 링크 와 구간 의 답 을 단독으로 유지 합 니 다. 유지 하 는 정 보 를 취소 하기 어렵 기 때문에 우 리 는 스크롤 모 팀 의 유지 치 역 을 선택 합 니 다. 구간 의 길 이 는 2n 2 \ sqrt {n} 2n 의 사용 계산법 4 폭력 보다 적 고 큰 부분 은 매번 O (n) O (\ sqrt {n}) O (n) 를 조회 합 니 다.모 팀 이 이동 할 때마다 O (1) O (1) O (1) 는 블록 에 있 는 링크 를 유지 하고 스크롤 백 할 때 시간 스탬프 O (1) O (1) O (1) O (1) 를 사용 하여 거 슬러 올라간다.
전체 시간 복잡 도 O (n) O (n \ sqrt {n}) O (N), 코드 량 4k 정도.
기대 점수: 100 100 100 100
전체적으로 보면 이것 은 간단 한 문제 로 해법 이 자 연 스 럽 고 코드 의 양 이 적당 하 며 사고방식 의 난이도 가 적당 하 다. 선분 수, 막 대, 블록, 링크 등 여러 가지 초등 데이터 구 조 를 고찰 한 것 은 영락 없 는 작은 싱 그 러 운 데이터 구조 가 좋 은 문제 이다.
첨부 std:

#include
using namespace std;

typedef long long LL;

LL que_range( int x ) { return 1ll * x * (x + 1) / 2; }

template<int _size>
struct stamp{
    int A[ _size ];
    int B[ _size ];
    int T[ _size ];
    int cnt = 1;
    bool bind = false;
    
    void Roll() { cnt ++; }
    void Bind() { bind = true; Roll(); }
    void Unte() { bind = false; }
    
    void Set0() { memset( B, 0, sizeof(B) ); Roll(); }
    
    int& operator []( int index ) {
        if( bind ) {
            if( T[index] ^ cnt ) T[index] = cnt, A[index] = B[index];
            return A[index];
        } else return B[ index ];	
    }
};

int block = 500;
int belong[200005];
int beg[405];

struct que{
    int l, r, x, y, id;	
    que() {}
    que( int _id ) { cin >> l >> r >> x >> y; id = _id; }
    bool operator <( que& from ) const
      { return belong[x] == belong[ from.x ] ? y < from.y : x < from.x; }
};

int n, q; 
vector<que> Q;

int c [200005];
int uc[200005];

stamp<200005> pre;
stamp<200005> nxt;
stamp<405> mid;

int bf1( que& x ) { 
    int ans = 0, lst = 0;
    for( int i = x.l; i <= x.r; i ++ ) {
        if( c[i] <= x.y and c[i] >= x.x ) lst ++;
        else lst = 0;
        ans += lst;
    }
    return ans;
}

int bf2( que& x ) {
    int ans = 0;
    for(int i = x.x;i <= x.y;i ++) {
        int p = uc[i];
        if( p < x.l or p > x.r ) continue;
        ans -= que_range( p - pre[p - 1] );
        ans -= que_range( nxt[p + 1] - p );
        nxt[ pre[p - 1] ] = nxt[p + 1];
        pre[ nxt[p + 1] ] = pre[p - 1];
        ans += que_range( nxt[p + 1] - pre[p - 1] + 1 );
    }
    pre.Roll(); nxt.Roll();
    return ans;
}

void updata( int x ) {
    int p = uc[x], b = belong[p];
    if( p ^ beg[b] ) {
        if( pre[p - 1] != beg[b] ) mid[b] -= que_range( p - pre[p - 1] );
        if( p != beg[b + 1] - 1 )nxt[ pre[p - 1] ] = nxt[p + 1];
        else nxt[p] = p, pre[p] = pre[p - 1], nxt[ pre[p - 1] ] = p;
    }
    if( p ^ beg[b + 1] - 1 ) {
        if( nxt[p + 1] != beg[b + 1] - 1 ) mid[b] -= que_range( nxt[p + 1] - p );
        if( p != beg[b] ) pre[ nxt[p + 1] ] = pre[p - 1];
        else pre[p] = p, nxt[p] = nxt[p + 1], pre[ nxt[p + 1] ] = p;
    }
    if( p != beg[b] and p != beg[b + 1] - 1 and pre[p - 1] != beg[b] and nxt[p + 1] != beg[b + 1] - 1 ) 
        mid[b] += que_range( nxt[p + 1] - pre[p - 1] + 1 );
}

LL ans[200005];

int main(){
    cin >> n >> q; 
    
    for(int i = 1;i <= n;i ++) {
        cin >> c[i]; uc[ c[i] ] = i;
        belong[i] = i / block + 1;
        if( belong[i] > belong[i - 1] ) beg[ belong[i] ] = i;
    }
    if( beg[ belong[n] ] == n ) belong[n] --;
    beg[ belong[n] + 1 ] = n + 1; belong[ n + 1 ] = belong[n] + 1;
    
    for(int i = 0;i <= n + 1;i ++) pre[i] = i + 1, nxt[i] = i - 1;
    nxt.Bind(); pre.Bind(); mid.Bind();
    
    for(int i = 1;i <= q;i ++) {
        que x = que(i);
        if     ( x.r - x.l <= block * 2 ) ans[i] = bf1( x );
        else if( x.y - x.x <= block * 2 ) ans[i] = bf2( x ); 
        else Q.push_back( x );
    }
    sort( Q.begin(), Q.end() );
    int pt = 0;
    for(int i = 1;i < belong[n];i ++) {
        int r = beg[i + 1] - 1;
        
        nxt.Unte(); pre.Unte(); mid.Unte();
        for(int j = 0;j <= n + 1;j ++) pre[j] = j + 1, nxt[j] = j - 1; mid.Set0();
        
        while( pt < Q.size() and belong[ Q[pt].x ]  == i ) {
            auto &P = Q[pt];
            
            nxt.Unte(); pre.Unte(); mid.Unte();
            while( r < P.y ) updata( ++ r );
            
            nxt.Bind(); pre.Bind(); mid.Bind();
            for( int j = P.x; j < beg[i + 1]; j ++ ) updata( j );
            
            long long Ans = 0, lst = 0; 
            int bl = belong[ P.l - 1 ] + 1;
            int br = belong[ P.r + 1 ] - 1;
            
            for( int j = P.l; belong[j] < bl; j ++ ) {
                if( c[j] >= P.x and c[j] <= P.y ) lst ++;
                else Ans += que_range( lst ), lst = 0;
            }
            
            for( int j = bl; j <= br; j ++ ) {
                if( nxt[ beg[j] ] == beg[j + 1] - 1 ) lst += beg[j + 1] - beg[j];
                else {
                    lst += nxt[ beg[j] ] - beg[j] + 1;
                    Ans += que_range(lst); Ans += mid[j];
                    lst = beg[j + 1] - pre[ beg[j + 1] - 1 ];
                }
            }
            
            for( int j = beg[br + 1]; j <= P.r; j ++ ) {
                if( c[j] >= P.x and c[j] <= P.y ) lst ++;
                else Ans += que_range( lst ), lst = 0;
            }
            
            Ans += que_range( lst );
            ans[ P.id ] = Ans;
            
            nxt.Roll(); pre.Roll(); mid.Roll();
            pt ++;
        }
    }
    for(int i = 1;i <= q;i ++) cout << ans[i] << "
";
    return 0;
}