天下一プログラマーコンテスト2016 予選B : D - 天下一数列にクエリを投げます

シンプルながらその発想はなかった。
http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_d

問題

N要素の数列a[i]がある。
これに対し以下の加算クエリjをA個順に行う。

• a[L[j]...R[j]]にそれぞれX[j]を加算する。

さらに以下の調査クエリkをB個に答えよ。

• a[X[k]]について、S[k]番目の加算クエリの実行前から、T[k]番目の加算クエリ実行後までの間における最小値

解法

2次元のテーブルC(i,j)を考えよう。
C(i,j) := a[i]にj番目までの加算クエリを適用した状態の数値、とする。
以下iを横軸、jを縦軸に対応付けて考える。
すると、加算クエリ(L[i]-1,i)-(R[i],B)の矩形区間に対する加算に対応し、調査クエリは(X[k],S[k]-1)-(X[k],T[k])の矩形区間に対する最小値の算出に対応する。
ここで全体を90度回転してみる。
すると加算クエリは相変わらず矩形区間に対する加算であるが、調査クエリは縦軸(回転前で言う時間軸)のある1点において、横軸(S[k]-1)...(T[k])の最小値を求めるクエリと見なすことができる。

こうなってしまえば、後は縦方向に平面走査しながら範囲加減算・範囲最小値を行えるSegTreeを用いてクエリを処理できる。

template<class V,int NV> class RMQ {
public:
	vector<V> val, mi;
	RMQ(){ val.resize(NV*2,0); mi.resize(NV*2,0); };
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return 1LL<<60;
		if(x<=l && r<=y) return mi[k];
		return min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)) + val[k];
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			mi[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			mi[k]=min(mi[k*2],mi[k*2+1]) + val[k];
		}
	}
};

int N,A,B;
int a[101010];
int L[101010],R[101010],X[101010];
int S[101010],T[101010],K[101010];
ll ret[101010];

vector<int> ev_add[101010];
vector<int> ev_del[101010];
vector<int> ev_query[101010];

RMQ<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>a[i+1];
	cin>>A;
	FOR(i,A) {
		cin>>L[i]>>R[i]>>X[i];
		ev_add[L[i]].push_back(i);
		ev_del[R[i]].push_back(i);
	}
	cin>>B;
	FOR(i,B) {
		cin>>S[i]>>T[i]>>K[i];
		ev_query[K[i]].push_back(i);
	}
	
	for(i=1;i<=100000;i++) {
		FORR(r,ev_add[i]) {
			st.update(r+1,A+1,X[r]);
		}
		FORR(r,ev_query[i]) {
			ret[r]=a[K[r]] + st.getval(S[r]-1,T[r]+1);
		}
		FORR(r,ev_del[i]) st.update(r+1,A+1,-X[r]);
	}
	FOR(i,B) cout<<ret[i]<<endl;
	
}

まとめ

90度回転は思いつかなかった。
参加してたら平方分割してただろうけど、時間間に合ったかな…。