Permutation Transformer (UVa 11999 World Finals Warmup 2011 1)

UVa Online Judge Source

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3073

問題

1からnの数列がある。この数列の[a,b]の範囲をリバースして数列の一番後ろにくっつけるという操作をm回行う。最終的な数列を出力せよ。
1<=n,m<=100,000

解法

配列、クエリを平方根分割して気合で\sqrt{n}のブロックごとに分けた双方向リストを繋げ変えたりする。
具体的には最初と、\sqrt{m}回ごとに数列を\sqrt{n}のブロックごとに分けて初期状態の双方向リストを作る。クエリには[a,b]の範囲を切り出して、配列は遅延リバース、リストは即座にリバースしながら末尾に付け加える。こうすることによりO(\max(n,m)^{1.5})くらいで処理できる。

追記：平衡二分木を使ったらもっと楽だった。
Block Linked Listバージョン。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cassert>
#include <bitset>
using namespace std;
typedef long long ll;

#define REP(i, n) for (int i=0; i<(int)(n); ++i)
#define FOR(i, k, n) for (int i=(k); i<(int)(n); ++i)
#define FOREQ(i, k, n) for (int i=(k); i<=(int)(n); ++i)
#define FORIT(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(v) (int)((v).size())
#define MEMSET(v, h) memset((v), (h), sizeof((v)))

struct Block {
  int index;
  vector<int> vect;
  int rev;
  Block *prev;
  Block *next;
  Block() : rev(0), prev(NULL), next(NULL) {;}
  bool operator==(const Block &rhs) const {
    return index == rhs.index;
  }
  bool operator!=(const Block &rhs) const {
    return index != rhs.index;
  }
};

int n, sqn;
int m, sqm;
Block first;
Block last;
Block blocks[1000000];
int seq[1000000];
int idx;

inline void Init(int i) {
  blocks[i].index = i;
  blocks[i].vect.clear();
  blocks[i].rev = 0;
  blocks[i].prev = NULL;
  blocks[i].next = NULL;
}

void Reverse(Block &block) {
  if (block.rev) {
    reverse(block.vect.begin(), block.vect.end());
  }
  block.rev = 0;
}

void Erase(Block &block, int l, int r) {
  vector<int> vect;
  REP(i, block.vect.size()) {
    if (l <= i && i < r) { continue; }
    vect.push_back(block.vect[i]);
  }
  block.vect = vect;
}

void Connect(Block &prev, Block &next) {
  prev.next = &next;
  next.prev = &prev;
}

void ReCreate(bool init) {
  Block *block = &first;
  int index = 0;
  if (!init) {
    while (*block != last) {
      Reverse(*block);
      FORIT(it, block->vect) { seq[index++] = *it; }
      block = block->next;
    }
    assert(index == n);
  }
  REP(i, idx) { Init(i); }
  idx = 0;
  index = 0;
  while (index < n) {
    REP(i, sqn) {
      if (index >= n) { break; }
      blocks[idx].vect.push_back(seq[index++]);
    }
    if (index < n) {
      Connect(blocks[idx], blocks[idx + 1]);
    }
    idx++;
  }
  Connect(first, blocks[0]);
  Connect(blocks[idx - 1], last);
};

void Query(int a, int b) {
  int sum = 0;
  int soffset = -1;
  int eoffset = -1;
  Block *block = &first;
  Block *start = NULL;
  Block *end = NULL;
  while (*block != last) {
    int s = sum;
    sum += block->vect.size();
    if (sum > a && start == NULL) {
      soffset = a - s;
      start = block;
    }
    if (sum >= b && end == NULL) {
      eoffset = b - s;
      end = block;
    }
    block = block->next;
  }
  assert(start != NULL);
  assert(end != NULL);
  assert(0 <= soffset && soffset <= (int)start->vect.size());
  assert(0 < eoffset && eoffset <= (int)end->vect.size());

  Reverse(*start);
  Reverse(*end);

  if (start == end) {
    Block *mid = &blocks[idx++];
    FOR(i, soffset, eoffset) {
      mid->vect.push_back(start->vect[i]);
    }
    mid->rev = 1;
    Block *prelast = last.prev;
    Connect(*prelast, *mid);
    Connect(*mid, last);
    Erase(*start, soffset, eoffset);
  } else {
    Block *lmid = &blocks[idx++];
    Block *rmid = &blocks[idx++];
    FOR(i, soffset, start->vect.size()) {
      lmid->vect.push_back(start->vect[i]);
    }
    FOR(i, 0, eoffset) {
      rmid->vect.push_back(end->vect[i]);
    }
    if (*start->next == *end) {
      Connect(*lmid, *rmid);
    } else {
      Connect(*lmid, *start->next);
      Connect(*end->prev, *rmid);
    }

    block = lmid;
    while (true) {
      block->rev ^= 1;
      swap(block->prev, block->next);
      if (*block == *rmid) { break; }
      block = block->prev;
    }
    Block *prelast = last.prev;
    Connect(*prelast, *rmid);
    Connect(*lmid, last);

    Connect(*start, *end);
    Erase(*start, soffset, start->vect.size());
    Erase(*end, 0, eoffset);
  }
}

int main() {
  first.index = -1;
  last.index = -2;
  REP(i, 1000000) { Init(i); }
  while (scanf("%d %d", &n, &m) > 0) {
    REP(i, n) { seq[i] = i + 1; }
    sqn = sqrt(n) + 0.5;
    sqm = sqrt(m) + 0.5;
    ReCreate(true);
    REP(i, m) {
      if (i % sqm == sqm - 1) { ReCreate(false); }
      int a, b;
      scanf("%d %d", &a, &b);
      a--;
      Query(a, b);
    }
    ReCreate(false);
    REP(i, n) {
      printf("%d\n", seq[i]);
    }
  }
}

平衡二分木バージョン。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef int Node;
struct RBST {
  Node v;
  RBST *l;
  RBST *r;
  int size;
  RBST() : l(NULL), r(NULL), size(0) {;}
  RBST(Node v) : v(v), l(NULL), r(NULL), size(1) {;}
  RBST *Update() {
    size = 1 + (l ? l->size : 0) + (r ? r->size : 0);
    return this;
  }
};
RBST _pool[1000000];
RBST *pool = NULL;

int Count(RBST *t) { return t ? t->size : 0; }

RBST *Merge(RBST *l, RBST *r) {
  if (!l) { return r; }
  if (!r) { return l; }
  if (rand() % (Count(l) + Count(r)) < Count(l)) {
    l->r = Merge(l->r, r);
    return l->Update();
  } else {
    r->l = Merge(l, r->l);
    return r->Update();
  }
  assert(false);
  return NULL;
}

// [0, k), [k, n)
pair<RBST*, RBST*> Split(RBST *t, int k) {
  if (t == NULL) { return pair<RBST*, RBST*>(NULL, NULL); }
  if (k <= Count(t->l)) {
    pair<RBST*, RBST*> s = Split(t->l, k);
    t->l = s.second;
    return make_pair(s.first, t->Update());
  } else {
    pair<RBST*, RBST*> s = Split(t->r, k - Count(t->l) - 1);
    t->r = s.first;
    return make_pair(t->Update(), s.second);
  }
}

RBST *Insert(RBST *t, int k, Node v) {
  pair<RBST*, RBST*> s = Split(t, k);
  RBST *val = pool++;
  *val = RBST(v);
  return Merge(s.first, Merge(val, s.second));
}

RBST *Erase(RBST *t, int k) {
  pair<RBST*, RBST*> s1 = Split(t, k);
  pair<RBST*, RBST*> s2 = Split(s1.first, k - 1);
  return Merge(s2.first, s1.second);
}

RBST *At(RBST *t, int index) {
  assert(t != NULL);
  if (index < Count(t->l)) {
    return At(t->l, index);
  } else {
    index -= Count(t->l);
  }
  if (index == 0) { return t; }
  index--;
  return At(t->r, index);
}

int n, m;
int main() {
  while (scanf("%d %d", &n, &m) > 0) {
    RBST *tree = NULL;
    RBST *rev = NULL;
    pool = _pool;
    REP(i, n) {
      tree = Insert(tree, i, i + 1);
      rev = Insert(rev, i, n - i);
    }

    REP(i, m) {
      int a, b;
      scanf("%d %d", &a, &b);
      a--;
      pair<RBST*, RBST*> temp;
      temp = Split(tree, b);
      RBST* right = temp.second;
      temp = Split(temp.first, a);
      RBST* mid = temp.second;
      RBST* left = temp.first;

      temp = Split(rev, n - a);
      RBST* rright = temp.second;
      temp = Split(temp.first, n - b);
      RBST* rmid = temp.second;
      RBST* rleft = temp.first;

      tree = Merge(left, Merge(right, rmid));
      rev = Merge(mid, Merge(rleft, rright));
    }
    REP(i, n) {
      printf("%d\n", At(tree, i)->v);
    }
  }
}