| 题目名称 | 2065. 学数数 |
|---|---|
| 输入输出 | jxthree.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2015-10-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：52， 提交：106， 通过率：49.06% | ||||
 Asm.Def |
100 | 0.293 s | 7.73 MiB | C++ |
 Fmuckss |
100 | 0.371 s | 4.89 MiB | C++ |
 dududu |
100 | 0.372 s | 4.89 MiB | C++ |
|
dududu |
100 | 0.373 s | 4.40 MiB | C++ |
|
dududu |
100 | 0.374 s | 4.89 MiB | C++ |
 0 |
100 | 0.397 s | 2.96 MiB | C++ |
 Narcissus |
100 | 0.429 s | 9.85 MiB | C++ |
 /k |
100 | 0.433 s | 3.83 MiB | C++ |
 cqw |
100 | 0.433 s | 42.28 MiB | C++ |
 BaDBoY |
100 | 0.446 s | 4.31 MiB | C++ |
| 本题关联比赛 | |||
| 20151019 | |||
| 关于 学数数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Hzoi_Mafia :
你还有分呢…… | ||||
|
好不容易考场上打了个$Treap$
去重20 $long long$20 我tm就这样从A到了60 | ||||
|
树状数组
| ||||
|
考试的时候直接搞了个fhq-Treap上去...强行加log...
| ||||
|
这波优化没做好...反而比预估慢了好多.....
| ||||
|
你们在查找答案的时候二分是怎么写的QAQAQ
| ||||
|
其实“利用单调栈预处理某值主导的区间范围”这是个比较经典的思路……
然后发现每次的栈顶元素一定是上次处理的值……所以这里可以把栈删掉，每次直接沿着已经求出的lfst或rfst跳一跳就行了…… | ||||
|
这个只算一边的想法真是6
| ||||
|
1.比赛时差一点就写出来了，真是悲剧（来自手残患者的忧伤）；
2.linux下用int的占位符或I64d读入long long会导致严重的错误，而在windows上是没有错误的 | ||||
HZOI_蒟蒻一只
Hzoi_Mafia
하루Kiev 
Anonymity
slongle
Satoshi
张灵犀不和我一般见识真可怕呢（笑【题目描述】
从前有一只咩，还有一只叽，还有……嗯……一只毒。
毒是咩和叽的师父。
咩经常算不对像3+0.5这样的数，它总认为3+0.5=5。叽经常算不对60+20这样的数，它总认为60+20=100。
所以毒为了锻炼它们数数的能力，想出了下面这个游戏：
毒先在纸上写下n个数a1，a2，…，an，然后咩和叽会找出所有的连续子数组(共有n*(n+1)/2个)，在自己的纸上记录下每个连续子数组的最大值，那之后毒会给
咩和叽Q个问题，每个问题形如下面三种之一：
1．记录的数中有多少个大于K?
2．记录的数中有多少个等于K?
3．记录的数中有多少个小于K?
然而这只咩太蠢了，总是答错毒的问题，咩很伤心，请你帮帮它吧!
【输入格式】
第一行两个整数n，Q。
第二行n个整数a1，a2，…，an。
下面Q行，每行有一个字符op和一个整数K。
如果op是“>”，说明是第一种问题。
如果op是“=”，说明是第二种问题。
如果op是“<"，说明是第三种问题
【输出格式】
共有Q行，第i行表示第i个问题的答案。
【样例输入】
3 5
1 2 3
> 1
< 2
= 3
> 4
< 5
【样例输出】
5
1
3
0
6
【提示】
咩和叽的纸上应该写着1，2，2，3，3，3。
数据范围与约定
对于20％的数据，1≤n≤200，1≤Q≤200，1≤ai，K≤10^6。
对于40％的数据，1≤n≤5000，1≤Q≤5000，1≤ai，K≤10^6。
对于60％的数据，1≤n≤10^5，1≤Q≤10^5，1≤ai，K≤10^6，ai两两不同。
对于80％的数据，1≤n≤10^5，1≤Q≤10^5，1≤ai，K≤10^6。
对于1OO％的数据，1≤n≤10^5，1≤Q≤10^5，1≤ai，K≤10^9。
【来源】
在此键入。