#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

unsigned R() { return (rand() << 15) + rand(); }

typedef long long ll;

struct T
{
  static T *null;
  int x, y, size;
  T *l, *r;
  ll sum;

  T() { l = r = this, x = 0, size = 0, sum = 0; }
  T( int x, int y, T *l, T *r ) : x(x), y(y), l(l), r(r) { calc(); }
  void calc()
  {
    size = l->size + r->size + (this != null);
    sum = l->sum + r->sum + x;
  }

  void out( int dep = 0 )
  {
    //printf("out: this = %p, dep = %d (null = %p)\n", this, dep, null);
    if (this == null)
    {
      if (dep == 0)
        puts("<empty>");
      return;
    }
    l->out(dep + 1);
    printf("%*sx = %d, y = %d, size = %d, sum = %I64d\n", 2 * dep, "", x, y, size, sum);
    r->out(dep + 1);
  }
};

typedef T *Node;

Node T::null = new T();
Node z = T::null, root = z;

void Split( Node t, Node &l, Node &r, int x ) // <= x, > x
{
  if (t == z)
    l = r = z;
  else if (t->x <= x)
    Split(t->r, t->r, r, x), l = t;
  else
    Split(t->l, l, t->l, x), r = t;
  l->calc(), r->calc();
}

void Merge( Node &t, Node l, Node r ) // l <= r
{
  if (l == z)
    t = r;
  else if (r == z)
    t = l;
  else if (l->y < r->y)
    t = l, Merge(l->r, l->r, r);
  else
    t = r, Merge(r->l, l, r->l);
  t->calc();
}

void InsertSlow( Node &t, int x, int y )
{
  Node l, r;
  Split(t, l, r, x); // l <= x, r > x
  Merge(l, l, new T(x, y, z, z)); // l + (x)
  Merge(t, l, r); // (l + (x)) + r
}

inline void InsertFast( Node &t, int x, int y )
{
  if (t == z)
    t = new T(x, y, z, z);
  else if (t->y < y)
    InsertFast(x < t->x ? t->l : t->r, x, y);
  else
  {
    Node l, r;
    Split(t, l, r, x);
    t = new T(x, y, l, r);
  }
}

inline void DeleteFast( Node &t, int x )
{
  if (t == z)
    assert(0); // return;
  else if (t->x != x)
    DeleteFast(x < t->x ? t->l : t->r, x);
  else
    Merge(t, t->l, t->r);
}

// L <= x <= R
ll Sum( Node &t, int L, int R )
{
  Node l, r;
  Split(t, t, r, R);     // <= R
  Split(t, l, t, L - 1); // x < L  <=>  x <= L - 1
  ll res = t->sum;
  Merge(t, l, t);
  Merge(t, t, r);
  return res;
}

void TestTime()
{
  const int n = 1e5;
  int a[n];
  forn(i, n)
    InsertSlow(root, a[i] = R(), R());
  printf("time = %.2f\n", 1. * clock() / CLOCKS_PER_SEC);

  random_shuffle(a, a + n);
  forn(i, n)
    DeleteFast(root, a[i]);
  printf("time = %.2f\n", 1. * clock() / CLOCKS_PER_SEC);
}

int main()
{
  const int n = 10;
  forn(i, n)
    InsertFast(root, i, R());
  root->out();
  printf("sum = %I64d\n", Sum(root, 4, 6));
    
  //  root->out();
  return 0;
}