Codeforces 777C Alyona and Spreadsheet

Codeforces 777C Alyona and Spreadsheet

题目链接

http://codeforces.com/problemset/problem/777/C

题目大意

给你一个矩阵,多次询问,每次询问 $L$ 和 $R$ ,你需要回答是否存在一列使得L行到R行为不下降序列

题目分析

这题注意到,只要知道 $L$ 行开始,最长不下降序列最长的那列到哪个位置结束就行了,所以可以先预处理找到所有的不下降序列,就可以找到所有的以某行为起始的最长的不下降序列长度,又因为从前面几行延伸过来的其实也是不下降的,所以再求某一行结束位置和前面几行相比的最大值,查询时比较最大结束位置和 $R$ 谁大就可以了。

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Scroll Up