除去1001,1006,1007,1008四道水题外,1002 ~ 1005这4题应该是有铜牌到银牌的难度的,剩下的1009 ~ 1011属于金牌及以上难度。签到题里面,1008可能稍微难一点,到区域赛能出这题并且罚时不高基本可以铜。
1003 后缀数组 + RMQ + 二分 + 主席树
题意
给长度为$10^5$的串$s$,有$m$次查询,查询用$(l,r,k)$表示,要求输出$s[l..r]$这个子串在$s$里面第$k$次出现的位置,如果不存在,输出$-1$。
分析
- 首先由于子串$s[l..r]$肯定会在l处出现一次,并且子串长度为$r-l+1$;
- 不妨对$s$进行后缀排序,学过后缀数组就会知道,rank[i]表示第i个后缀的排名,sa[i]表示排名为i的后缀是谁,height[i]是排名为i和排名为i-1的后缀的最长公共前缀长度;
- 有了这些信息,根据height转移单调性,不妨对height数组建立ST表;
- 设后缀l与排名小于l的后缀的最长公共前缀的最小位置为L,后缀l与排名大于l的后缀的最长公共前缀的最大位置为R,根据height单调性,可以采用二分 + ST表O(1)查询的方式求得;
- 这样,问题就转变成了查询区间$[L,R]$内,$sa[i]$第$k$大是谁,标准的主席树操作。
整体时间复杂度$O((n+m)logn)$,个人感觉难度接近(低于)regional银牌,但由于网络赛各种原因,这题最后出烂了?
我的代码
1 |
|
1002 主席树 + set
题意
给一个长度为$10^5$的排列$A$,有$10^5$次操作。第一种是给$A[i] + 10^7$;第二种是给定一个$k$和$r$,要求找到一个$x$,使得$k \le x$并且x不等于$A[1..r]$中任意一个数。
强制在线。
分析
- 首先可以想到,由于一开始给的A数组是个排列,且第一种操作加的数字固定为$10^7$,所以,操作1可以认为在原序列中删除了$A[i]$这个数字;
- 那么我们可以把A[i]这个数字标记为已经被删除,那么下次查询的时候,一方面我们可以从原序列中去查询第一个大于等于k,且未在A[1..r]出现过的数字,另一方面,我们可以在标记删除的容器里二分找到第一个不小于k的数字,两者取小便可,根据排列的性质,这两个数字一定不会冲突;
- 所以问题就变成了,维护一个set,存放被删除的数字,构造一个主席树,然后查询的时候直接找到第一个合适的数字便可。
时间复杂度$O((n+m)logn)$,个人觉得整体而言比1003简单,介于铜牌题和银牌题之间。
我的代码
已经将输入挂去除,$read(x)$ 等价于 $cin>>x$。
1 |
|