[총집합] LOJ 블록 1–9

카탈로그

블록 9문제

출제자hzw의 해석

수열 블록으로 시작하기 1

수정: 구간 가산

조회: 단점값 조회

코드

수열 블록으로 시작하기 2

수정: 구간 가산

조회: 구간 순위

코드

수열 블록으로 시작하기 6

수정: 단일 삽입

조회: 단일 포인트 값

코드

수열 블록으로 시작하기 7

수정: 구간 가, 구간 곱하기

조회: 단일 조회

코드

수열 블록으로 시작하기 8

수정: 구간 할당

조회: 구간 계수

코드

[총집합] LOJ 블록 분할 시작 1–9

블록 9 문제

출제자hzw의 해석

(tips. 아래 코드에서 IO 최적화는 모두 생략되었습니다. 전송문을 누르고 싶습니다)

디지털 블록으로 시작하기 1

수정:구간 더하기

질의:단일 포인트 질의

이것은 고전적인 제목으로, 선단수, 나무상수조 등을 모두 할 수 있는데, 여기서 블록을 나누어 이야기하자
블록을 나누는 것은 일정한 길이의 한 단락을 블록으로 포장하여 통일적으로 처리하는 알고리즘이다
각 블록마다 자신의 정보, 자신의 표시, 통일된 유지보수, 통일된 조회가 있다
우리는 각 구간의 수정이나 조회를 몇 개의 전체 블록과 앞뒤 두 개의 불완전한 블록에서 수정, 조회 후 정보의 총체로 나눌 수 있다
그럼 이 문제에서 블록은 얼마나 나눠야 하나요?정답은 $\sqrt n $입니다.
본인이 너무 약하기 때문에 hzw대장부의 증명을 드리겠습니다.
만약 우리가 모든 m개의 원소를 하나의 덩어리로 나눈다면 $\rac{n}{m}$블록이 있습니다. 구간에 추가된 작업은 $O(\rac{n}{m})$개의 전체 블록과 구간 양측의 두 개의 불완전한 블록 중 2m개의 원소와 관련됩니다.우리는 모든 블록에 덧셈 표시를 설정합니다. (이 블록에 원소가 얼마나 첨가되었는지 기록하는 것입니다.) 매번 조작할 때마다 전체 블록에 $O (1) $표시를 하고, 완전하지 않은 블록은 원소가 비교적 적기 때문에 원소의 값을 폭력적으로 수정합니다.물어볼 때마다 원소의 값에 그 원소가 있는 블록의 덧셈 표시를 되돌려줍니다.이렇게 매번 조작의 복잡도는 $O(\rac{n}{m})+O(m)$이며, 균일치 부등식에 따라 m에서 $\sqrtn$를 뽑을 때 총 복잡도가 가장 낮다

코드

#include 
#define rint register int
using namespace std;
const int N=50005,B=225; //B     
int n,len,bn; //bn   ，len   
int L[B],R[B],tag[B],a[N],block[N];
//L[i]  i    ,R[i]  i    ,tag[i]  i       
//a[i]    i       ,block[i]    i    
inline void add(int l,int r,int c){
    int p=block[l],q=block[r]; //p        ，q        
    if(p==q){ //           
        for(int i=l;i<=r;++i) //   [l,r]        
            a[i]+=c;
        return ;
    }
    for(rint i=p+1;i<=q-1;++i)
        tag[i]+=c; //         ，          
    for(rint i=l;i<=R[p];++i)
        a[i]+=c; //            
    for(rint i=L[q];i<=r;++i)
        a[i]+=c; //            
}
signed main(){
    read(n);
    for(rint i=1;i<=n;++i)
        read(a[i]);
    bn=len=sqrt(n);
    for(rint i=1;i<=bn;++i){
        L[i]=(i-1)*len+1;
        R[i]=i*len;
        for(rint j=L[i];j<=R[i];++j)
            block[j]=i; //          
    }
    if(R[bn]

수열 블록 분리2

수정:구간 더하기

검색:구간 랭킹

이 문제는 1과 비슷하지만 st[i][j]를 추가로 유지해야 한다. 블록 i가 작은 순서에서 큰 순서로 j위에 랭크된 수를 나타낸다.
sort폭력으로 단조성을 유지하면lowerbound () 는 어떤 블록의 랭킹을 직접 얻고 정보를 통합하면 됩니다
수정 부분은 1의 기초 위에서 매번 블록에 대한 수정을 마친 후에 st[][]를 유지하면 된다
조회 부분은 흩어진 작은 덩어리에 대해 폭력적으로 일일이 판단한다.전체 블록에 대해 2분 동안 순위를 확인하면 이 블록의 답을 얻을 수 있다.마지막으로 모든 블록의 답안을 누적하면 된다

코드

#include 
#define rint register int
using namespace std;
const int N=50050,B=235;
int n,len,bn,L[B],R[B],tag[B],a[N],block[N],st[B][B];
//      ，st[i][j]   i          j  
inline void maintain(const int &x){ //  x     st[][]     ，   st[x][]     
    memset(st[x],0,sizeof st[x]);
    for(rint i=L[x];i<=R[x];i++)
        st[x][++st[x][0]]=a[i];
    sort(st[x]+1,st[x]+1+st[x][0]);
}
inline void add(int l,int r,int c){
    /*    */
    int p=block[l],q=block[r];
    if(p==q){
        for(int i=l;i<=r;++i)
            a[i]+=c;
        maintain(p); //   p
        return ;
    }
    for(rint i=p+1;i<=q-1;++i)
        tag[i]+=c;
    for(rint i=l;i<=R[p];++i)
        a[i]+=c;
    for(rint i=L[q];i<=r;++i)
        a[i]+=c;
    maintain(p); //   p
    maintain(q); //   q
}
inline int que(int l,int r,int c){
    int p=block[l],q=block[r],res=0;
    if(p==q){
        for(rint i=l;i<=r;i++)
            res+=(a[i]+tag[p]

수열 블록 엔트리 6

수정:단일 점 삽입

질의:단일 포인트 값

이 문제는 우리가 동적 삽입 방법을 채택한다
vector의 insert 프로세스를 빌려 우리는 삽입 조작을 편리하게 완성할 수 있다
삽입된 위치는 다음 코드에서 확인할 수 있습니다.
(x의 첫 번째 값은 찾으려는 하표이고, 마지막 값은 블록의 하표이며, p는 블록의 번호이며,vec[]는 블록에 사용되는 저장 구조이다)

while(x>vec[p].size()) x-=vec[p].size(),p++;

조회 작업도 위의 코드를 호출하면 원하는 위치를 쉽게 찾을 수 있다
ε = = (づ′▽`)づ
본 문제의 데이터는 랜덤이며, 이상의 부분은 이미 대응할 수 있지만, 랜덤이 아니라면?
끊임없이 삽입하면 블록이 비대해지고 복잡도가\(O (n^2)\로 퇴화됩니다.
그럼 어떡하지?
우리는 블록 재구성을 채택하여 어떤 블록이 원 블록의 길이\(\sqrt 블록의 길이\)배를 초과한 후 원래의 블록을 뜯어 새로운 블록을 구성한다
재구성 부분 코드는 다음과 같습니다.

    int n=0; // 0       
    for(rint i=1;i<=bn;i++){
        int kkk=vec[i].size();
        for(int j=0;j

(tips.LOJ와 hzw의 문제풀이 배수를 모두 20배로 정했는데 사실은\(\sqrt[4] {n}\)이다. 비교적 대략적으로 나의 정확한 배수로 최적화할 수 있다. 즉, 위 코드의 마지막 줄)

코드

#include 
#define rint register int
using namespace std;
const int N=200050,B=460; //     
int a[N],n,len,lim,bn;
vector vec[B];
struct res{int block,pos;};
inline res get(int x){ //    ，     ~~
    int p=1;
    while(x>vec[p].size()) x-=vec[p].size(),p++;
    return (res){p,x-1};
}
inline void rebuild(){ //  ，     ~~
    int n=0;
    for(rint i=1;i<=bn;i++){
        int kkk=vec[i].size();
        for(int j=0;jlim) rebuild(); //            
}
inline int que(int x){
    res now=get(x); //    
    return vec[now.block][now.pos];
}
signed main(){
    read(n);
    for(rint i=1;i<=n;i++)
        read(a[i]);
    len=sqrt(n);
    for(rint i=1;i<=n;i++)
        vec[(i-1)/len+1].push_back(a[i]); //  
    bn=(n-1)/len+1;
    lim=len*sqrt(len); //   
    while(n--){
        int opt,l,r,c;
        read(opt),read(l),read(r),read(c);
        if(!opt) edi(l,r);
        else Write(que(r),'
');
    }
}

디지털 블록으로 시작하기 7

수정:구간 더하기, 구간 곱하기

조회:단일 조회

이 문제는 매우 고전적이다. 낙곡P3373은 구간 구화판으로 선단수로 만든다
이 문제에 대해 너는 초등학교 전치 지식이 필요하다. 곱셈 우선순위가 덧셈보다 높다는 것이다
따라서 이 문제에서 각 블록에 대해 우리가 유지해야 할 두 가지 정보: 덧셈 표기와 곱셈 표기는 덧셈 표기보다 우선순위가 높다는 것이 뚜렷하다.
그 다음은 분류 토론이다.

전체 블록 x의 덧셈 표시는add이고 곱셈 표시는mul이며 주어진 조작값은val이다.

x가 덧셈 조작을 한 번 할 때:

add+=val;

x가 곱셈 조작을 한 번 하려고 할 때:

mul*=val;
add*=val;

블록의 경우 폭력 매거 수정

또한 블록 작업의 불확실성 때문에 블록에 대해push작업을 단독으로 한 번 진행하고 블록의 표시를 바꾸어 블록의 모든 요소(선승후가)를 수정하고 곱하기 표시를 1로 하고 표시를 0으로 한다.
이상은 수정 작업입니다.
조회에 관해서는 원소값을 먼저 곱셈 표시를 곱한 다음에 덧셈 표시를 더하면 된다

코드

#include 
#define rint register int
using namespace std;
const int mod=1e4+7,N=1e5+20,B=335;
int n,a[N],block[N],L[B],R[B],mul[B],add[B],bn,len;
inline void push(const int &x){
    for(rint i=L[x];i<=R[x];i++)
        a[i]=(a[i]*mul[x]%mod+add[x])%mod;
    mul[x]=1; //          ！！！        。。。
    add[x]=0;
}
inline void edi(bool flag,int l,int r,int v){ //flag        ，1  ，0  
    int p=block[l],q=block[r];
    push(p);
    if(p==q){
        for(rint i=l;i<=r;i++)
            a[i]=flag?(a[i]*v)%mod:(a[i]+v)%mod; //      
        return ;
    }
    push(q);
    for(rint i=p+1;i<=q-1;i++){
        if(flag){
            (mul[i]*=v)%=mod; //           
            (add[i]*=v)%=mod;
        }
        else{
            (add[i]+=v)%=mod;
        }
    }
    for(rint i=l;i<=R[p];i++)
        a[i]=flag?(a[i]*v)%mod:(a[i]+v)%mod; //  ，    
    for(rint i=L[q];i<=r;i++)
        a[i]=flag?(a[i]*v)%mod:(a[i]+v)%mod;
}
signed main(){
    read(n);
    for(rint i=1;i<=n;i++)
        read(a[i]),a[i]%=mod;
    bn=len=sqrt(n);
    for(rint i=1;i<=bn;i++){
        L[i]=(i-1)*len+1;
        R[i]=i*len;
    }
    if(R[bn]

수열 블록 엔트리 8

수정:구간 지정

질의:구간 수

구간 할당치의 조작은 매우 간단하고 폭력적이어서 일일이 열거하면 된다
조회에 있어서, 우리는 모든 블록을 대체적으로 두 종류로 나눌 수 있다는 것을 발견했다. 즉, 숫자가 같고, 숫자가 같지 않은 것이다
그래서 우리는 하나의same[]수조를 유지하고 각 블록의 동일한 값을 기록할 수 있다. 서로 다른 말은 -oo이다.
(tips.oo는 무궁무진하다. 0x3f3f3f3f 또는 0x7fffffff와 같은 극치를 선택할 수 있다)
(tips.hzw의 코드는 hack될 수 있다. 왜냐하면 그의 -oo는 -1이기 때문에 우리는 하나의 블록 안의 요소가 모두 -1일 수 있다는 것을 안다)
Same[]이 생기면 어떡하지?
당연히 기예가 음란하고 기교 있게 폭력적이지!

부치는 간소화할 수 있고 전체 블록은 직접 O(1)same값을 수정하면 되며 좌우 흩어진 블록은 폭력적으로 매거할 수 있다

계수할 때 블록 x, 조회 값 v에 대해 다음 위조 코드로 신속하게 판단할 수 있다.

if(same[x]==-1){
    from     to    
            ;
}
else
if(same[x]==v){
    ans+=   -   +1;
}
else{
    ans+=0;
}

불필요한 조작을 피하기 위해 매번 조회를 요구하기 전에 조회되고same 값이 수정된 블록에 대해push 조작을 하고 이 블록의same 값을 이 블록의 모든 요소에 부여하여 유지보수

복잡도에 관해서는 hzw 대장부의 증명을 다시 한 번 인용하겠습니다.
이렇게 하면 최악의 경우 매번\(O (n)\) 의 시간이 소모될 것 같지만, 사실은 이렇게 분석할 수 있다. 초기 서열이 모두 같은 값이라고 가정하면 조회는\(O (\sqrt n)\) 이다. 만약에 구간 조작을 하면, 맨 끝 두 블록의 표시를 최대 파괴할 수 있기 때문에, 뒤에 두 블록의 폭력적인 시간만 물어볼 수 있기 때문에 매번 조작의 복잡도는\(O (\sqrt n)\) 를 균등하게 할당할 수 있다.

코드

#include 
#define rint register int
using namespace std;
const int N=1e5+30,B=333,oo=0x3f3f3f3f;
int a[N],block[N],L[B],R[B],same[B],n,bn,len;
inline void push(const int &x){ // same      ，         
    if(same[x]!=-oo){
        for(rint i=L[x];i<=R[x];i++)
            a[i]=same[x];
        same[x]=-oo;
    }
}
inline int work(int l,int r,int v){
    int p=block[l],q=block[r],res=0;
    push(p); //    
    if(p==q){
        if(same[p]==v) return r-l+1; //  same     ，       
        for(rint i=l;i<=r;i++) //    &  
            if(a[i]==v) res++;
            else a[i]=v;
        return res;
    }
    push(q); //    
    for(rint i=p+1;i<=q-1;i++){
        if(same[i]==v) res+=R[i]-L[i]+1;
        else{
            if(same[i]==-oo)
                for(rint j=L[i];j<=R[i];j++)
                    if(a[j]==v) res++;
                    else a[j]=v;
        }
        same[i]=v; //     same     
    }
    /*        p==q    */
    if(same[p]==v) res+=R[p]-l+1;
    else
    for(rint i=l;i<=R[p];i++)
        if(a[i]==v) res++;
        else a[i]=v;
    if(same[q]==v) res+=r-L[q]+1;
    else
    for(rint i=L[q];i<=r;i++)
        if(a[i]==v) res++;
        else a[i]=v;
    return res;
}
signed main(){
    read(n);
    for(rint i=1;i<=n;i++)
        read(a[i]);
    bn=len=sqrt(n);
    for(rint i=1;i<=bn;i++){
        L[i]=(i-1)*len+1;
        R[i]=i*len;
    }
    if(R[bn]