SRM 675 Div.1 LimitedMemorySeries1

문제 링크 : http://community.topcoder.com/stat?c=problem_statement&pm=14088

문제 내용 : 5,000,000만 개의 수 X(i)가 있을 때에, Q 개의 쿼리 query(i)에 대해서 전체 X를 오름차순 정렬하였을 때에 query(i)번째 원소를 출력하는 문제이다. 하지만 메모리 제한이 2MB라서 X를 전부 저장해 둘 수 없다. X에 대한 일차 함수식은 (X(i-1)*A + B) % 10억7 이다. 쿼리 개수는 100개 이하이다.

풀이 1 : 버킷, 평방분할

수의 범위가 0~10억6인데, 이 범위를 크기가 D인 루트개의 구간으로 평방분할한다. X(i) / D의 구간에 X가 몇 개인지 누적해둔다. 그럼 각 쿼리에 대해서 O(D)에 query(i)번째 원소가 어느 구간에 있는지 알 수 있고, 해당 구간에 대한 counting 배열을 만들어서 구간 [L, L+D) 를 [0, D)로 바꾸어 i이하인 수가 몇 개인지 누적할 수 있다. 

풀이2 : Parallel Binary Search

각 쿼리에 대해 답의 구간에 대한 정보도 들고 다니게 한다. 처음엔 [0~10억6]이겠다. 쿼리에 대해서 답의 구간을 이분탐색해야 하는데, 이걸 각 쿼리마다 수행하는 것이 아니라 모든 쿼리의 중간값들을 모아놓고 함께 처리한다. k번째 step에서 모든 쿼리에 대한 중간값이 오름차순이 되도록 쿼리들을 정렬한 다음에 X(0)부터 X(N-1)까지에 대해서 쿼리 중간값을 각각 이분탐색해본다. 현재 X에 대해 이분탐색했을 때 t ~ Q-1번째 쿼리까지의 중간값이 X보다 크다면 t~Q-1번째 쿼리들에 대해서는 현재 X가 답이 되는 원소보다 작거나 같다는 것이므로 cnt[t]++해주고, 모든 X에 대해서 다 해주었다면 나중에 cnt[i] += cnt[i-1]해서 cnt[i]가 query(i)보다 큰 지의 여부로 i번째 쿼리의 구간을 조절해주면 된다. 시간복잡도는 O(N lg X lg Q)

const int sz = 20000;
struct query {
	int s, e, k, m, res;
} qu[105];
int qn, cnt[105];
const int mod = 1000000007;
inline bool cmp(query q1, query q2) {
	return q1.m < q2.m;
}
class LimitedMemorySeries1 {
public:
	void upd(int X) {
		int lo = 0, hi = qn - 1, md, F = qn;
		while (lo <= hi) {
			md = (lo + hi) / 2;
			if (qu[md].m < X) lo = md + 1;
			else {
				F = min(F, md);
				hi = md - 1;
			}
		}
		cnt[F]++;
	}
	long long getSum(int n, int x0, int a, int b, vector <int> q) {
		sort(q.begin(), q.end());
		qn = q.size();
		for (int i = 0; i < qn; i++) qu[i] = { 0, mod - 1, q[i], 0, mod - 1 };
		long long res = 0;
		for (int K = 0; K < 32; K++) {
			for (int i = 0; i < qn; i++) qu[i].m = (qu[i].s + qu[i].e) / 2;
			sort(qu, qu + qn, cmp);
			for (int i = 0; i < qn; i++) cnt[i] = 0;
			int qi = 0;
			long long X;
			X = x0;
			upd(X);
			for (int i = 1; i < n; i++) {
				X = (X*a + b) % mod;
				upd(X);
			}
			for (int i = 1; i < qn; i++) cnt[i] += cnt[i - 1];
			for (int i = 0; i < qn; i++) {
				if (cnt[i] > qu[i].k) qu[i].e = qu[i].m - 1, qu[i].res = min(qu[i].res, qu[i].m);
				else qu[i].s = qu[i].m + 1;
			}
		}
		for (int i = 0; i < qn; i++) res += qu[i].res;
		return res;
	}
};