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