「USACO 2007 Jan」Balanced Lineup 排队【RMQ】

Time Limit: 5 Sec Memory Limit: 64 MB

Description

每天,农夫约翰的 NN (1N50,0001 \leqslant N \leqslant 50,000) 头牛总是按同一序列排队。有一天,约翰决定让一些牛玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但为了避免水平差距悬殊,牛的身高不应该相差太大。约翰准备了 QQ (1Q180,0001 \leqslant Q \leqslant 180,000) 个可能的牛的选择,和所有牛的身高 (11 \leqslant 身高 1,000,000\leqslant 1,000,000)。他想知道每一组里面最高和最低的牛的身高之差。

注意:在最大数据上,输入和输出将占用大部分运行时间。

Input

11 行:N,QN, Q
22N+1N+1 行:第 i+1i+1 行是第 ii 头牛的身高。
N+2N+2N+Q+1N+Q+1 行:两个整数 A,BA, B (1ABN1 \leqslant A \leqslant B \leqslant N),表示从 AABB 的所有牛。

Output

11QQ 行:所有询问的答案 (最高和最低的牛的身高之差),每行一个。

查看更多

「JSOI 2009」Count【树状数组】

Time Limit: 10 Sec Memory Limit: 64 MB

Description

一个 n×mn \times m 的方格,初始时每个格子有一个整数权值。接下来每次有 22 种操作:

  • 改变一个格子的权值;
  • 求一个子矩阵中某种特定权值出现的个数。

Input

11 行有两个整数 N,MN, M
接下来的 NN 行,每行 MM 个数。第 i+1i+1 行第 jj 个数,表示格子 (i,j)(i, j) 的初始权值。
接下来输入一个整数 QQ
之后的 QQ 行,每行描述一个操作:

  • 操作 1: 1  x y c1 \ \ x \ y \ c 。表示将格子 (x,y)(x, y) 的权值更改为 cc (1xn1 \leqslant x \leqslant n, 1ym1 \leqslant y \leqslant m, 1c1001 \leqslant c \leqslant 100)。
  • 操作 2: 2  x1 x2 y1 y2 c2 \ \ x_1 \ x_2 \ y_1 \ y_2 \ c (其中 x1x2x_1 \leqslant x_2, y1y2y_1 \leqslant y_2)。表示询问所有满足格子颜色为 cc,且 x1xx2x_1 \leqslant x \leqslant x_2, y1yy2y_1 \leqslant y \leqslant y_2 的格子 (x,y)(x, y) 的个数。

Output

对于每个操作 22,按照在输入中出现的顺序,依次输出,每行一个整数表示所求得的个数。

查看更多

「BZOJ 3289」Mato 的文件管理【莫队 + 树状数组】

Time Limit: 40 Sec Memory Limit: 128 MB

Description

Mato 同学从各路神犇以各种方式 (你们懂的) 收集了许多资料,这些资料一共有 nn 份,每份有一个大小和一个编号。为了防止他人偷拷,这些资料都是加密过的,只能用 Mato 自己写的程序才能访问。Mato 每天随机选一个区间 [l,r][l, r],他今天就看编号在此区间内的这些资料。Mato 有一个习惯,他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来,再用他写的排序程序给文件大小排序。排序程序可以在 11 单位时间内交换 22 个相邻的文件 (因为加密需要,不能随机访问)。Mato 想要使文件交换次数最小,你能告诉他每天需要交换多少次吗?

Input

11 行一个正整数 nn,表示 Mato 的资料份数。
22 行由空格隔开的 nn 个正整数,第 ii 个表示编号为 ii 的资料的大小。
33 行一个正整数 qq,表示 Mato 会看几天资料。
接下来的 qq 行,每行两个正整数 l,rl, r,表示 Mato 这天看 [l,r][l, r] 区间的文件。

Output

qq 行,每行一个正整数,表示 Mato 这天需要交换的次数。

查看更多

「Internal」仙人掌 - 多源最短路【仙人掌】

Time Limit: 1 Sec Memory Limit: 128 MB

Description

圣玛格丽特学园的一角有一个巨大、如迷宫般的花坛。大约有一个人这么高的大型花坛,做成迷宫的形状,深受中世纪贵族的喜爱。维多利加的小屋就坐落在这迷宫花坛的深处。某一天早晨,久城同学要穿过这巨大的迷宫花坛,去探望感冒的维多利加。整个迷宫可以用 NN 个路口与 MM 条连接两个不同路口的无向通道来描述。路口被标号为 11NN,每条通道有各自的长度。整个迷宫一定是连通的,迷宫中可能存在若干个环路,但是,出于美观考虑,每个路口最多只会属于一个简单环路。

你需要回答多个这样的询问:假如久城处在路口 xx,维多利加的小屋处在路口 yy,久城最短需要走多少距离才能到达小屋?

Input

第一行 2 个整数 N,MN, M,表示迷宫花坛的路口数和通道数;

接下来 MM 行,每行 3 个整数 x,y,zx,y,z,描述一条连接路口 xx 与路口 yy,长度为 zz 的通道;

再接下来 1 行包含一个整数 QQ,表示询问数量;

之后 QQ 行,每行 2 个整数 x,yx,y,描述一个询问。

Output

对于每个询问输出一行一个整数,表示最短距离。

查看更多

「ZJOI 2007」矩阵游戏【二分图匹配】

Time Limit: 10 Sec Memory Limit: 192 MB

Description

小 Q 是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个 N×NN \times N 黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作:行交换操作:选择矩阵的任意两行,交换这两行(即交换对应格子的颜色)列交换操作:选择矩阵的任意行列,交换这两列(即交换对应格子的颜色)游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。对于某些关卡,小 Q 百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!于是小 Q 决定写一个程序来判断这些关卡是否有解。

Input

11 行包含一个整数 TT,表示数据的组数。
接下来包含 TT 组数据,每组数据第一行为一个整数 NN (N200N \leqslant 200),表示方阵的大小;接下来 NN 行是一个 N×NN \times N 的 01 矩阵 (0 表示白色,1 表示黑色)。

Output

输出文件应包含 TT 行。对于每一组数据,如果该关卡有解,输出一行 Yes;否则输出一行 No。

查看更多