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

시험기간이라서 문제 스택만 이어가고 있다. 이번에 푼 문제는 어제 푼 문제랑 똑같이 Mo's Algorithm을 쓴다. 어제 문제랑 거의 똑같고, 계산만 조금 달라서 할 말은 없다.

이제부터 문제 풀 때 시간을 재 볼려 한다. 이 문제는 이해 ~5min / 코딩하는데 25m 21s 걸렸다. 얼마 정도 걸리는게 보통인지는 모르겠으나,  코딩이 꽤 느린 거 같아서 연습 좀 해야겠다는 생각이 든다.

BOJ 8462 배열의 힘
어제 문제랑 계산 방법만 조금 다르고 완전히 똑같다. EZ했고 주의해야할 점이 결과값이 int 범위를 넘는다는거. 그거만 주의하면 된다. 그거때매 1 wa 떴다.

#include<bits/stdc++.h>
using namespace std;
typedef vector<pair<int,pair<int,int> > > vipii;
typedef pair<int, pair<int,int> > pipii;
typedef pair<int, int> pii;

int n,sqrtn;
int arr[(int)1e5+7];
long long ans[(int)1e5+7], ret;
long long D[(int)1e6+7];
vipii q;
bool cmp(pipii a, pipii b)
{
    if(a.second.second / sqrtn == b.second.second / sqrtn) return a.second.first < b.second.first;
    return a.second.second / sqrtn < b.second.second / sqrtn;
}

void transition(pii a, pii b)
{
    while(b.first < a.first)
        ret -= (D[arr[--a.first]]*(D[arr[a.first]])*arr[a.first]), D[arr[a.first]]++,
        ret += (D[arr[a.first]]*(D[arr[a.first]]) * arr[a.first]);
    while(a.second < b.second)
        ret -= (D[arr[++a.second]]*(D[arr[a.second]])*arr[a.second]), D[arr[a.second]]++,
        ret += (D[arr[a.second]]*(D[arr[a.second]])*arr[a.second]);
    while(a.first < b.first)
        ret -= (D[arr[a.first]]*(D[arr[a.first]])*arr[a.first]), D[arr[a.first]]--,
        ret += (D[arr[a.first]]*(D[arr[a.first]])*arr[a.first++]);
    while(b.second < a.second)
        ret -= (D[arr[a.second]]*(D[arr[a.second]])*arr[a.second]), D[arr[a.second]]--,
        ret += (D[arr[a.second]]*(D[arr[a.second]])*arr[a.second--]);
}

int main()
{
    //freopen("output.txt", "w", stdout);
    int Q; scanf("%d %d",&n,&Q);
    sqrtn = (int) sqrt(n);
    for(int i = 1; i<= n; i++) scanf("%d", arr+i);
    for(int i = 1; i<=Q; i++)
    {
        int a,b; scanf("%d %d",&a,&b);
        q.push_back({i,{a,b}});
    }
    sort(q.begin(),q.end(), cmp);
    pii bef; bef.first = bef.second = 1;
    D[arr[1]] = 1; ret = arr[1];

    for(auto i : q)
    {
        transition(bef, i.second);
        bef = i.second; ans[i.first] = ret;
    }
    for(int i = 1; i <= Q; i++)
        printf("%lld\n", ans[i]);
}