pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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);
  }
}