[BOJ 2042] 구간 합 구하기

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

2042번: 구간 합 구하기

Tag : segment tree

 

풀이

두가지 풀이가 있다. 

1.  세그먼트 트리 : \(O(QlogN)\) 

2. 누적합 + 변화량만 따로 저장 : \(O(N + Q^2)\)

 

구간 합 구하기 2에는 simd 펜윅을 박은 분이 1등이던데 이 문제에는 그런 제출이 없어서 다행..

코드

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
   
long long tree[1000001];
 
__libc_start_main() {
    int n=0,m=0,k=0,i=0,a=0,li=0,ri=0;char c=0;long long x=0,op=0,b=0;
    char *p,O[1<<15],*d;int e;
    struct stat st;fstat(0,&st);d=O;
    p=(char*)mmap(0,st.st_size,1,1,0,0);
    for(c=*p++;c&16;n=(n<<1)+(n<<3)+(c&15),c=*p++);
    for(c=*p++;c&16;m=(m<<1)+(m<<3)+(c&15),c=*p++);
    for(c=*p++;c&16;k=(k<<1)+(k<<3)+(c&15),c=*p++);
    for(i=1;i<=n;i++) {
        x=0;p+=e=*p=='-';for(c=*p++;c&16;x=(x<<1)+(x<<3)+(c&15),c=*p++);x=e?-x:x;
        tree[i]+=x;
        if(i+(i&-i)<=n) tree[i+(i&-i)]+=tree[i];
    }
    for(;m+k--;) {
        op=0;for(c=*p++;c&16;op=(op<<1)+(op<<3)+(c&15),c=*p++);
        a=0;for(c=*p++;c&16;a=(a<<1)+(a<<3)+(c&15),c=*p++);
        b=0;p+=e=*p=='-';for(c=*p++;c&16;b=(b<<1)+(b<<3)+(c&15),c=*p++); 
        e&&(b^=9223372036854775808ll);
        if(op & 1) {
            for(li=a,ri=a-1;li|ri;) {
                if(li>ri) b-=tree[li],li-=li&-li;
                else if(li<ri) b+=tree[ri],ri-=ri&-ri;
                else break;
            }
            for(;a<=n;a+=a&-a)tree[a]+=b;
        } else {
            for(op=0,li=b,ri=a-1;li|ri;) {
                if(li>ri) op+=tree[li],li-=li&-li;
                else if(li<ri) op-=tree[ri],ri-=ri&-ri;
                else break;
            }
            if(d-O+100>=1<<15) syscall(1,1,O,d-O),d=O;
            if(op&9223372036854775808ll) *d++='-',op^=9223372036854775808ll;
            char t[16],*q=t;
            do *q++=op%10|48; while(op/=10);
            do *d++=*--q; while(q!=t);
            *d++=10;  
        }
    }
    syscall(1,1,O,d-O);
    _exit(0);
} main;

---

두번째 풀이는 조금 신기하다.

원소의 개수는 크지만 쿼리가 10000개밖에 되지 않는 점을 이용하는 풀이인데

이전 쿼리들에서 변화량만을 저장해놓고 쿼리들 이전의 누적합과 더해서 답을 구하는 풀이다.

시간복잡도는 \(O(N + Q^2)\)가 된다. 

 

코드

#include "bits/stdc++.h"
#pragma GCC optimize("O3")
#define endl '\n'
 
using namespace std;
using ll = long long;
    
ll n, m, k;
ll sum[1000001];
ll arr[1000001];
vector<pair<ll, ll>> qry;

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
template<typename T>
struct FASTIO {
    char *p,O[2000000],*d;
    void set() {
        struct stat st;fstat(0,&st);d=O;
        p=(char*)mmap(0,st.st_size,1,1,0,0);
    }
    ~FASTIO() {
        write(1,O,d-O);
    }
    inline T get() {
        T x=0;bool e;p+=e=*p=='-';
        for(char c=*p++;c&16;x=10*x+(c&15),c=*p++);
        return e?-x:x;
    }
    inline void put(T x) {
        if(x<0) *d++='-', x=-x;
        char t[16],*q=t;
        do *q++=x%10|48; while(x/=10);
        do *d++=*--q; while(q!=t);
        *d++=10;
    }
};

FASTIO<ll> IO;
 
int main() {
//    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
 
    IO.set();
    n = IO.get(); m = IO.get(); k = IO.get();
    for(int i=1; i<=n; i++) {
        arr[i] = IO.get();
        sum[i] = sum[i - 1] + arr[i];
    }
    for(m+=k; m; m--) {
        ll t = IO.get(), a = IO.get(), b = IO.get();
        if(t == 1) {
            ll diff = b - arr[a];
            arr[a] = b;
            qry.emplace_back(a, diff);
        } else {
            ll ret = sum[b] - sum[a - 1];
            for(auto &[idx, val] : qry) {
                if(a <= idx and idx <= b) ret += val;
            }
            IO.put(ret);
        }
    }
}