CSES 범위 쿼리 질문 : 급여 쿼리
이 문제를 해결하려고합니다. https://cses.fi/problemset/task/1144/
최대 200000요소 의 배열이 주어지면 내 작업은 200000배열 내의 단일 값을 업데이트하도록 요청하거나 주어진 범위에있는 a와 b 사이의 요소 수를 찾도록 요청 하는 쿼리 까지 처리하는 것 입니다. 인덱스에서 많은 요소가 어떻게 예, 쿼리가 물어 보곤 1하는 5범위에있다 [2, 3]).
내 현재 아이디어는 먼저 주어진 배열의 값에 인덱스 압축 을 사용하는 것입니다 (값이 최대 10^9일 수 있으므로 단순 발생 배열을 유지하면 스토리지 제한을 초과 함). 그런 다음 압축 된 각 항목의 수를 포함하는 다른 배열을 유지합니다. 번호. 그런 다음 합계 세그먼트 트리를 사용하여 쿼리 처리 및 업데이트를 수행 할 수 있습니다.
그러나이 접근 방식을 구현하는 동안 문제가 발생했습니다. 단일 배열 값을 업데이트하면 압축 된 배열을 변경해야한다는 것을 깨달았습니다.
예를 들어 배열이 주어지면 다음 과 같은 [1, 5, 3, 3, 2]압축 함수를 정의 C합니다.
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;
그러면 발생 배열은 [1, 1, 2, 1]이고 합계 쿼리를 처리하는 것이 효율적입니다. 그러나 값 을 업데이트 하라는 지시를 받은 경우, 예를 들어 세 번째 요소를으로 변경하면 4모든 것이 균형을 잃게됩니다. 압축 기능은 다음과 같이 변경해야합니다.
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;
이로 인해 발생 배열을 재구성하여 O(N)업데이트 시간이 발생 합니다.
이후 N하도록 할 수 있습니다 200000내가 인덱스 압축 올바른 생각을 가지고 있다고 생각하지만, 내 현재의 접근 방식은 문제를 해결하기 위해 효율적으로 충분히 작동하지 않습니다. 누군가 내 방법으로 올바른 방향으로 나를 가리킬 수 있습니까?
답변
인덱스 압축 사용에 대한 올바른 아이디어가 있습니다. N까지만 그렇듯이 200000발생 배열을 유지하려면 배열 인덱스 200000대신 주어진 배열의 초기 값에 대한 요소 가 많아야합니다 10^9.
자신에 따르면 문제는 쿼리를 처리하는 동안 새로운 값을 만날 때입니다. 네가 옳아; 이로 인해 발생 배열이 균형을 잃고 업데이트가 제 O(N)시간 에 실행되어야 합니다. 이 문제에 대한 해결책은 현재 방법을 약간 수정하는 것입니다.
새 값을 발생하는 문제를 해결하기 위해, 우리는 단지 우리가 있습니다 있는지 확인 할 수 결코 새로운 값을 발생하지 않습니다. 합계 세그먼트 트리를 구성 하기 전에 모든 쿼리를 읽어이를 수행 할 수 있습니다 . 이로 인해 최대 N + 2*Q고유 값이 생성되거나 600000최악의 경우 문제의 512MB 스토리지 제한으로 발생 배열을 구성 할 수 있습니다. 그 후, 합계 세그먼트 트리는 이러한 쿼리에 효율적으로 응답 할 수 있습니다.
따라서 결국이 문제를 해결하는 전략은 모든 고유 번호를 입력 한 다음 인덱스 압축 함수를 구성한 다음 합계 세그먼트 트리를 사용하여 합계 쿼리를 효율적으로 처리하는 것입니다.
미래에는 이러한 종류의 질의 응답 질문에서 사전 계산 전에 모든 입력을 읽는 것이 유용 할 수 있음을 기억하십시오 . 프로그램에 행운을 빕니다.
먼저 순진한 것을 고려하십시오. 각 업데이트에 대해 어레이를 업데이트하십시오. 각 쿼리에 대해 전체 어레이를 스캔하고 답을 수집합니다. 이 솔루션의 복잡성에는 O(n)업데이트, O(n)쿼리가 있습니다. 좋지 않다.
시간 복잡성이 더 나쁜 다른 해결책을 생각 해낼 수 있지만 최종 결과가 무엇인지에 대한 힌트를 제공합니다. 항상 소스 배열을 유지하고 값-> 주파수의 해시 맵을 유지하십시오. 그런 다음 업데이트 할 때 이전 값에서 빈도를 줄이고 새 값에서 증가시킵니다. 이제 쿼리의 경우 해당 쿼리 범위의 모든 값을 반복하고 답을 합산하십시오. 이로 인해 O(1)업데이트 및 O(r-l)쿼리가 발생하므로 우수한 업데이트가 있지만 끔찍한 쿼리가 있습니다. 그러나이 결과는 우리가 할 수있는 경우에 개선 될 수있다 다만 그 쿼리 속도! 세그먼트 트리를 입력합니다 .
전통적으로, 당신은 생성시 잎까지 세그먼트 트리를 구성했습니다. 그러나 명목상에서 범위의 세그먼트 트리를 좋아 0-10^9하므로 그렇게 많은 메모리를 생성 할 수있는 방법이 전혀 없습니다 (그리고 그렇게하는 데 시간이 초과됩니다). 그러나 세그먼트 트리를 만들지 만 모든 노드에 대해 사용 된 적이 없다면 그 자식이 암시 적이 라면 어떨까요 ? 즉, 요소가없는 경우 하위 노드를 만들지 마십시오 . 이 구조는 적절하게 암시 적 세그먼트 트리 라고 명명됩니다.. 여기서 아이디어는 왼쪽 및 오른쪽 자식을 초기화하는 생성자에서 부분을 건너 뛰는 것을 제외하고는 세그먼트 트리를 정상적으로 구현하는 것입니다. 이제 부분 범위 쿼리로 인해 자녀를 조사해야 할 때 자녀가 존재하는지 확인하고 존재하지 않는 경우 새로 만듭니다. 그렇지 않으면 만들 필요가 없었으므로 해당 노드의 값 합계를 0이라고 가정합니다!
최종 솔루션은 다음과 같습니다. 쿼리 가능한 최대 값의 세그먼트 트리를 만듭니다 (대화식으로 대답 할 필요가없는 경우 쿼리를 저장하고 스캔하여 최대 r- 값을 찾는 것이 좋지만 그럴 필요는 없습니다). 이것을 암시 적 세그먼트 트리로 만드는 것에 유의하십시오 . 업데이트 할 때마다 소스 어레이를 유지하고 트리에서 O(log(max value)). 쿼리는 일반 세그먼트 트리 범위 쿼리이므로 O(log(max value)). 그리고 있습니다!
주어진 수보다 적은 수의 항목을 반환하는 order_of_key ()와 같은 유용한 메서드가있는 정책 기반 데이터 구조를 사용할 수 있습니다. getcnt (b + 1)-getcnt (a)-주어진 범위 사이의 항목 수를 제공하는 것처럼 두 번 호출 할 수 있습니다. 이에 대한 자세한 정보는-참조 할 수 있습니다-https://codeforces.com/blog/entry/11080 그리고 또한 https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html
많은 연구 끝에이 STL이 트리 기반 구조를 사용하는 동안 매우 유용하다는 것을 발견했습니다.
아래 코드를 테스트했고 모든 테스트 케이스를 통과했습니다.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
template<class T> using cust_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
cust_set<array<int,2>> freq;
int getcnt(int x)
{
return freq.order_of_key({x,0});
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
vector<int> emp(n);
int sal;
for(int i=0;i<n;i++)
{
cin >> emp[i];
freq.insert({emp[i],i});
}
char c;
int x,a,b;
while(q--)
{
cin>> c;
int ans=0;
if(c=='?')
{
cin>>a>>b;
cout << getcnt(b+1) - getcnt(a)<<"\n";
}
else
{
cin>>a>>b;
--a;
freq.erase({emp[a],a});
emp[a] = b;
freq.insert({emp[a],a});
}
}
return 0;
}