torus711 のアレ

主に競技プログラミングの問題について書きます

Segment Tree

TopCoder SRM 671, Division 1, Level 2 : BearDarts

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13951&rd=16551 問題概要 正整数からなる列 $w$ が与えられる.4 要素からなる $w$ の部分列をとって $\{ a, b, c, d \}$ としたとき,$ac = bd$ となっているものの総数を求めよ. $4 \l…

Good Bye 2014, D : New Year Santa Network

問題文 http://codeforces.com/contest/500/problem/D 問題概要 頂点からなる重み付きの木が与えられる.辺の情報は 3 つの配列 によって与えられ, 番の辺は 2 頂点 間を結び,その重みは である.また, を,2 頂点 間の単純道のコストとする. 今,以下の…

Codeforces #197, D : Xenia and Bit Operations

問題文 http://codeforces.com/contest/339/problem/D 概要 要素数が の数列 a が与えられる。 この数列に対し、次の手順により求まる値を v とする。 数列の項数が 2 以上の間、次の処理によって得られる数列を新しい a とする 奇数回目の処理のとき、偶数…

Codeforces #187, Division 2, B : Sereja and Array

問題文 http://codeforces.com/contest/315/problem/B 概要 n 項の数列 a が与えられる。 この数列に対する三種類のクエリが m 個来るので、これを処理せよ。 の要素を x にする の要素に y を加算する の要素を印字する

POJ 3368 : Frequent values

問題文 http://poj.org/problem?id=3368 概要 n 項からなる単調非減少な数列 a が与えられる。 以下のようなクエリを処理せよ。 区間 [ l, r ] の内で最も多く出現する数字の出現している個数を答えよ

POJ 3264 : Balanced Lineup

問題文 http://poj.org/problem?id=3264 概要 N 項からなる数列が与えられる。 続いて、以下のクエリが Q 個与えらえるので全て処理せよ。 区間 [ l, r ] の最大値と最小値の差を出力せよ