Cod sursa(job #1708435)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 27 mai 2016 00:45:48
Problema Pq Scor Ascuns
Compilator cpp Status done
Runda Marime 5.09 kb
#include <assert.h>
#include <stdio.h>
#include <vector>
#include <set>

using namespace std;

#define BRUTE_FORCE 1
#define DEBUG 0
#define NMAX 131072
#define VMAX 100000
#define MAXELEMS 10000000

int A[NMAX], N, Q;

void ReadInput() {
	scanf("%d %d", &N, &Q);
	assert(1 <= N && N <= 100000);
	assert(1 <= Q && Q <= 100000);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
		assert(0 <= A[i] && A[i] < VMAX);
	}
}

int poz[VMAX], pred[NMAX], cpred[NMAX];

void FindPredecessors() {
	for (int i = 0; i < VMAX; i++) poz[i] = 0;
	for (int i = 1; i <= N; i++) {
		pred[i] = poz[A[i]];
		cpred[i] = i - pred[i];
		poz[A[i]] = i;
	}
}

int ppred[MAXELEMS], plen[MAXELEMS], plenmax[MAXELEMS], nelems;
int li[2 * NMAX], ls[2 * NMAX], pstart[2 * NMAX];

void BuildSegmentTree() {
	nelems = 0;
	for (int node = NMAX; node < 2 * NMAX; node++) {
		li[node] = ls[node] = node - NMAX + 1;
		pstart[node] = nelems++;
		if (li[node] <= N) {
			ppred[pstart[node]] = pred[li[node]];
			plen[pstart[node]] = plenmax[pstart[node]] = li[node] - pred[li[node]];
		} else {
			ppred[pstart[node]] = plen[pstart[node]] = plenmax[plen[pstart[node]]] = 0;
		}
	}
	for (int node = NMAX - 1; node >= 1; node--) {
		int lson = node << 1;
		int rson = lson + 1;
		li[node] = li[lson];
		ls[node] = ls[rson];
		pstart[node] = nelems;
		nelems += (ls[node] - li[node] + 1);
		int nelemslson = ls[lson] - li[lson] + 1;
		int nelemsrson = ls[rson] - li[rson] + 1;
		int idxlson = 0, idxrson = 0, idxnode = 0;
		while (idxlson < nelemslson && idxrson < nelemsrson) {
			if (ppred[pstart[lson] + idxlson] <= ppred[pstart[rson] + idxrson]) {
				ppred[pstart[node] + idxnode] = ppred[pstart[lson] + idxlson];
				plen[pstart[node] + idxnode] = plen[pstart[lson] + idxlson];
				idxlson++;
				idxnode++;
			} else {
				ppred[pstart[node] + idxnode] = ppred[pstart[rson] + idxrson];
				plen[pstart[node] + idxnode] = plen[pstart[rson] + idxrson];
				idxrson++;
				idxnode++;
			}
		}
		for (; idxlson < nelemslson; idxlson++) {
			ppred[pstart[node] + idxnode] = ppred[pstart[lson] + idxlson];
			plen[pstart[node] + idxnode] = plen[pstart[lson] + idxlson];
			idxnode++;
		}
		for (; idxrson < nelemsrson; idxrson++) {
			ppred[pstart[node] + idxnode] = ppred[pstart[rson] + idxrson];
			plen[pstart[node] + idxnode] = plen[pstart[rson] + idxrson];
			idxnode++;
		}
		plenmax[pstart[node] + idxnode - 1] = plen[pstart[node] + idxnode - 1];
		for (idxnode--; idxnode >= 0; idxnode--) {
			plenmax[pstart[node] + idxnode] = plen[pstart[node] + idxnode];
			if (plenmax[pstart[node] + idxnode + 1] > plenmax[pstart[node] + idxnode])
				plenmax[pstart[node] + idxnode] = plenmax[pstart[node] + idxnode + 1];
		}
	}
}

vector<int> lpoz[NMAX];
set<int> lset;
int vlen[NMAX], nvlen;

void PreprocessBruteForce2() {
	for (int i = 1; i <= N; i++) {
		if (!pred[i]) continue;
		int len = i - pred[i];
		lset.insert(len);
		lpoz[len].push_back(i);
	}
	nvlen = 0;
	for (const auto& len : lset)
		vlen[nvlen++] = len;
}

int L, R, QANS;

void QuerySegTree(int node) {
	if (L <= li[node] && ls[node] <= R) {
		int nelems = ls[node] - li[node] + 1;
		if (DEBUG) {
			fprintf(stderr, "[QuerySegTree] node=%d[%d-%d] nelems=%d\n", node, li[node], ls[node], nelems);
			for (int i = 0; i < nelems; i++)
				fprintf(stderr, " %d: ppred=%d plen=%d plenmax=%d\n", i, ppred[pstart[node] + i], plen[pstart[node] + i], plenmax[pstart[node] + i]);
		}
		
		int idxmin = 0, idxmax = nelems - 1, idxsplit = nelems;
		while (idxmin <= idxmax) {
			int mid = (idxmin + idxmax) >> 1;
			if (ppred[pstart[node] + mid] < L) {
				idxmin = mid + 1;
			} else {
				idxsplit = mid;
				idxmax = mid - 1;
			}
		}
		if (idxsplit < nelems && plenmax[pstart[node] + idxsplit] > QANS)
			QANS = plenmax[pstart[node] + idxsplit];
		return;
	}
	int lson = node << 1;
	int rson = lson + 1;
	if (L <= ls[lson]) QuerySegTree(lson);
	if (R >= li[rson]) QuerySegTree(rson);
}

void ProcessQueries() {
	while (Q--) {
		scanf("%d %d", &L, &R);
		assert(1 <= L && L <= R && R <= N);
		QANS = -1;
		if (BRUTE_FORCE == 1) {
			for (int i = L; i <= R; i++)
				if (pred[i] >= L && cpred[i] > QANS) QANS = cpred[i];
		} else if (BRUTE_FORCE == 2) {
			for (int lidx = nvlen - 1; lidx >= 0; lidx--) {
				int len = vlen[lidx];
				if (len > R - L) continue;
				int idxmin = 0, idxmax = lpoz[len].size() - 1;
				int idxans = idxmax + 1;
				while (idxmin <= idxmax) {
					int mid = (idxmin + idxmax) >> 1;
					if (lpoz[len][mid] <= R) {
						idxans = mid;
						idxmin = mid + 1;
					} else idxmax = mid - 1;
				}
				if (idxmax < lpoz[len].size()) {
					int r = lpoz[len][idxmax];
					if (r - len >= L) {
						QANS = len;
						break;
					}
				}
			}
		} else {
			QuerySegTree(1);
		}
		printf("%d\n", QANS);
		//fprintf(stderr, "nqleft=%d\n", Q);
	}
}

int main() {
	freopen("pq.in", "r", stdin);
	freopen("pq.out", "w", stdout);
	ReadInput();
	FindPredecessors();
	if (!BRUTE_FORCE) BuildSegmentTree();
	else if (BRUTE_FORCE == 2) PreprocessBruteForce2();
	ProcessQueries();
	return 0;
}