Текущ брой на Списание ИнфоМан
 


Международна олимпиада по информатика 2005, Задача 1.3. MOUNTAINS

Уловието на задачата може да прочетете тук.

Решение

За решението на тази задача може да се използва двоично дърво. Всеки от върховете му описва интервал (брой последователни участъци) J = [2kt,2k(t+1)), което означава, че този интервал включва участъците между точките с x-координати 2kt и 2k(t+1), за някакви цели числа kи t. Всеки връх пази две стойности:

SJ = Σdi , където iе от интервала J;

HJ = max({Σ2kt≤i≤j di, за всички j от интервала J}), а ако HJ е отрицателно HJприема стойност 0;

Един връх е листо ако всички стойности diв интервала, за който отговаря този връх са равни. В този случай пресмятането на SJ и HJ е тривиално. Ако върхът не е листо, той има два наследника, отговарящи за интервали J1 = [2k-12t,2 k-1(2t+1)) и J2 = [2k-1(2t+1),2 k-1*(2t+2)). Стойностите за интервала Jсе пресмятат по следния начин: SJ = SJ1 + SJ2и HJ = max(HJ1,SJ1+HJ2). Коренът на дървото отговаря за интервала [0,2p), където p e най-малкото число, за което 2p >= n.

Когато се извършва промяна на наклона на някой интервал трябва да се обходи дървото като се започне от корена му. Ако даден връх, който се разглежда, е изцяло в интервала на промяната той става листо и пресмятането на двете стойности за този връх е тривиално. В противен случай, ако някаква част от интервалите, за които отговарят двата наследника на разглеждания връх, е в интервала на промяна, то се извършва същата стъпка и за тях. Ако те не съществуват се създават динамично. Това може да се реализира рекурсивно.

При запитванията обхождането на дървото отново се започва от корена. Ако в целия интервал няма по-голяма височина от зададената, отговорът е n. В противен случай, ако височината в левия наследник е по-голяма от зададената, обхождането продължава към този връх, ако не – към десния наследник. По този начин пътят от корена на дървото до някое негово листо преминава само през върхове, които отговарят на интервал, в който има височина, която е по-голяма от зададената. Обхождането спира, когато се достигне листо в дървото. В този случай вече лесно може да се провери къде точно ще спре колата.

Смяната на наклона на участъците изисква добавяне или промяна на най-много 2pвърха. Обработка на въпрос изисква да се обходят най-много pвърха. Ето защо това решение има сложност O((I+Q).logn)и сложност по памет O(I.logn). Примерното решение по-долу имплементира тази идея.

Съществува и по-добро решение от описаното по-горе. Може да се извърши компресиране на координатите, тъй като важни са само краищата на интервалите на промяна. Ако се разгледат само те като координати може да се построи статично дърво като това по-горе, вместо да се създава динамично. Възможно е да се прочетат предварително всички заявки от входа и да се направи това. Тогава координатите ще са 2I на брой. Междинните координати не са важни, тъй като отсечките между тях си сменят наклона винаги заедно и могат да се разглеждат като една цяла отсечка. Тогава сложността е O((I+Q).logI), а сложността по памет е O(I+Q).

Примерна реализация


#include <stdio.h>
#include <stdlib.h>

struct treenode
{
	int sum,h;
	treenode *left,*right;
};

int n;
treenode *root;
int stdv[33];
int deg;

void makeNewNode(treenode *curn, int val, int k, int t)
{
	curn->left = NULL;
	curn->right = NULL;
	curn->h = (stdv[k]*(t+1)-stdv[k]*t)*val;
	if(curn->h<0)
		curn->h = 0;

	curn->sum = (stdv[k]*(t+1)-stdv[k]*t)*val;
}

int maxv(int a, int b)
{
	return (a>b)?a:b;
}

void insert(treenode *curn, int a, int b, int val, int k, int t)
{
	int diff;

	// if the interval for this node is in the interval searched
	if(a<=stdv[k]*t+1 && stdv[k]*(t+1)<=b)
	{
		makeNewNode(curn, val, k, t);
		return;
	}

	// if this node is a leaf create its children
	if(curn->left==NULL)
	{
		diff = (curn->sum)/(stdv[k]*(t+1)-stdv[k]*t);

		curn->left = (treenode*)malloc(sizeof(treenode));
		makeNewNode(curn->left,diff,k-1,2*t);

		curn->right = (treenode*)malloc(sizeof(treenode));
		makeNewNode(curn->right,diff,k-1,2*t+1);
	}

	// if the interval for the left child has common points
	// with the interval searched
	if(a<=stdv[k-1]*(2*t+1))
	{	
		insert(curn->left,a,b,val,k-1,2*t);
	}

	// if the interval for the right child has common points
	// with the interval searched
	if(stdv[k-1]*(2*t+1)+1<=b)
	{
		insert(curn->right,a,b,val,k-1,2*t+1);
	}

	// update the values for this node
	curn->sum = curn->left->sum+curn->right->sum;
	curn->h = maxv(curn->left->h, curn->left->sum+curn->right->h);
}

int query(int h)
{
	int diff;
	int curh;
	treenode *curn;
	int k,t;
	int ans;

	curn = root;

	if(root->h <= h)
		return n;

	curh = 0;
	k = deg;
	t = 0;
	while(1)
	{
		// if this is a leaf stop here
		if(curn->left==NULL)
		{
			diff = (curn->sum)/(stdv[k]*(t+1)-stdv[k]*t);
			ans = (h-curh)/diff;
			ans += stdv[k]*t;


			return ans;
		}

		// if the car is going to stop in the interval
		// described by the left subnode
		if(curh+curn->left->h > h)
		{
			curn = curn->left;
			k--;
			t = 2*t;
		}
		else
		{
			curh += curn->left->sum;
			curn = curn->right;
			k--;
			t = 2*t+1;
		}
	}
}

void solve()
{
	char com;
	int h;
	int res;
	int fr,to,val;

	scanf("%d",&n);

	stdv[0] = 1;
	deg = 0;
	while(stdv[deg]<n)
	{	
		deg++;
		stdv[deg] = 2*stdv[deg-1];
	}

	// create the root of the tree
	root = (treenode*)malloc(sizeof(treenode));
	root->h = 0;
	root->sum = 0;
	root->left = NULL;
	root->right = NULL;

	while(1)
	{
		scanf(" %c ",&com);
		if(com=='E')
			break;

		if(com=='Q')
		{
			scanf("%d",&h);
			res = query(h);
			printf("%d\n",res);
		}

		if(com=='I')
		{
			scanf("%d %d %d",&fr,&to,&val);
			insert(root,fr,to,val,deg,0);
		}
	}
}

int main()
{
	solve();

	return 0;
}

Автор: Антон Димитров


обратно към брой 27