BZOJ3289 Mato的文件管理

Time Limit: 40 Sec (Total)

Memory Limit: 128 MB

莫队+树状数组维护

类(jiu)似(shi)冒泡排序的过程

注意优化时间

BZOJ1878 | SDOI2009 HH的项链

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入输出格式

输入格式:

第一行:一个整数N,表示项链的长度。

第二行:N 个整数,表示依次表示项链中贝壳的编号(编号为0 到1000000 之间的整数)。

第三行:一个整数M,表示HH 询问的个数。

接下来M 行:每行两个整数,L 和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

输出格式:

M 行,每行一个整数,依次表示询问对应的答案

什么描述啊……

我们可以 简单地 发现对于每次区间询问,如果一种编号出现了多次,那么只有最后一次才是有意义的。

那么离线询问并按照R为第一关键字,L为第二关键字排序。

然后从当前位置指针(初始为1,当然)扫到R统计有没有新出现的和重复出现的

如果是新出现的那么标记一下再扔到树状数组里(哦,忘记了,树状数组是按位置建的,也就是下标和项链是对应的)

如果是重复出现的,那么,有一个数组保存之前出现的位置,get到这个位置然后往树状数组里这个位置扔一个-1就行了。

之后更新前一次出现位置数组并扔进树状数组里。

最后求区间和……

真是一道好题。

#洛谷P2448 无尽的生命

题目描述

逝者如斯夫,不舍昼夜!

叶良辰认为,他的寿命是无限长的,而且每天都会进步。

叶良辰的生命的第一天,他有1点能力值。第二天,有2点。第n天,就有n点。也就是S[i]=i

但是调皮的小A使用时光机,告诉他第x天和第y天,就可以任意交换某两天的能力值。即S[x]<–>S[y]

小A玩啊玩,终于玩腻了。

叶良辰:小A你给我等着,我有100种办法让你生不如死。除非能在1秒钟之内告知有多少对“异常对”。也就是说,最后的能力值序列,有多少对的两天x,y,其中x<y,但是能力值S[x]>S[y]?

小A:我好怕怕啊。

于是找到了你。

对于30%的数据,x_i,y_i <= 2000

对于70%的数据, x_i,y_i <= 100000

对于100%的数据, x_i.y_i <= 2^31-1 k<=100000

逆序对裸题

由于xy这么大我们来离散化

把只要是交换过的(不管几次)都标记下来,排下序(点权为1)

没交换过的一些区间缩成一个点(点权为区间长度)

然后进行离散化操作,离散成新的段,相邻两点间下标严格递增1(还有一个就是开头没被交换的区间对答案没有影响直接扔掉)

我们离线了交换操作,这个时候就二分查找,把原来应该换哪两个点映射成现在应该换哪两个点

全换完之后就是个裸的逆序对问题,按点权建树状数组,然后统计区间和就行了。

·

//注释是做题的时候瞎写的凑合着看看吧,要说的都说了。

BZOJ2028 | SHOI2009 Booking 会场预约

题目描述

PP大厦有一间空的礼堂,可以为企业或者单位提供会议场地。这些会议中的大多数都需要连续几天的时间(个别的可能只需要一天),不过场地只有一个,所以不同的会议的时间申请不能够冲突。也就是说,前一个会议的结束日期必须在后一个会议的开始日期之前。所以,如果要接受一个新的场地预约申请,就必须拒绝掉与这个申请相冲突的预约。一般来说,如果PP大厦方面事先已经接受了一个会场预约,例如从10日到15日,就不会在接受与之相冲突的预约,例如从12日到17日。不过,有时出于经济利益,PP大厦方面有时会为了接受一个新的会场预约,而拒绝掉一个甚至几个之前预订的预约。于是,礼堂管理员QQ的笔记本上笔记本上经常记录着这样的信息: 本题中为方便起见,所有的日期都用一个整数表示。例如,如果一个为期10天的会议从“90日”开始到“99日”,那么下一个会议最早只能在“100日”开始。最近,这个业务的工作量与日俱增,礼堂的管理员QQ希望参加SHTSC的你替他设计一套计算机系统,方便他的工作。这个系统应当能执行下面两个操作: A操作:有一个新的预约是从“start日”到“end日”,并且拒绝掉所有与它相冲突的预约。执行这个操作的时候,你的系统应当返回为了这个新预约而拒绝掉的预约个数,以方便QQ与自己的记录相校对。 B操作:请你的系统返回当前的仍然有效的预约的总数。


输入格式

输入文件的第一行是一个整数n,表示你的系统将接受的操作总数。接下去n行每行表示一个操作。每一行的格式为下面两者之一: “A start end”表示一个A操作; “B”表示一个B操作。


输出格式

输出文件有n行,每行一次对应一个输入。表示你的系统对于该操作的返回值。

二分+树状数组/线段树

还是用树状数组吧。

我们考虑所有接受的预约的开始时间都是严格递增的,那么我们建立Fenwick Tree,add(i,1)表示开始时间为i的预约存在,加入fwt

然后考虑拒绝的情况

二分查找所有开始时间小于等于当前预约结束时间的预约(只有这样才有可能被拒绝)

然后找到:开始时间与当前预约的结束时间最接近的一个预约。检查它的结束时间是否大于等于当前预约的开始时间建议画区间图

考虑未加入当前预约之前所有预约的开始、结束时间都是满足严格递增关系的,如果找到的最接近结束时间的都不与当前预约冲突,那在它之前的所有预约其结束时间严格递减,更不可能被拒绝。

所以直接break

而考虑右边(时间轴),如果能找到开始时间在当前预约的结束时间左边的预约,那就不可能跑到当前预约的右面。整体在当前预约右面的也一定不会被二分找到。

所以这样考虑到了所有情况

然后就统计一下输出就行了。

注意拒绝的时候还要add(position,-1),还有就是一开始就要查一下在当前预约的结束时间左边一共有多少预约。用这个二分。

POJ 2985 The k-th Largest Group

题目大意是这样的      查看原题

某人养了很多猫,从1-n编号,他想给她们(??!)分成几组,给出m个操作,其中可以

1)给出第i群猫和第j群猫,把她们合并。(注意猫i代表了第i群猫,而如果,猫k也在这群猫里,那猫k也能代表这群猫)

2)在线询问某次操作之后第k大的猫群有多大

考虑1)显然是一个并查集。

2)可以按照猫群大小建Fenwick Tree然后查找区间第k大数就可以了。

特别推荐这篇博文(虽然弱弱的我看了好久才看懂)

Press Here

然后是Code