Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

01/1
21:10
主席树

[bzoj 3932] [CQOI2015]任务查询系统

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优先级从小到大排序后取前Ki个)的优先级之和是多少。特别的,如果Ki大于第Xi秒正在运行的任务总数,则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在1到n之间(包含1和n)。

Read More →

[bzoj 3932] [CQOI2015]任务查询系统

@krydom1年前

09/11
13:05
主席树

[bzoj 4408] [Fjoi 2016]神秘数

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13},
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
8无法表示为集合S的子集的和,故集合S的神秘数为8。
现给定n个正整数a[1]..a[n],m个询问,每次询问给定一个区间[l,r](l<=r),求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

Read More →

[bzoj 4408] [Fjoi 2016]神秘数

@krydom1年前

08/4
21:58
主席树 树套树 树状数组

[bzoj 1901] Zju2112 Dynamic Rankings

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。

Read More →

[bzoj 1901] Zju2112 Dynamic Rankings

@krydom2年前

06/3
15:56
主席树 二分法

[bzoj 2653] middle

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整。
给你一个长度为n的序列s。
回答Q个这样的询问:s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中,最大的中位数。
其中a<b<c<d。
位置也从0开始标号。
我会使用一些方式强制你在线。

Read More →

[bzoj 2653] middle

@krydom2年前

03/8
20:08
主席树

Poi2014 Couriers [bzoj 3524]

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 给一个长度为n的序列a。1≤a[i]≤n。
m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。

Read More →

Poi2014 Couriers [bzoj 3524]

@krydom2年前

08/21
18:31
主席树

Feed the dogs [poj 2761]

00:00/00:00

有没有wifi有没有wifi有而且耐用五毛勒!有没有wifi有没有wifi有而且耐用五毛勒!!

203fb80e7bec54e717bd766dbf389b504fc26a6b   m3xj2kmf5lajpg

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 Wind loves pretty dogs very much, and she has n pet dogs. So Jiajia has to feed the dogs every day for Wind. Jiajia loves Wind, but not the dogs, so Jiajia use a special way to feed the dogs. At lunchtime, the dogs will stand on one line, numbered from 1 to n, the leftmost one is 1, the second one is 2, and so on. In each feeding, Jiajia choose an inteval[i,j], select the k-th pretty dog to feed. Read More →

Feed the dogs [poj 2761]