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

https://www.acmicpc.net/problem/17353

 

문제 요약

별이 떨어지는 n개의 지점이 있다. 별은 구간[l,r]의 형태로 떨어지고 각 점엔 순서대로 1,2,3,...,r-l+1개가 떨어진다. 별이 떨어지는 것과 한점에 떨어진 별의 개수를 구하는 것을 쿼리로 처리해라.

 

풀이 (QlogN)

• 느리게 갱신되는 세그먼트 트리

공차가 1인 등차수열을 다루는 문제이다. imos법으로 해결할 수 있다. 모든 l~r구간에 1씩 더하고 r+1에 r-l+1을 빼놓은 다음 1~x구간합을 구해주는 방법이다. 누적합을 매 번 취해줄 수 없기 때문에 세그트리로 구간합을 구해야 한다. l~r구간 업데이트가 필요하기 때문에 레이지 세그를 사용해야 한다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid (st+en>>1)
const int N = 1e5+1;

ll a[10*N],seg[4*N],lp[4*N];
void pp(int i,int st,int en) {
    seg[i]+=(en-st+1)*lp[i];
    if(st!=en)lp[i*2]+=lp[i],lp[i*2+1]+=lp[i];
    lp[i]=0;
}
ll update(int i,int st,int en,int l,int r,int x) {
    pp(i,st,en);
    if(r<st||l>en)
        return seg[i];
    if(st>=l&&r>=en) {
        lp[i]+=x;
        pp(i,st,en);
        return seg[i];
    }
    return seg[i]=update(i*2,st,mid,l,r,x)+update(i*2+1,mid+1,en,l,r,x);
}
ll query(int i,int st,int en,int l,int r) {
    pp(i,st,en);
    if(r<st||l>en)
        return 0;
    if(st>=l&&r>=en) 
        return seg[i];
    return query(i*2,st,mid,l,r)+query(i*2+1,mid+1,en,l,r);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,q;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>q;
    while(q--) {
        int t,x,y;
        cin>>t>>x;
        if(t==1) {
            cin>>y;
            update(1,1,n,x,y,1);
            update(1,1,n,y+1,y+1,-(y-x+1));
        }
        else {
            cout<<query(1,1,n,1,x)+a[x]<<'\n';
        }
    }
}