2900 프로그램

 

시간복잡도를 신경써서 풀어야 하는 문제

마지막에 l부터 r까지 구하는 부분은 부분합으로 시간 복잡도를 줄일 수 있는데

jump 만큼 건너뛰는 부분을 어떻게 줄여야 할지 몰랐다. 

 

고민하다가 다른 사람 풀이를 보니 음?? 그냥 somthing 함수를 호출했다??

1씩 * 5번 뛰는 걸 한번에 더하긴 했지만 그래도 10^6 * 10^6이라 시간복잡도가 터지지 않을까 싶었다.

계산해보니 NlogN이 돼서 안 터진다.. 신기했다

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int N;
i64 a[1000005];
i64 sum[1000005];

void something(int jump, int count) {
    int i = 1;
    while (i <= N) {
        a[i] = a[i] + count;
        i = i + jump;
    }
}

int main() {
    int k;
    scanf("%d %d", &N, &k);
    
    map<int, int> mp;
    for (int i = 0; i < k; i++) {
        int x;
        scanf("%d", &x);
        
        mp[x]++;
    }
    
    for (auto mi : mp) {
        something(mi.xx, mi.yy);
    }
    
    int q;
    scanf("%d", &q);
    
    for (int i = 1; i <= N; i++) {
        sum[i] = a[i] + sum[i-1];
    }
    
    // for (int i = 1; i <= N; i++) {
    //     printf("%d ", sum[i]);
    // }
    
    for (int i = 0; i < q; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        
        printf("%lld\n", sum[r+1] - sum[l]);
    }
    
    return 0;
}