13547 수열과 쿼리5 https://www.acmicpc.net/problem/13547
요즘 고급(?) 알고리즘 기술들을 습득하고있다.
이 문제또한 이 기술에 해당된다.
배열이 주어지고 부분배열안에 자연수 $s$의 개수를 $K_{s}$라고 칭한다.
부분배열의 힘은 $K_{s}*K_{s}*s$로 나타낸다.
이러한 query를 처리하는 문제이다.
단도직입적으로 말하면 이 문제는 Mo's algorithm으로 풀 수 있다.
이 알고리즘은 query를 정렬시키는데 sqrt-decomposition개념이 들어간다.
개념은 어렵지 않다.
query가 [Left, Right]으로 입력이 들어온다면 query를 정렬시킬 때
Left / $\sqrt{N}$가 작은순서로 정렬 시킨다.
만약 같다면 Right값이 작은순서로 정렬시킨다.
그 후 query를 돌리면서 현재 Left, Right과 query의 Left,Right값에 따라
확장(Insert), 축소(Remove)시킨다.
여기서 $\sqrt{N}$으로 나누어 처리하는 이유는 다음과 같은 query 입력을 생각하면 알 수 있다.
$\sqrt{N}$이 4이고 Left값을 나누지 않고 정렬한 query는 위와 같은 모습일 것이다.
이는 기존에 Left, Right가 각각 0, 1이라 하면
1번 query에서 8번확장, 2번 query에서 8번축소, 3번 query에서 1번축소와 7번확장,
4번 query에서 1번확장과 5번 축소로 도합 30번의 연산을 한다.
이번에는 $\sqrt{N}$으로 나누고 정렬한 query를 보도록 하자.
위의 query는 모든 Left값이 $\sqrt{N}$으로 나누어지면 동일해지기 때문에 Right값에 의존된다.
1번 query에서 1번확장과 1번축소, 2번 query에서 2번확장, 2번축소,
3번 query에서 6번확장, 4번 query에서 2번확장 도합 14번의 연산을 한다.
이 과정을 통해서 O($\sqrt{N}*$($N+Q$))의 복잡도로 해결할 수 있다고 한다.
이 개념이 끝이다. 정말 간단하다.
문제로 돌아가면 Insert, Remove를 숫자들의 갯수를 미리 저장하여 $O(1)$에 할 수 있다.
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int sq;
struct Query {
int idx, l, r;
int V;
long long ans;
Query(int ii, int ll, int rr) :idx(ii), l(ll), r(rr), V(l / sq) {}
};
int N, M;
int arr[100000];
long long number[1000001];
void Remove(long long &sum, int data) {
long long prev = number[data] * number[data] * 1LL * data;
sum -= prev;
number[data]--;
sum += (number[data] * number[data] * 1LL * data);
}
void Insert(long long &sum, int data) {
long long prev = number[data] * number[data] * 1LL * data;
sum -= prev;
number[data]++;
sum += (number[data] * number[data] * 1LL * data);
}
int main() {
scanf("%d%d", &N, &M);
sq = (int)sqrt(N);
for (int n = 0;n < N;n++) scanf("%d", &arr[n]);
vector<Query> save;
for (int m = 0;m < M;m++) {
int u, v;
scanf("%d%d", &u, &v);
if (u > v) swap(u, v);
u--, v--;
save.emplace_back(Query(m, u, v));
}
sort(save.begin(), save.end(), [&](Query const &a, Query const &b)->bool {
if (a.V == b.V) return a.r < b.r;
return a.V < b.V;
});
int L = save[0].l, R = save[0].l - 1;
long long sum = 0;
for (int m = 0;m < M;m++) {
while (L < save[m].l) {
Remove(sum, arr[L]);
L++;
}
while (L > save[m].l) {
L--;
Insert(sum, arr[L]);
}
while (R < save[m].r) {
R++;
Insert(sum, arr[R]);
}
while (R > save[m].r) {
Remove(sum, arr[R]);
R--;
}
save[m].ans = sum;
}
sort(save.begin(), save.end(), [&](Query const &a, Query const &b)->bool {
return a.idx < b.idx;
});
for (int m = 0;m < M;m++) printf("%lld\n", save[m].ans);
return 0;
}
| cs |
수열과 쿼리5문제도 Mo's algorithm으로 해결할 수 있다.
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct Save {
int l, r;
int idx;
};
int N, M;
int arr[100001];
int ret[100001];
int chk[1000001];
int sq;
Save query[100001];
int ans;
void Insert(int idx) {
if (!chk[arr[idx]]) ans++;
chk[arr[idx]]++;
}
void Remove(int idx) {
chk[arr[idx]]--;
if (!chk[arr[idx]]) ans--;
}
int main() {
scanf("%d", &N);
sq = (int)sqrt(N);
for (int n = 0;n < N;n++) scanf("%d", &arr[n]);
scanf("%d", &M);
for (int m = 0;m < M;m++) scanf("%d%d", &query[m].l, &query[m].r), query[m].l--, query[m].r--, query[m].idx = m;
if (N == 1) {
for (int m = 0;m < M;m++) printf("1\n");
return 0;
}
sort(query, query + M, [](Save &a, Save &b)->bool {
return a.l / sq == b.l / sq ? a.r < b.r : a.l / sq < b.l / sq;
});
int l = 0, r = 1;
Insert(0); Insert(1);
for (int m = 0;m < M;m++) {
while (query[m].r < r) Remove(r--);
while (query[m].r > r) Insert(++r);
while (query[m].l < l) Insert(--l);
while (query[m].l > l) Remove(l++);
ret[query[m].idx] = ans;
}
for (int m = 0;m < M;m++) printf("%d\n", ret[m]);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기