[백준]하늘에서 떨어지는 1, 2, ..., R-L+1개의 별(17353)

문제 링크 : [백준]하늘에서 떨어지는 1, 2, ..., R-L+1개의 별(17353)

17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

 

문제 설명

1번부터 N번 지점이 존재하는데, 매일 밤 a번부터 b번까지 별이 떨어집니다.

별을 a번 위치에 한개, a+1번 위치에 두개, a+2번 위치에 세개.....이런 식으로 떨어집니다.

최초 각 지점별 떨어져있는 별을 갯수가 주어지고, 아래와 같은 쿼리가 주어 질 때, 옳바른 값을 구하세요.

입력

N(지점의 갯수, 1 <= N <= 1,000,000)

S_i(최초 별의 수, 0 <= S_i <=1,000,000)

Q(쿼리의 갯수, 1 <= Q <= 100,000)

O_i A_i [B_i](O_i : 쿼리 종류(1 : A_i 지점에 떨어진 별을 출력, 2 : A_i부터 B_i지점까지 별이 떨어짐)

5
1 2 1 2 1
4
1 1 5
2 5
1 2 5
2 5

 

출력

6
10

 

카테고리

#세그먼트트리 #LazyPropagation

 

시간 복잡도 상한

O(QlogN)

 

해결 방법

1. 빈번한 구간의 업데이트와 조회 쿼리를 보면 바로 Lazy Propagation을 이용한 세그먼트 트리임을 알 수 있습니다.
2. 그러나 일반적인 Lazy Propagation과는 달리, 한번의 업데이트 쿼리에서 수행해야할 업데이트가 인덱스마다 값이 다릅니다.
3. 여기서부터 약간의 산수가 필요합니다.
4. 문제에서 나왔듯이, 별이 떨어지기 시작한 위치만 안다면, 계산하고자 하는 위치에 떨어지는 별의 갯수를 계산 할 수 있습니다.(R-L+1)
5. 이것을 세그먼트 트리(Lazy Propagation)에도 적용을 해봅니다.
6. 현재 노드가 커버하는 구간을 알고, 그 구간중 제일 왼쪽에 있는 지점에 몇개의 별이 떨어지는지 알 수 있다면, 현재 노드의 구간에 총 몇개의 별이 떨어지는지 알 수 있습니다.
7. 제일 왼쪽에 떨어지는 별을 a개, 현재 노드가 커버하는 총 범위가 b개라고 하면, a+(a+1)+...+(a+b-2)+(a+b-1)=a*b+b*(b-1)/2 가 됩니다.
8. 그러나 Lazy Propagation은 한번이 쿼리마다 업데이트가 일어나는 것이 아니고 누적된 값을 처리해야 합니다.
9. 이때는 구간의 제일 왼쪽에 떨어지는 별들의 누적합과 구간에 업데이트가 몇번이 일어났는지를 확인하여 값을 계산하면 됩니다.

시간복잡도

O(QlogN)

코드

#include<iostream>
#include<string.h>
#define N 100001
using namespace std;
typedef long long L;
int n,m,i,a,b;
L t[N*4],lz[N*4][2];
L in(int p,int l,int r){
    if(l==r)return t[p]=lz[l][0];
    return t[p]=in(p*2,l,(l+r)/2)+in(p*2+1,(l+r)/2+1,r);
}
void z(int p,int l,int r){
    L&a=lz[p][0],&b=lz[p][1],s=r-l+1;
    if(a){
        t[p]+=a*s+s*(s-1)*b/2;
        if(l!=r){
            lz[p*2][0]+=a;
            lz[p*2][1]+=b;
            lz[p*2+1][0]+=a+(s+1)/2*b;
            lz[p*2+1][1]+=b;
        }
        a=b=0;
    }
}
L u(int p,int l,int r,int x,int y,L v){
    z(p,l,r);
    if(y<l||r<x)return t[p];
    if(x<=l&&r<=y){lz[p][0]=v*(l-x+1);lz[p][1]++;z(p,l,r);}
    else t[p]=u(p*2,l,(l+r)/2,x,y,v)+u(p*2+1,(l+r)/2+1,r,x,y,v);
    return t[p];
}
L q(int p,int l,int r,int x){
    z(p,l,r);
    if(x<l||r<x)return 0;
    if(l==r)return t[p];
    return q(p*2,l,(l+r)/2,x)+q(p*2+1,(l+r)/2+1,r,x);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)cin>>lz[i][0];
    in(1,1,n);
    memset(lz,0,sizeof(lz));
    cin>>m;
    while(m--){
        cin>>a>>b;
        if(a&1){
            cin>>a;
            u(1,1,n,b,a,1);
        }else cout<<q(1,1,n,b)<<"\n";
    }
}