IObuff fread读入优化模板

话不多说,直接上代码吧(自带O3优化)

调用的时候gi(x)就是读入x;可以读long long

2017/9/17 总结

奇袭

©党星宇

Problem

Description:

由于各种原因,桐人现在被困在Under World(以下简称UW)中,而UW马上
要迎来最终的压力测试——魔界入侵。 唯一一个神一般存在的Administrator被消灭了,靠原本的整合骑士的力量
是远远不够的。所以爱丽丝动员了UW全体人民,与整合骑士一起抗击魔族。 在UW的驻地可以隐约看见魔族军队的大本营。整合骑士们打算在魔族入侵前
发动一次奇袭,袭击魔族大本营! 为了降低风险,爱丽丝找到了你,一名优秀斥候,希望你能在奇袭前对魔族
大本营进行侦查,并计算出袭击的难度。 经过侦查,你绘制出了魔族大本营的地图,然后发现,魔族大本营是一个N
×N的网格图,一共有N支军队驻扎在一些网格中(不会有两只军队驻扎在一起)。 在大本营中,每有一个k×k(1≤k≤N)的子网格图包含恰好k支军队,我们袭
击的难度就会增加1点。 现在请你根据绘制出的地图,告诉爱丽丝这次的袭击行动难度有多大。

Input

第一行,一个正整数N,表示网格图的大小以及军队数量。
接下来N行,每行两个整数,Xi,Yi,表示第i支军队的坐标。 保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样
的。

Output

一行,一个整数表示袭击的难度。

Solution

显然,题目可化简为:给定N个数的一个排列,问这个序列中有多少个子区间的数恰好是连续的。
进一步可以化为:有多少种情况使得,相邻的k个数中最大值和最小值的差小于等于k-1。
大致有两种解法,一种是分治,一种是线段树。
这里主要讲一下分治的解法。
考虑分治,对于当前分治区间[L,R],记区间中点为mid。当前区间的答案就是Ans[L..mid]+Ans[mid+1..R]+跨过中点的合法区间数,然后就分为两种情况了:
1.最小值和最大值在同侧。
2.最小值和最大值在异侧。
下面只考虑最值同在左,和最小值在左,最大值在右的情况。其余两种是对称的。
对于最值同在左侧的情况,我们枚举左边界在哪,然后可以计算出右边界的位置,在判断是否合法,统计答案。时间复杂度:O(N).
对于最小值在左侧,最大值在右侧的情况,如果一个区间满足我们所要求的关系的话,就一定有:
移项可得
然后可以用单调栈+桶来完成这个任务。时间复杂度:O(N).
如果加一些黑科技可以大大减少代码量,但是复杂度会多一个log
总的时间复杂度:O(NlogN)/O(NlogN^2)
简单提一下,线段树解法的思路大致也是维护一个单调栈,然后进行区间修改和查询,统计答案。
时间复杂度:O(NlogN).

Code