Mrrl

В этой задаче нельзя обойтись "текущей подпоследовательностью". Надо держать самые длинные подпоследовательности, заканчивающиеся на разные элементы (чем больше элемент, тем длиннее должна быть подпоследовательность, заканчивающаяся на него), и когда приходит новый элемент, то присоединить его к самой длинной из последовательностей, к какой возможно (причём старую последовательность сразу выбрасывать нельзя - она ещё может пригодиться), а потом выбросить неоптимальные (последовательность такой же длины, что и другая, но заканчивающаяся на больший элемент).
Например, для последовательности [1,2,7,8,9,5,6,3] вам придётся помнить
[1,2,7,8,9]
[1,2,5,6]
[1,2,3]
[1,2]
[1]
Любая из этих последовательностей может быть началом правильного ответа.
Так что начало решения у вас правильное. Но в векторе d должны храниться не числа, а их индексы (и поиск должен быть более сложным), а массив prev надо модифицировать так: prev[i]=d[j-1].
Для примера [1,2,7,8,9,5,6,3] получаем
d={-1,0,1,7,6,4,-1,-1,-1,...}, prev={-1,0,1,2,3,1,5,1}
(значение -1 используется для обозначения ситуации "нет такого индекса").

Не bouble, а double.
В описании массива пишете
double *arr2;
а в инициализации -
arr2=new double[n];
Если поменять тип только в одном месте, будет ошибка.

Если номер позиции pos, число разрядов len, а число, которое надо изменить - x, то ответом будет
x | (((1 << len) - 1) << pos)

Если сравнивать код с алгоритмом, то пропущено условие d[j-1] < a[i] (видимо, в коде оно должно выглядеть, как ub==v.begin() || ub[-1] < a[i] ). Похоже, что без него алгоритм будет искать не возрастающую, а неубывающую последовательность (но я в этом не уверен).

Если позиция сразу проигрышная, то программа не помечает ход как правильный. Больше ошибок пока не видно.

Если N небольшое (скажем, не больше 100000), то можно так:

char *A=new char[N+1];
  for(int n=1;n<=N;n++){
    int a=0;
    for(int b=0;b<n;b++) a=(10*a+1)%n;
    A[n]=!a;
  }

При больших N нужно пользоваться аналогом быстрого возведения в степень.
Получается, что кроме 3 и 37, в числах оказываются такие простые делители, как 163, 757, 1999, 9397... Не понимаю, откуда они берутся.
UPD.
757 - делитель 10^27-1
163 и 9397 - делители 10^81-1
1999 - делитель 10^999-1

calloc должен заполнять нулями, это да. Но realloc не обязан заполнять нулями вновь захваченные элементы массива, это надо делать вручную.

Как-то так:

int S0[37],S1[37],S2[37],S3[37],S4[37];

void Expand(int *a,int *b,int n){
	int s0=0;
	for(int i=0;i<n+10;i++){
		if(i<n) s0+=a[i];
		if(i>=10) s0-=a[i-10];
		b[i]=s0;
	}
}

int Conv(int *S,int balance,int m){
	int res=0;
	while(--m>=0) res+=S[m]*S4[balance+m];
	return res;
}

// number of tickets in 0..u-1
int NHappy(int u){
	int res=0;
	int balance=0;
	int digit;

	digit=u/10000000; u%=10000000;
	for(int i=0;i<digit;i++) res+=Conv(S3,balance++,28);
	digit=u/1000000; u%=1000000;
	for(int i=0;i<digit;i++) res+=Conv(S2,balance++,19);
	digit=u/100000; u%=100000;
	for(int i=0;i<digit;i++) res+=Conv(S1,balance++,10);
	digit=u/10000; u%=10000;
	for(int i=0;i<digit;i++) res+=S4[balance++];
	digit=u/1000; u%=1000;
	for(int i=0;i<digit && balance>=0;i++) res+=S3[balance--];
	digit=u/100; u%=100;
	for(int i=0;i<digit && balance>=0;i++) res+=S2[balance--];
	digit=u/10; u%=10;
	for(int i=0;i<digit && balance>=0;i++) res+=S1[balance--];
	if(balance>=0 && balance<u) res++;
	return res;
}

void __cdecl main(){
	S0[0]=1;
	Expand(S0,S1,10);
	Expand(S1,S2,19);
	Expand(S2,S3,28);
	Expand(S3,S4,37);

	int m,n;
	for(;;){
		printf("m,n: ");
		scanf("%d%d",&m,&n);
		printf("Result: %d\n",NHappy(99999999)+1-NHappy(m)-NHappy(99999999-n));
	}
}

Проверок входных данных не делается. На простых тестах результаты были правильными. Работает, по моим оценкам, быстрее, чем за 2000 операций. Если нужно проверять много диапазонов, то можно предварительно вычислить частичные суммы Conv() в циклах, и тогда любой диапазон сосчитается за два десятка операций (и при этом не будет требовать гигабайта памяти).

UPD: Вот оптимизированный вариант:

int S[8][38];

void InitS(){
	for(int i=1;i<38;i++) S[0][i]=1;
	for(int a=1;a<9;a++){
		int s0=0;
		for(int i=1;i<=37;i++){
			s0+=S[a-1][i];
			if(i>10) s0-=S[a-1][i-10];
			S[a][i]=s0;
		}
	}
}

// number of tickets in 0..u-1
int NHappy(int u){
	int res=0;
	int balance=36;
	for(int a=7,b=10000000;a>=0;a--,b/=10){
		int digit=u/b;
		u%=b;
		int b1;
		if(a>3){
			balance-=9;
			res+=S[a][b1=balance+digit]-S[a][balance];
		} else{
			b1=balance-digit; if(b1<0) b1=-1;
			res+=S[a][balance+1]-S[a][b1+1];
		}
		balance=b1;
	}
	return res;
}

void __cdecl main(){
	InitS();
	int m,n;
	for(;;){
		printf("m,n: ");
		scanf("%d%d",&m,&n);
		printf("Result: %d\n",NHappy(99999999)+1-NHappy(m)-NHappy(99999999-n));
	}
}

Не спрашивайте, почему :)

Лишние пробелы - это те, которых больше одного подряд?

List *delSpaces(List *p) {
    for(List **a=&p;*a;){
        if((*a)->c==' ' && (*a)->next && (*a)->next->c==' ') *a=(*a)->next;
        else a=&((*a)->next);
    }
    return p;
}

Не проверялось.

Решить задачу легко - заводите массив A[N,N], в каждой клетке [K,M] которого будет записано число лесенок из K кубиков, нижний слой которых состоит из M кубиков. Число будет ненулевым, когда M <= K <= M*(M+1)/2.
Массив заполняется начиная со строчки K=1 по формуле A[K,M]=sum(A[K-M,r],r=1..M-1). Сумма элементов в строчке K=N будет искомым числом.

В решении, ссылку на которое вы дали, последовательно вычисляется число лестниц из j кубиков, нижний ряд которых не длиннее, чем i кубиков. Чтобы найти это число, надо к уже найденным лестницам, нижний ряд которых не длиннее, чем i-1 кубик (их мы оставляем без изменения), прибавить лестницы из j-i кубиков с нижним рядом не длиннее, чем i-1 кубик (к ним мы добавим ряд из i кубиков). Что и делается во внутреннем цикле.