DID : PS 1문제 (2023/04/05)

시험 공부 중 한문제 슬쩍 풀었다.

BOJ 16978 수열과 쿼리 22
PST로 풀린다고 해서 풀어볼려 했는데, 오프라인 쿼리로 풀릴 거 같아서 느낌 그대로 조져 보았다. 그냥 합 연산인데 오프라인 쿼리를 곁들인? 쿼리1,2를 저장해서 쿼리 2를 정렬하고, 쿼리 1을 순차적으로 해결해 나가면 된다. EZ

#include<bits/stdc++.h>
#define ppiipii pair<pair<int,int>, pair<int,int> >
using namespace std;
typedef long long ll;
vector<pair<int,int> > query1;
vector<ppiipii > query2;
ll ans[100005];

struct Node
{
    ll v;
    Node *l, *r;
    Node(){l = r = NULL, v = 0;}
    Node(Node *l, Node *r, int v){this->l = l; this->r = r; this-> v = v;}
};
ll arr[(int)1e5+7];
Node root;

void init(Node *node, int s,int e)
{
    if(s == e)
    {
        node->v = (ll)arr[s];
        return;
    }
    int mid = (s+e)/2;
    node->l = new Node(); init(node->l,s,mid);
    node->r = new Node(); init(node->r,mid+1, e);
    node->v = (node->l->v) + (node->r->v);
}
ll query(Node *node, int s,int e, int a,int b)
{
    if(a <= s and e <= b) return node->v;
    if(b < s or e < a) return 0LL;
    int mid = (s+e)/2;
    return query(node->l,s,mid,a,b) + query(node->r, mid+1,e,a,b);
}
void update(Node *node, int s,int e, int x, int v)
{
    if(x < s or e < x) return;
    else if(s == e)
        node->v = v;
    else
    {
        int mid = (s+e)/2;
        update(node->l,s,mid,x,v);
        update(node->r, mid+1, e,x,v);
        node->v = node->l->v + node->r->v;
    }
}
int main()
{
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lld", arr+i);
    init(&root, 1, n);
    int Q; scanf("%d", &Q);
    int query2num = 0;
    query1.push_back({0,0});
    while(Q--)
    {
        int a; scanf("%d",&a);
        int b,c,d;
        switch(a)
        {
        case 1:
            scanf("%d %d",&b,&c);
            query1.push_back({b,c});
            break;
        case 2:
            scanf("%d %d %d", &b,&c,&d);
            query2.push_back({{b,++query2num},{c,d}});
        }
    }
    sort(query2.begin(),query2.end());
    auto l = query2.begin();

    int m = query1.size();
    for(int i=0; i<m; i++)
    {
        update(&root,1,n,query1[i].first, query1[i].second);
        while(l->first.first == i)
            ans[l->first.second] = query(&root, 1,n,l->second.first, l->second.second), l++;
    }
    for(int i = 1; i <= query2num; i++) printf("%lld\n", ans[i]);
}