网络游戏

网络游戏

Time Limit:40000MS  Memory Limit:65536K
Total Submit:11 Accepted:3
Case Time Limit:3000MS

Description

TT是个富甲一方的大富豪。作为一个富有激情和创造力的新时代青年,他早做腻了一般的买卖,决定顺应时代潮流,开一家网络公司。由于他从小就热爱网络游 戏,所以TT决定把网络游戏作为他的第一个经营项目。
由于TT的制作团队相当强大,所以TT很快就开发出了一个绝对能盖过暴雪出的一堆游戏的的超牛B网络游戏,一夜之间风靡全球,TT也再次发了一笔 财。当然TT对钱并不感兴趣,他更感兴趣的是游戏本身。
TT的网络游戏会根据玩家的各方面给玩家一个实力积分。TT最喜欢的做的事情是选出一些有代表性的玩家,然后按一种特别的顺序排成一个序列,然后 调查连续的一段中积分不超过V的玩家有多少个,以得知这一片玩家是否实力太弱。当然这个序列是会经常改变的,TT经常会把看不顺眼的玩家T掉、在中间加入 一个玩家。并且,玩家的积分也是经常会变的。
刚开始的时候,由于TT选的人不多,这个序列用他的开发团队写的一个简单程序还可以勉强维护。但人一多起来,TT就有些觉得不爽了,所以他决定请 你给他写个牛B的程序来解决这个问题。

Input

输入文件的第一行包含两个整数n和Q,n代表一开始TT所选玩家个数,Q表示TT的操作数。
接下来一行包含n个整数,表示一开始TT选的各个玩家的积分。
接下来的Q行,每行第一个整数o表示本次的操作类型:
若o=0,则接下来三个整数a,b,c表示TT询问第a个人到第b个人之间积分不超过c的有多少个。
若o=1,则接下来两个整数p,v表示TT在第p个人后面插入了一个积分为v的玩家。若p=0,则表示将该玩家插在序列开头。
若o=2,则接下来一个整数p表示TT将第p个人从序列中删除。
若o=3,则接下来两个整数p,v表示TT将第p个玩家的积分更新为v。

Output

对于每个o=0的操作,输出一行包含一个整数,表示该问题的答案。

Sample Input

5 8
10 2 6 1 5
1 1 7
3 5 5
2 5
0 3 5 8
1 2 7
0 2 5 10
0 3 6 2
2 3

Sample Output

3
4
1

Hint

对于20%的数据 n < =10000,Q < =10000
对于100%的数据 n < =100000,Q < =100000,所有输入整数在maxlongint以内。

Source

2008湖南省队集训By刘鹰
嘿嘿。。让我来给出一个(N+Q)LogN+QLogN^2的算法。。。
首先用Splay或者神马平衡树把最终的序列求出来的。。
然后把还没有插入的数看成maxlongint。。不影响结果。。
然后用线段数套平衡树硬搞就可以了。。。
擦~~写了10KB。。怎么一点都不给力啊。。。还没块状链块。。。

2 thoughts on “网络游戏

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>