Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Mar 13th, 2018 52 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. typedef long long int ll;
  5. int n, m, k;
  6. ll arr[1000001];
  7. ll tree[3000100];
  8.  
  9. ll makeTree(int left,int right,int node ) {
  10.  
  11.     if (left == right) { //기저사례
  12.         return tree[node] = arr[left];
  13.     }
  14.  
  15.     int mid = (left + right) / 2;
  16.  
  17.     tree[node] += makeTree(left, mid, node * 2);//왼쪽 노드 합
  18.     tree[node] += makeTree(mid + 1,right, node * 2 +1);//오른쪽 노드 합
  19.  
  20.     return tree[node];
  21. }
  22.  
  23. void upDate(int left,int right,int node, int change_node ,ll diff) {
  24.  
  25.     if (!(left <= change_node &&change_node <= right))return; //영향이 없으므로...
  26.  
  27.     tree[node] += diff;
  28.  
  29.     if (left != right) {
  30.         int mid = (left + right) / 2;
  31.         upDate(left, mid, node * 2, change_node, diff);
  32.         upDate(mid +1,right, node * 2 +1, change_node, diff);
  33.     }
  34. }
  35.  
  36. ll sum(int node, int left, int right, int start, int end) {
  37.    
  38.     if (right < start || end < left)return 0; //구간밖
  39.  
  40.     if (start <= left && right <= end)return tree[node];//포함관계라면
  41.  
  42.     int mid = (left + right) / 2;
  43.  
  44.     return sum(node * 2, left, mid, start, end)+sum(node*2+1,mid+1,right,start,end);
  45. }
  46. int main() {
  47.  
  48.     scanf("%d %d %d", &n, &m, &k);
  49.     for (int i = 1; i <= n; i++)scanf("%lld", &arr[i]);
  50.    
  51.     //구간합 트리만들기
  52.     makeTree(1, n, 1);
  53.  
  54.     for (int i = 0; i < k + m; i++) {
  55.         int cmd, b;ll c;
  56.         scanf("%d %d %lld", &cmd, &b, &c);
  57.        
  58.         if (cmd == 1) { //변경
  59.             ll diff = c - arr[b];
  60.             arr[b] = c;
  61.             upDate(1, n, 1, b, diff);//1부터 n까지 1(루트)부터시작, b인덱스변경
  62.         }
  63.         else { //합 출력
  64.             // 1(루트부터) 1부터n범위탐색해서 b부터 c구간합 찾기
  65.             printf("%lld\n", sum(1, 1, n , b , c));
  66.         }
  67.     }
  68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top