torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Segment Tree

AtCoder Beginner Contest 341, E : Alternating String

問題文 https://atcoder.jp/contests/abc341/tasks/abc341_e 問題概要 $0$ と $1$ からなる $n$ 要素の列 $S = S_1, S_2, \dots S_n$ ($S_i \in { 0, 1 }$) が与えられる.クエリが $q$ 個与えられるので,順に処理せよ.クエリは以下の 2 種類からなる: $(…

AtCoder Beginner Contest 340, E : Mancala 2

問題文 https://atcoder.jp/contests/abc340/tasks/abc340_e 問題概要 $0$ から $n - 1$ で番号付けられた $n$ 個の箱があり,最初,箱 $i$ には $A_i$ 個のボールが入っている. $i = 1, 2, \dots, m $ に対し順に以下の手続きを実行する. 変数 $c$ を用意…

AtCoder Beginner Contest 339, E : Smooth Subsequence

問題文 https://atcoder.jp/contests/abc339/tasks/abc339_e 問題概要 $n$ 項の数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる. $A$ の(連続するとは限らない)部分列であって,隣接する 2 項の差の絶対値が $d$ 以下なものの長さの最大値…

AtCoder Beginner Contest 185, F : Range Xor Query

問題文 https://atcoder.jp/contests/abc185/tasks/abc185_f 問題概要 長さ $N$ の正整数の列 $A$ について,以下の 2 種類のクエリが $Q$ 個飛んでくる.順に処理せよ. クエリ 1 : $A_{ X_i }$ を $A_{ X_i } \oplus Y_i$ で置き換える クエリ 2 : $\oplus…

ACL Beginner Contest, D : Flat Subsequence

問題文 https://atcoder.jp/contests/abl/tasks/abl_d 問題概要 数列 $\{ A_i \}$ と正整数 $K$ が与えられる.以下の条件を満たす数列 $B$ の長さとしてあり得る最大値を求めよ. $B$ は $A$ の部分列 (意味のある)任意の $i$ について $| B_i - B_{ i + …

AtCoder Beginner Contest 179, D : Leaping Tak

問題文 https://atcoder.jp/contests/abc179/tasks/abc179_d 問題概要 $X$ 軸上に住むことを考える(原文参照><;).今,$x = 1$ の地点にいて,次の方法で移動することができる. $K$ 個の区間 $[ L_i, R_i ]$ ($0 \leq i \leq K$) が与えられる.この区…

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 ] の最大値と最小値の差を出力せよ