NZEC на INVCNT с Гайлом на Spoj

Фильтрация по очень длинному списку может привести к максимальной ошибке отказа (в спецификациях указано до десяти миллионов). Вместо использования '(length (filter...') используйте fold

(define (inversion L)
 (let loop ((accumulator 0) (L L))
   (if (null? L)
       accumulator
       (loop 
         (+ accumulator
            (fold
              (lambda (init next)
                (if (> (car l) next)
                    (+ init 1)
                    init))
              0
              (cdr L)))
         (cdr L)))))

Во-вторых, это было бы легче читать, вытащив эту складку в свою собственную функцию.

(define (inversions-from-car L)
  (fold
     (lambda (init next)
        (if (> (car l) next)
            (+ init 1)
            init))
      0
      (cdr L)))

(define (inversion L)
 (let loop ((accumulator 0) (L L))
   (if (null? L)
       accumulator
       (loop 
         (+ accumulator
             (inversions-from-car L)     
         (cdr L)))))

Это выглядит как хорошая задача для игры со структурами данных, потому что, как написано, это сложность n ^ 2.

Я думаю, вы можете уменьшить это до n (log n)

Скажем, создайте отсортированное дерево в списке значений в паре с количеством узлов слева. для этого набора

'(2 3 8 6 1) -> '(1 2 3 6 8) -> 
(*tree (*entry 3 2 2)
       (*tree (*entry 2 1 1)
              (*tree (*entry 1 0 1)
                     ()
                     ())
              ())
        (*tree (*entry 8 1 1)
               (*tree (*entry 6 0 1)
                      ()
                      ())
               ()))      

*дерево и *запись - это просто теги типа *дерево должно иметь запись, левую и правую *запись должна иметь значение, #left и число)

Начните с поиска ПЕРВОГО в исходном списке с нулевым аккумулятором.

'(2 3 8 6 1)

Если значение ввода соответствует FIRST, добавьте #left к аккумулятору

Если значение entry больше ПЕРВОЙ рекурсии по левой ветке дерева с аккумулятором

Если значение записи меньше, чем FIRST , рекурсивно по правой ветке с добавлением #left к аккумулятору.

Если это нулевое дерево, выдайте ошибку

Затем нужно обновить дерево.

Если значение записи равно FIRST, измените запись, чтобы уменьшить число на единицу.

Если значение записи больше, чем FIRST, измените запись, чтобы уменьшить #left на единицу и выполнить рекурсию по левой ветке.

Если значение записи меньше, чем first , рекурсия по правой ветке

Если это нулевое дерево, выдайте ошибку

Вы можете объединить эти правила в один обход

Дополнительно добавьте правило, что если #left равно 0, а число равно нулю, то, если правая ветвь равна нулю, мутируйте это дерево в пустое дерево, иначе - в правую ветвь.

Вот грубый (непроверенный вариант идеи)

(define (rev-sorted-list->count-list L) ;;sort should be resverse of
                                        ;; final desired order
 (let loop ((value (car L)) (count 1) (L (cdr L)) (acc '()))
   (cond ((null? L) '())
         ((= value (car l))
          (loop value (+ 1 count) (cdr L) acc))
         (else 
          (loop (car l) 1 (cdr L) (cons (cons value count) acc))))))

(define (make-tree count c-L)
 (let* ((middle (ceiling (+ 1 count) 2))
        (left-count (- middle 1))
        (right-count (-count middle))
        (left (if (= 0 left-count)
                  null-tree 
                  (make-tree left-count c-L)))
        (entry+right
          (let loop ((index 1) (L c-L))
            (if (= index middle) 
                L
                (loop (+ 1 index) (cdr L)))))
        (entry 
         (make-entry 
           (caar entry+right)
           left-count
           (cdar entry+right))))
    (build-tree 
       entry
       left
       (if (= 0 right-count)
           null-tree
           (make-tree right-count (cdr entry+right))))))     

;;form left branches from starting points
;;;form right from stopping points
;;never mutating c-L or copies

;;if count = 0 then null tree

(define (build-tree entry left right)
  (list '*tree entry left right) 

(define (entry tree)
 (cadr tree)
(define (left-branch tree)
 (caddr tree))
(define (right-branch tree)
 (cadddr tree))

(define null-tree (list '*tree '()))
(define (null-tree? tree)
 (null? (entry tree)))

(define (make-entry value Nleft count)
 (let ((vec (make-vector 3)))
  (begin (vector-set! vec 0 value)
         (vector-set! vec 1 Nleft)
         (vector-set! vec 2 count)
         vec)))

;;might meessage passing function here

(define (entry-value entry)
 (vector-ref entry 0))

(define (entry-Nleft entry)
 (vector-ref entry 1))

(define (entry-Nleft-set! entry int)
 (vector-set! entry 1 int))

(define (entry-count entry)
 (vector-ref entry 2))

(define (entry-count-set! entry int)
 (vector-set! entry 2 int))

(define (inversions! Test-List Search-Tree)
 (let loop ((acc 0) (L Test-list) (T Search-tree))
   (cond ((null? L) acc)
         ((null-tree? T) (error "null tree " 
                                 "in inner loop of inversion!"))
         ((= (car L) (entry-value (entry T)))
          (entry-count-set! (entry T)
                            (- (entry-count (entry T)) 1))
          (if (and (= 0 (entry-count (entry T)))
                   (= 0 (entry-Nleft (entry T))))
               (set-cdr! T (right-branch T))
               'skip)
          (loop (+ acc (entry-Nleft (entry T)))
                (cdr L)
                Search-tree))
         ((< (car L) (entry-value (entry T)))
          (entry-Nleft-set! (entry T)
                            (- (entry-Nleft (entry T)) 1))
          (loop acc L (left-branch T)))
         ((> (car L) (entry-value (entry T)))
          (loop (+ acc (entry-Nleft (entry T)))
                L
                (right-branch T))))))