Cod sursa(job #37934)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 25 martie 2007 13:07:22
Problema Distincte Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.96 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 101000
#define LOGMAX 18
#define PX 666013

int v[NMAX], poz[NMAX], vaux[NMAX], paux[NMAX], ci[NMAX * 2], cs[NMAX * 2], sum[NMAX * 2];
int ORSTdim[NMAX * 2], vx[NMAX >> 1], vy[NMAX >> 1], ve[NMAX >> 1];
int *ORSTx[NMAX * 2], **ORSTy[NMAX * 2], *ORSTci[NMAX * 2], *ORSTcs[NMAX * 2], **ORSTsum[NMAX * 2];
int i, j, k, l, N, M, P;

void msortvx(int li, int ls, int n)
{
	int i, j, k, m;

	if (li >= ls)
		return;

	m = (li + ls) >> 1;

	msortvx(li, m, n);
	msortvx(m + 1, ls, n);

	i = k = li; j = m + 1;

	while (i <= m && j <= ls)
	{
		if (vx[i] < vx[j])
		{
			ORSTx[n][k] = vx[i];
			ORSTy[n][0][k] = vy[i];
			ORSTsum[n][0][k] = ve[i];
			k++;
			i++;
		}
		else
		{
			ORSTx[n][k] = vx[j];
			ORSTy[n][0][k] = vy[j];
			ORSTsum[n][0][k] = ve[j];
			k++;
			j++;
		}
	}

	if (i <= m)
	{
		for (j = i; j <= m; j++)
		{
			ORSTx[n][k] = vx[j];
			ORSTy[n][0][k] = vy[j];
			ORSTsum[n][0][k] = ve[j];
			k++;
		}
	}
	else // j <= ls
	{
		for (i = j; i <= ls; i++)
		{
			ORSTx[n][k] = vx[i];
			ORSTy[n][0][k] = vy[i];
			ORSTsum[n][0][k] = ve[i];
			k++;
		}
	}

	for (k = li; k <= ls; k++)
	{
		vx[k] = ORSTx[n][k];
		vy[k] = ORSTy[n][0][k];
		ve[k] = ORSTsum[n][0][k];
	}
}

void msortORST(int li, int ls, int niv, int n1, int n)
{
	int i, j, k, m;

	if (li > ls)
		return;

	ORSTci[n][n1] = li;
	ORSTcs[n][n1] = ls;

	if (li >= ls)
	{
		ORSTy[n][niv][li] = vy[li];
		ORSTsum[n][niv][li] = ve[li] % PX;
		return;
	}

	m = (li + ls) >> 1;

	msortORST(li, m, niv + 1, (n1 << 1), n);
	msortORST(m + 1, ls, niv + 1, (n1 << 1) + 1, n);

	i = li; j = m + 1; k = li;

	while (i <= m && j <= ls)
	{
		if (vy[i] < vy[j])
		{
			ORSTy[n][0][k] = vy[i];
			ORSTsum[n][0][k] = ve[i];
			k++;
			i++;
		}
		else
		{
			ORSTy[n][0][k] = vy[j];
			ORSTsum[n][0][k] = ve[j];
			k++;
			j++;
		}
	}

	if (i <= m)
	{
		for (j = i; j <= m; j++)
		{
			ORSTy[n][0][k] = vy[j];
			ORSTsum[n][0][k] = ve[j];
			k++;
		}
	}
	else // j <= ls
	{
		for (i = j; i <= ls; i++)
		{
			ORSTy[n][0][k] = vy[i];
			ORSTsum[n][0][k] = ve[i];
			k++;
		}
	}

	for (k = li; k <= ls; k++)
	{
		vy[k] = ORSTy[n][0][k];
		ve[k] = ORSTsum[n][0][k];
	}

	ORSTy[n][niv][li] = vy[li];
	ORSTsum[n][niv][li] = ve[li] % PX;

	for (k = li + 1; k <= ls; k++)
	{
		ORSTy[n][niv][k] = vy[k];
		ORSTsum[n][niv][k] = (ORSTsum[n][niv][k - 1] + ve[k]) % PX;
	}
}

void buildORST(int n)
{
	P = 1, l = 1;
	while (P < ORSTdim[n])
		P <<= 1, l++;

	
	for (i = ORSTdim[n] + 1; i <= P; i++)
		vx[i] = N + i, vy[i] = ve[i] = 0;
	
	ORSTdim[n] = P;
	

	ORSTx[n] = (int *) malloc((ORSTdim[n] + 1) * sizeof(int));
	ORSTy[n] = (int**) malloc(l * sizeof(int*));
	ORSTsum[n] = (int**) malloc(l * sizeof(int*));

	for (i = 0; i < l; i++)
	{
		ORSTy[n][i] = (int*) malloc((ORSTdim[n] + 1) * sizeof(int));
		ORSTsum[n][i] = (int*) malloc((ORSTdim[n] + 1) * sizeof(int));
	}

	msortvx(1, ORSTdim[n], n);

	ORSTci[n] = (int *) malloc(2 * (ORSTdim[n] + 1) * sizeof(int));
	ORSTcs[n] = (int *) malloc(2 * (ORSTdim[n] + 1) * sizeof(int));

	for (i = 1; i <= ORSTdim[n]; i++)
		ORSTx[n][i] = vx[i];

	msortORST(1, ORSTdim[n], 0, 1, n);
}

inline int q2ORST(int li, int ls, int ymax, int n, int n1, int niv)
{
	int cmid = (ORSTci[n][n1] + ORSTcs[n][n1]) >> 1;
	int yp, yli, yls, ymid;

	if (li == ORSTci[n][n1] && ls == ORSTcs[n][n1])
	{
		if (ymax < ORSTy[n][niv][ORSTci[n][n1]])
			return 0;

		yli = ORSTci[n][n1]; yls = ORSTcs[n][n1];
		yp = 1;

		while (yli <= yls)
		{
			ymid = (yli + yls) >> 1;

			if (ORSTy[n][niv][ymid] <= ymax)
			{
				yp = ymid;
				yli = ymid + 1;
			}
			else
				yls = ymid - 1;
		}

		return ORSTsum[n][niv][yp];
	}

	if (ls <= cmid)
		return q2ORST(li, ls, ymax, n, (n1 << 1), niv + 1);

	if (li > cmid)
		return q2ORST(li, ls, ymax, n, (n1 << 1) + 1, niv + 1);

	return (q2ORST(li, cmid, ymax, n, (n1 << 1), niv + 1) + q2ORST(cmid + 1, ls, ymax, n, (n1 << 1) + 1, niv + 1));
}

inline int qORST(int xmax, int ymax, int n)
{
	int xp, li, ls, mid;

	if (ORSTdim[n] <= 0)
		return 0;

	li = 1; ls = ORSTdim[n];
	xp = 0;

	while (li <= ls)
	{
		mid = (li + ls) >> 1;

		if (ORSTx[n][mid] <= xmax)
		{
			xp = mid;
			li = mid + 1;
		}
		else
			ls = mid - 1;
	}

	if (xp > 0)
		return q2ORST(1, xp, ymax, n, 1, 0);
	
	return 0;
}

void mergesort(int li, int ls, int n)
{
	int m;

	if (li > ls || n > (2 * NMAX - 1))
		return;

	ci[n] = li;
	cs[n] = ls;
	ORSTdim[n] = 0;

	if (li >= ls)
	{
		sum[n] = v[li] % PX; 
		return;
	}

	m = (li + ls) >> 1;

	mergesort(li, m, n << 1);
	mergesort(m + 1, ls, (n << 1) + 1);

	// compute position intervals

	i = li; j = m + 1;

	while (i <= m && j <= ls)
	{
		while (i < m && v[i] == v[i + 1])
			i++;

		if (v[i] == v[j])
		{
			// we have common position interval [ poz[i], poz[j] ]

			//fprintf(stderr, "n=%d,v=%d,p1=%d,x=%d,cmid=%d,p2=%d\n", n, v[i], poz[i], m - poz[i] + 1, m, poz[j]);

			ORSTdim[n]++;
			vx[ORSTdim[n]] = m - poz[i] + 1;
			vy[ORSTdim[n]] = poz[j];
			ve[ORSTdim[n]] = v[i];
			//ve.push_back(make_pair(v[i], make_pair(cmid[n] - poz[i] + 1, poz[j])));

			while (j < ls && v[j] == v[j + 1])
				j++;
			j++;
		}
		else
		if (v[i] < v[j])
			i++;
		else
		{
			while (j < ls && v[j] == v[j + 1])
				j++;
			j++;
		}
	}

	// build an orthogonal range search tree for the common pairs

	if (ORSTdim[n] > 0)
		buildORST(n);

	// merge

	i = li; j = m + 1; k = li;

	while (i <= m && j <= ls)
	{
		if (v[i] <= v[j])
		{
			vaux[k] = v[i];
			paux[k] = poz[i];
			k++;
			i++;
		}
		else
		{
			vaux[k] = v[j];
			paux[k] = poz[j];
			k++;
			j++;
		}
	}

	if (i <= m)
	{
		for (j = i; j <= m; j++)
		{
			vaux[k] = v[j];
			paux[k] = poz[j];
			k++;
		}
	}
	else // j <= ls
	{
		for (i = j; i <= ls; i++)
		{
			vaux[k] = v[i];
			paux[k] = poz[i];
			k++;
		}
	}

	for (k = li; k <= ls; k++)
		v[k] = vaux[k],
		poz[k] = paux[k];

	sum[n] = v[li] % PX;
	for (k = li + 1; k <= ls; k++)
		if (v[k] > v[k - 1])
			sum[n] = (sum[n] + v[k]) % PX;
}

inline int query(int li, int ls, int n)
{
	int cmid = (ci[n] + cs[n]) >> 1;

	if (li == ci[n] && ls == cs[n])
		return sum[n];

	if (ls <= cmid)
		return query(li, ls, (n << 1));

	if (li > cmid)
		return query(li, ls, (n << 1) + 1);

	return (query(li, cmid, (n << 1)) + query(cmid + 1, ls, (n << 1) + 1) - qORST(cmid - li + 1, ls, n) + PX) % PX;
}

int main()
{
	freopen("distincte.in", "r", stdin);

	scanf("%d %d %d", &N, &k, &M);

	for (i = 1; i <= N; i++)
		scanf("%d", &v[i]);

	/*
	P = 1;
	while (P < N)
		P <<= 1;

	for (i = N + 1; i <= P; i++)
		v[i] = 0;

	N = P;
	*/

	for (i = 1; i <= N; i++)
		poz[i] = i;

	mergesort(1, N, 1);

	freopen("distincte.out", "w",stdout);

	while (M--)
	{
		scanf("%d %d", &i, &j);
		printf("%d\n", query(i, j, 1));
	}

	return 0;
}