2017-08-18

August Long Challenge 2017: Walks on the binary tree

計算量: \(O(Q \log^2 N)\)
キーワード: persistent segment tree | zobrist hash | binary counter | binary search on segment tree | lcp

考察

これはそもそもbinary stringの問題である。
文字列数が2であればlen(s)+len(t)-lcp(s,t)で計算できる。複数文字列があるならソートして隣接要素間のLCPをすべて引けば良い。
sortはLCPがあればいいので、LCPの方法を考える。
ハッシュを用いてLCPを求めることにする。zobrist hash化したものをsegtreeに載せておけば、LCPは二分探索でいける。
二進カウンタと同じ考え方で、更新クエリで書き換わる桁数はO(1) amortizedである。文字列をsegtreeで持つことにしていたので、永続により空間O(Q log N)で保持できるということになる。
segtree上の[0,k)型クエリの二分探索は工夫することでO(log^2 n)からO(log N)に落とせる。fenwick tree上の二分探索(lower_bound)として有名？
先読みソート+linked listを用いて動的更新に対応させた。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <string>
 
using namespace std;
 
struct node {
  node *l = nullptr;
  node *r = nullptr;
  uint64_t sum = 0;
};
 
constexpr int N = 1 << 17;
 
uint64_t rnd[N];
 
uint64_t sum(node *x) {
  return x ? x->sum : 0ULL;
}
 
node *build(int l, int r) {
  node *ret = new node();
  if (r - l == 1) return ret;
  ret->l = build(l, l + r >> 1);
  ret->r = build(l + r >> 1, r);
  return ret;
}
 
int getval(int k, node *x, int l = 0, int r = N) {
  if (r - l == 1) {
    return x->sum != 0;
  }
  int m = l + r >> 1;
  if (k < m) {
    return getval(k, x->l, l, m);
  } else {
    return getval(k, x->r, m, r);
  }
}
 
node *setval(int k, int v, node *x, int l = 0, int r = N) {
  x = x ? new node(*x) : new node();
  if (r - l == 1) {
    x->sum = v ? rnd[l] : 0;
    return x;
  }
  int m = l + r >> 1;
  if (k < m) {
    x->l = setval(k, v, x->l, l, m);
  } else {
    x->r = setval(k, v, x->r, m, r);
  }
  x->sum = sum(x->l) ^ sum(x->r);
  return x;
}
 
int lcp(node *x, node *y, int k = N) {
  if (k == 1) return 0;
  if (sum(x->l) == sum(y->l)) {
    return lcp(x->r, y->r, k / 2) + k / 2;
  } else {
    return lcp(x->l, y->l, k / 2);
  }
}
 
bool compare(node *x, node *y) {
  int l = lcp(x, y);
  if (l == N - 1) return false;
  return getval(l, x) < getval(l, y);
}
 
void solve() {
  int n, q;
  cin >> n >> q;
 
  node *curr = build(0, N);
 
  vector<node *> strs(q);
 
  vector<bool> query(q);
  for (int i = 0; i < q; i++) {
    char type;
    scanf(" %c", &type);
    if (type == '!') {
      int k;
      scanf("%d", &k);
      k = n - 1 - k;
      for (; k >= 0; k--) {
        bool b = getval(k, curr);
        curr = setval(k, !b, curr);
        if (!b) break;
      }
    } else {
      query[i] = true;
    }
    strs[i] = curr;
  }
 
  vector<int> perm(q);
  for (int i = 0; i < q; i++) {
    perm[i] = i;
  }
 
  sort(perm.begin(), perm.end(), [&](int i, int j) {
    return compare(strs[i], strs[j]);
  });
 
  vector<int> inv(q);
  for (int i = 0; i < q; i++) {
    inv[perm[i]] = i;
  }
 
  long long ans = 1LL * q * n + 1;
  for (int ii = 0; ii + 1 < q; ii++) {
    int i = perm[ii];
    int j = perm[ii + 1];
    ans -= min(n, lcp(strs[i], strs[j]));
  }
 
  vector<int> left(q, -1);
  vector<int> right(q, -1);
 
  for (int i = 0; i + 1 < q; i++) {
    left[i + 1] = i;
    right[i] = i + 1;
  }
 
  auto del = [&](int i) {
    int y = inv[i];
    int x = left[y];
    int z = right[y];
    if (x != -1) ans += min(n, lcp(strs[perm[x]], strs[perm[y]]));
    if (z != -1) ans += min(n, lcp(strs[perm[y]], strs[perm[z]]));
    if (x != -1 && z != -1) ans -= min(n, lcp(strs[perm[x]], strs[perm[z]]));
    if (x != -1) right[x] = z;
    if (z != -1) left[z] = x;
    ans -= n;
  };
  for (int i = 0; i < q; i++) {
    if (query[i]) {
      del(i);
    }
  }
 
  vector<long long> anss;
  for (int i = q - 1; i >= 0; i--) {
    if (query[i]) {
      anss.push_back(ans);
    } else {
      del(i);
    }
  }
 
  for (int i = (int)anss.size() - 1; i >= 0; i--) {
    printf("%lld\n", anss[i]);
  }
}
 
uint64_t xorshift() {
  static uint64_t x = 1234567;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  return x;
}
 
int main() {
  for (int i = 0; i < N; i++) {
    rnd[i] = xorshift();
  }
 
  int T;
  cin >> T;
  while (T--) {
    solve();
  }
}

2017-08-18

August Long Challenge 2017: Hill Jumping

正答数を見る限りだと正攻法ではないんだろなとは思う。

計算量: \(O(100 Q \log N)\)
キーワード: link-cut tree | envelope

考察

各点におけるジャンプ先をsucc[i]とする。変更クエリにより書き換わるsuccの要素数はたかだか200である。
succ[i]で繋いでいくと木になる。この問題は木上のkth-ancestorを求める問題と見做せる。
link-cut treeによりlink, cut, kth-ancestorはいずれもO(log N) amortizedで処理できる。
kth-ancestorは二分探索木のkth-minと同様

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>
#include <cassert>
 
using namespace std;
 
constexpr int N = 1e5 + 10;
 
struct node {
  node *l = nullptr;
  node *r = nullptr;
  node *p = nullptr;
  int size = 1;
  int key;
};
 
bool is_root(node *x) {
  return !x->p || (x != x->p->l && x != x->p->r);
}
 
int size(node *x) {
  return x ? x->size : 0;
}
 
void fix(node *x) {
  x->size = 1 + size(x->l) + size(x->r);
}
 
void rot(node *x) {
  node *y = x->p;
  node *z = y->p;
  if (z) {
    if (y == z->l) z->l = x;
    if (y == z->r) z->r = x;
  }
  x->p = z;
  y->p = x;
  if (x == y->l) {
    y->l = x->r;
    x->r = y;
    if (y->l) y->l->p = y;
  } else {
    y->r = x->l;
    x->l = y;
    if (y->r) y->r->p = y;
  }
  fix(y);
}
 
void splay(node *x) {
  while (!is_root(x)) {
    node *y = x->p;
    if (!is_root(y)) {
      node *z = y->p;
      rot((x == y->l) == (y == z->l) ? y : x);
    }
    rot(x);
  }
  fix(x);
}
 
void expose(node *x) {
  node *tmp = x;
  node *r = nullptr;
  while (x) {
    splay(x);
    x->r = r;
    fix(x);
    r = x;
    x = x->p;
  }
  splay(tmp);
}
 
void link(node *c, node *p) {
  expose(c);
  expose(p);
  p->r = c;
  c->p = p;
  fix(p);
}
 
void cut(node *x) {
  expose(x);
  x->l->p = nullptr;
  x->l = nullptr;
  fix(x);
}
 
int kth_element(node *x, int k) {
  expose(x);
  while (true) {
    if (size(x->r) == k) {
      break;
    } else if (k < size(x->r)) {
      x = x->r;
    } else {
      if (!x->l) {
        break;
      }
      k -= 1 + size(x->r);
      x = x->l;
    }
  }
  splay(x);
  return x->key;
}
 
long long ft[N];
 
void add(int k, int v) {
  for (k++; k < N; k += k & -k) {
    ft[k] += v;
  }
}
 
long long getval(int k) {
  long long ret = 0;
  for (k++; k > 0; k &= k - 1) {
    ret += ft[k];
  }
  return ret;
}
 
int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    add(i, a);
    add(i + 1, -a);
  }
 
  vector<int> succ(n, -1);
  for (int i = 0; i < n; i++) {
    succ[i] = i;
  }
  vector<node *> nodes(n);
  for (int i = 0; i < n; i++) {
    nodes[i] = new node();
    nodes[i]->key = i;
  }
 
  auto update = [&](int l, int r) {
    l = max(0, l);
    deque<int> mono;
    for (int i = min(n - 1, r + 100); i >= r + 1; i--) {
      while (!mono.empty() && getval(i) >= getval(mono.front())) {
        mono.pop_front();
      }
      mono.push_front(i);
    }
    for (int i = r; i >= l; i--) {
      while (!mono.empty() && mono.back() > i + 100) {
        mono.pop_back();
      }
      while (!mono.empty() && getval(i) >= getval(mono.front())) {
        mono.pop_front();
      }
      mono.push_front(i);
      if (mono.size() == 1) {
        if (succ[i] != i) {
          cut(nodes[i]);
        }
        succ[i] = i;
      } else {
        if (succ[i] != i) {
          cut(nodes[i]);
        }
        succ[i] = mono[1];
        link(nodes[i], nodes[mono[1]]);
      }
    }
  };
  update(0, n - 1);
 
  while (q--) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int u, cnt;
      scanf("%d %d", &u, &cnt);
      u--;
      printf("%d\n", kth_element(nodes[u], cnt) + 1);
    } else {
      int l, r, x;
      scanf("%d %d %d", &l, &r, &x);
      l--;
      r--;
      add(l, x);
      add(r + 1, -x);
      update(r - 99, r);
      update(l - 100, l - 1);
    }
  }
}

2017-08-13

Codeforces Round #428 (Div. 2): D. Winter is here

http://codeforces.com/problemset/problem/839/D

dp[i]:=gcdがiになるような部分列の総数とすると以下の関係式が成り立つ。

\begin{equation}
dp[i]=\text{gcdがiの倍数の部分列の総数}-dp[2i]-dp[3i]-dp[4i]-\cdots
\end{equation}

gcdがiの倍数になる部分列の総数を得るために、\( \sum_{k=1}^{n} k\binom{n}{k} \) を計算する必要が出てくるが、\((1+x)^n\) を微分すれば分かる。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

constexpr int MOD = 1e9 + 7;

struct modint {
  int n;
  modint(int n = 0) : n(n) {}
};

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= MOD ? a.n - MOD : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + MOD : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % MOD); }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }

template<typename T>
modint modpow(modint a, T b) {
  modint ret = 1;
  for (; b > 0; b >>= 1, a *= a) if (b & 1) ret *= a;
  return ret;
}

int main() {
  constexpr int N = 1.01e6;
  int n;
  cin >> n;
  vector<modint> dp(N);
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    dp[a] += 1;
  }
  for (int i = 1; i < N; i++) {
    for (int j = i * 2; j < N; j += i) dp[i] += dp[j];
    dp[i] *= modpow(2, dp[i].n - 1);
  }
  modint ans = 0;
  for (int i = N - 1; i >= 2; i--) {
    for (int j = i * 2; j < N; j += i) dp[i] -= dp[j];
    ans += i * dp[i];
  }
  cout << ans.n << endl;
}

2017-08-04

Educational Codeforces Round 26: G. Functions On The Segments

http://codeforces.com/contest/837/problem/G

解法

二次元の総和クエリに落とし込む。高次元クエリを扱うテクニックとして永続的データ構造を用いるという方法がある。永続 segtree により解くことができるが、wavelet matrix を用いて解くこともできる。

計算量は、構築O(n log x) 質問O(log x) である。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// wavelet-matrix
constexpr int N=75000*2;
constexpr int H=18;

struct foo {
  int key;
  long long a, b;
};

foo dat[N], mat[H][N+1];

void build(int l, int r, int d) {
  if(d==H || r-l==0) return;
  for (int i=l; i<r; i++) {
    mat[d][i+1].key=mat[d][i].key+(dat[i].key>>H-1-d&1);
  }
  int m=stable_partition(dat+l, dat+r, [&](foo x) { return ~x.key>>(H-1-d)&1; })-dat;
  for (int i=l; i<r; i++) {
    mat[d][i+1].a=mat[d][i].a+dat[i].a;
    mat[d][i+1].b=mat[d][i].b+dat[i].b;
  }
  build(l, m, d+1);
  build(m, r, d+1);
}

int count1(int d, int l, int r) { 
  return mat[d][r].key-mat[d][l].key;
}

int count0(int d, int l, int r) {
  return (r-l)-count1(d, l, r);
}

long long sum(int l, int r, long long x, int k) {
  int ll=0, rr=N;
  long long ret=0;
  for (int i=0; i<H; i++) {
    int mm=count0(i, ll, rr)+ll;
    int l0=count0(i, ll, l)+ll;
    int r0=count0(i, ll, r)+ll;
    if (~k>>H-1-i&1){
      l=l0;
      r=r0;
      rr=mm;
    } else {
      ret+=mat[i][r0].a*x+mat[i][r0].b;
      ret-=mat[i][l0].a*x+mat[i][l0].b;
      l=count1(i, ll, l)+mm;
      r=count1(i, ll, r)+mm;
      ll=mm;
    }
  }
  return ret;
}

int main() {
  int n;
  cin>>n;

  vector<long long> base(n+1);
  for (int i=0; i<n; i++) {
    int x1, x2, y1, A, B, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &A, &B, &y2);
    base[i+1]=base[i]+y1;
    dat[i*2+0]={x1, A, -y1+B};
    dat[i*2+1]={x2, -A, -B+y2};
  }
  build(0, N, 0);

  long long last=0;
  int q;
  cin>>q;
  while (q--) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    l--;
    int xi=(x+last)%int(1e9);
    int t=min(xi, 200005);
    last=sum(l*2, r*2, xi, t)+base[r]-base[l];
    printf("%lld\n", last);
  }
}

2017-08-04

Educational Codeforces Round 26: E. Vasya's Function

http://codeforces.com/contest/837/problem/E

解法

b-gcd(a,b) は gcd(a,b) の倍数である。つまり次の操作でも gcd は gcd(a,b) の倍数になるはずである。何だかんだでf(a,b)=f(a/g,b/g)が成り立つ。よってf(a,b)の計算は

a,bをgcd(a,b)で割る
gcd(a,b)≠1 になるまでbを引き続ける

の繰り返しでできる。前者が起きる回数は O(log a) であるから、もし後者を高速にシミュレーションできれば解くことができる。

後者はあらかじめ a の素因数リストを計算しておけば分かる。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long gcd(long long a, long long b) { 
  while (b!=0) {
    long long tmp=a;
    a=b;
    b=tmp%b;
  }
  return a;
}

vector<long long> primes(long long n) {
  vector<long long> ret;
  for (long long i=2; i*i<=n; i++) {
    if (n%i==0){ 
      ret.push_back(i);
      while (n%i==0) n/=i;
    }
  }
  if (n!=1) ret.push_back(n);
  return ret;
}

int main() {
  long long a, b;
  cin>>a>>b;  

  auto ps=primes(a);
  long long ans=0;
  while (b!=0) {
    long long g=gcd(a, b);
    a/=g;
    b/=g;
    long long next=0;
    for (long long p:ps) if (a%p==0) {
      next=max(next, (b-1)/p*p);
    }
    ans+=b-next;
    b=next;
  }
  cout<<ans<<endl;
}