Codeforces ECR #026 : G. Functions On The Segments

リソース制限に手間取った。
http://codeforces.com/contest/837/problem/G

問題

n個の関数f_i(x)がある。これらはパラメータx1,x2,y1,y2,a,bを用いて以下のように定義される。

• 
• 
• 

これらの各パラメータが与えられたとき、以下のクエリQ個に答えよ。
なお、この問題ではクエリの先読みができない。

• 整数L,R,xが与えられるので

解法

定番テクを組み合わせて解く。
定義域に関するx_1、x_2に関し座標圧縮しよう。

まずfの定義におけるy_1およびy_2の扱いだが、(a=0,b=y_1)および(a=0,b=y_2)と考えると、この関数は常にax+bの形で表現できる。
よって座標圧縮後の各xに対し各関数のa,bの総和を求めておけば、圧縮後の座標に含まれないxに対する値も容易に求められる。

クエリでは計算対象の関数群[L,R]が定められているので、a,bの総和を求める範囲を平方分割で事前にO(√N)個の変数に分けておけばよい。
そうすると前処理O(N√N)、クエリO(Q√N)程度で処理できる。

int N;
int X1[101010],X2[101010],Y1[101010],A[101010],B[101010],Y2[101010];
int Q;
int L,R,X;
vector<int> MP;
const int DI=500;
ll BB[203030][75000/DI+5];
int AA[203030][75000/DI+5];

ll val(int i,int x) {
	if(x<=X1[i]) return Y1[i];
	if(x>X2[i]) return Y2[i];
	return (ll)A[i]*x+B[i];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	MP.push_back(0);
	FOR(i,N) {
		scanf("%d%d%d%d%d%d",&X1[i],&X2[i],&Y1[i],&A[i],&B[i],&Y2[i]);
		MP.push_back(X1[i]+1);
		MP.push_back(X2[i]+1);
	}
	MP.push_back(1000000001);
	sort(ALL(MP));
	MP.erase(unique(ALL(MP)),MP.end());
	FOR(i,N) {
		y=i/DI;
		BB[0][y]+=Y1[i];
		x=lower_bound(ALL(MP),X1[i]+1)-MP.begin();
		BB[x][y]+=B[i]-Y1[i];
		AA[x][y]+=A[i];
		x=lower_bound(ALL(MP),X2[i]+1)-MP.begin();
		BB[x][y]+=Y2[i]-B[i];
		AA[x][y]-=A[i];
	}
	FOR(i,N/DI+1) for(x=1;x<MP.size();x++) AA[x][i]+=AA[x-1][i],BB[x][i]+=BB[x-1][i];
	
	scanf("%d",&Q);
	ll last=0;
	while(Q--) {
		scanf("%d%d%d",&L,&R,&X);
		L--,R--;
		X=(X+last)%1000000000;
		
		last=0;
		while(R%DI!=DI-1 && L<=R) last+=val(R,X),R--;
		while(L%DI!=0 && L<=R) last+=val(L,X),L++;
		x=lower_bound(ALL(MP),X+1)-MP.begin()-1;
		while(R>L) last+=(ll)AA[x][R/DI]*X+BB[x][R/DI],R-=DI;
		_P("%" PRId64 "\n",last);
		
	}
}

まとめ

SegTree解答もあるみたいね。