Educational Codeforces Round 10. D. Nested Segments: c++, perl and common lisp implementation, Segment Tree

July 1, 2016
Codeforces

Problem Link

Fenwick Tree，它的本质就是把一个序列的和划分成一个个子序列的和。比如一个序列的长 度是10，那么10的二进制是1010，也就是2^1 + 2^3，所以结果就是树里面2和8两个节点的 和。在树里面，节点（n）表示数列里从1到n的元素的和，那么：

  • (1) = (1)
  • (2) = (2)
  • (3) = (1) + (2)
  • (4) = (4)
  • (5) = (1) + (4)
  • (6) = (2) + (4)
  1. 按照右端点排序，然后把它离散化；
  2. 按照左端点倒序排列，从大到小循环，计算右端点在Fenwick Tree里面的presum（也就 是之前插入的比当前右端点小的数量），这个presum就是当前的segment包含的segment 的个数；
  3. 把当前右端点插入Fewnwick Tree；

题目要求计算每个端点包含的segment的数量，因为后面要用到排序和离散化，所以可以在 结构体或者类中增加一个域表示它原来在数组中的初始位置。每计算一个presum就可以根据 这个域放到结果数组里面的对应位置。

C++

#include <bits/stdc++.h>

using namespace std;

struct segment {
  int x, y, position;
};

const int N = 2e5 + 1;
int n, fenwick[N];
long long ans[N];

segment S[N];

int cmpx_r(segment a, segment b) { return a.x > b.x; }

int cmpy(segment a, segment b) { return a.y < b.y; }

int lowbit(int x) { return x & -x; }

long long presum(int index) {
  long long ans = 0;

  while (index > 0) {
    ans += fenwick[index];
    index -= lowbit(index);
  }

  return ans;
}

void updateFenwick(int index, int n) {
  while (index <= n) {
    fenwick[index]++;
    index += lowbit(index);
  }
}

int main(void) {

#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
#endif

  while (~scanf("%d", &n)) {
    int i;

    memset(fenwick, 0, sizeof(fenwick));

    for (i = 1; i <= n; ++i) {
      scanf("%d%d", &S[i].x, &S[i].y);
      S[i].position = i;
    }

    // compress y
    sort(S + 1, S + n + 1, cmpy);

    for (i = 1; i <= n; ++i) {
      S[i].y = i;
    }

    // sort by x reversely
    sort(S + 1, S + n + 1, cmpx_r);

    for (i = 1; i <= n; ++i) {
      ans[S[i].position] = presum(S[i].y);
      updateFenwick(S[i].y, n);
    }

    for (i = 1; i <= n; ++i) {
      cout << ans[i] << endl;
    }
  }

  return 0;
}

Perl

因为IO的问题，这道题用Perl会在第15或者16个test case里面会超时，我看上面用python 的也都超时了……

use strict;
use 5.014;
use utf8;

my $n;
chomp($n = <>);
my @s;

for(0..$n-1) {
    my $segment;
    chomp($segment = <>);
    my ($l, $r) = split(' ', $segment);
    push @s, {
        left => $l,
        right => $r,
        position => $_,
    };
}

# compress right
@s = sort { $a->{right} <=> $b->{right} } @s;

for(0..$#s) {
    $s[$_]->{right} = $_ + 1;
}

# sort by left
@s = sort { $b->{left} <=> $a->{left} } @s;

my @ans;
my @fenwick = ();

for(@s) {
    $ans[$_->{position}] = presum($_->{right});
    updateFenwick($_->{right});
}

for(@ans) { say $_ }

sub presum {
    my $index = shift;
    my $ans = 0;
    while ($index > 0) {
        $ans += $fenwick[$index];
        $index -= lowbit($index);
    }
    $ans;
}

sub updateFenwick {
    my $index = shift;
    while ($index <= $n) {
        $fenwick[$index]++;
        $index += lowbit($index);
    }
}

sub lowbit { $_[0] & -$_[0] }

Common Lisp

;; Finished at 2016/07/07 7:51:23 AM

(defvar *n*)
(defparameter *maxn* 20)

(defclass node ()
  ((left :accessor left
         :initarg :left)
   (right :accessor right
          :initarg :right)
   (ori-position :accessor ori-position
                 :initarg :ori-position)))

(defparameter *s* (make-array *maxn*
                              :element-type 'node
                              :fill-pointer 0
                              :adjustable t))
(defparameter *fenwick* (make-array *maxn*
                                    :element-type 'integer
                                    :fill-pointer 0
                                    :adjustable t))
(defparameter *ans* (make-array *maxn*
                                    :element-type 'integer
                                    :fill-pointer 0
                                    :adjustable t))

(defun print-array ()
  (loop for i from 0 to (1- *n*) do
           (format t "i = ~d, ~d ~d~%"
                   i
                   (left (aref *s* i))
                   (right (aref *s* i)))))

(defun lowbit (x)
  (boole boole-and x (- x)))

(defun presum (index)
  (let ((ans 0))
    (do ((i index
            (- i (lowbit i))))
        ((<= i 0) ans)
      (incf ans (elt *fenwick* (1- i))))))

(defun update-fenwick (index)
  (do ((i index (+ i (lowbit i))))
      ((> i *n*))
    (incf (elt *fenwick* (1- i)))))

(with-open-file
    (*standard-input*
     "in.txt"
     :if-does-not-exist nil)
  (setq *n* (read))
  (loop for i from 0 to (1- *n*) do
    (vector-push-extend
     (make-instance 'node
                    :left (read)
                    :right (read)
                    :ori-position i)
     *s*)
    (vector-push-extend 0 *fenwick*)
    (vector-push-extend 0 *ans*)))

(sort *s* #'< :key #'right)

;; compress right
(loop for i from 0 to (1- *n*) do
  (setf (right (elt *s* i))
        (1+ i)))

;; sort by left reverse
(sort *s* #'> :key #'left)
(loop for i from 0 to (1- *n*) do
  (setf (elt *ans* (ori-position (elt *s* i)))
        (presum (right (elt *s* i))))
  (update-fenwick (right (elt *s* i))))

(defun print-ans ()
  (loop for i from 0 to (1- *n*) do
    (format t "~d~%" (elt *ans* i))))

(print-ans)
comments powered by Disqus