2017-Sp68-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，yzc读到了签到题，丢给cjb，cjb上机'''C1y10'''。yzc和sub讨论了F，yzc上机写F，写了一会儿下机思考，cjb上机写G，'''G1y16'''。yzc继续上机写F，wa了，和sub讨论了一下，修改了算法，'''F2y32'''。sub上机写B，cjb和yzc讨论了M，yzc给出了更加清真的做法，把sub换下来上机'''M1y48'''，sub继续写B，之后'''B1y69'''。sub读了读D，把题意丢给了cjb，cjb和yzc讲了讲，讨论了一下，之后'''D1y81'''。之后cjb和yzc讲了A的做法，上机交替写代码，犯了点小错误，'''A3y109'''。sub丢了个dp给yzc，yzc上机'''E1y125'''，cjb和sub讨论了之后又丢了个dp给yzc，yzc继续'''K1y143'''。之后sub上机写L，cjb和yzc研究J，sub写了一段时间，wa了，yzc上机写J，也获得wa。sub上机改了还是wa，cjb上机写J的对拍，之后sub找到了错误，'''L3y223'''。yzc上机调试J，最后'''J2y265'''，最后3人一起开H，没搞出来。
== 总结 ==
=== chenjb ===
今天比较放松...不过题目做起来没什么感觉。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * I：
  * 题意：每次将一个子串[l,r]置为important或者不important，询问以[l,r]为结尾的串里第k小的important串，n<=100000, q<=200000, k<=50。
  * 解法：将串reverse，先处理出后缀数组，对于前两个操作，相当于选择一个子串，然后将它设置为important或者非important。显然，对于每个子串，以它作为前缀且rank最小的后缀是唯一的，将它作为这个子串的位置，也就是NormalL。然后前两个操作就相当于在线段树上沿路径对节点set进行单点插入或者删除。对于第三个操作，相当于查询一个区间大于len的所有important的子串中长度第K大的有多长。对于询问，因为K比较小，可以在线段树中对应的区间set提取出来大于len的部分塞进vector，然后暴力合并vector，时刻只保留前k个就好了，注意对于询问的串，要找到NormalL和NormalR(即包含该前缀的rk最小和最大后缀)，然后再查询。这题的关键就在于Normal化掉每个子串，就转化为数据结构问题了。
 * [https://wiki.icpc-camp.org/dreadnought/XVI%20Open%20Cup%20named%20after%20E.V.%20Pankratiev.%20Grand%20Prix%20of%20Ukraine Dreadnought]
 * [https://wiki.icpc-camp.org/twsf/XVI%20Open%20Cup%20named%20after%20E.V.%20Pankratiev.%20Grand%20Prix%20of%20Ukraine TheWaySoFar]
== 补题 ==
 * ~~H~~ by sub
 * ~~I~~ by cjb

流水账

开场各自看题，yzc读到了签到题，丢给cjb，cjb上机C1y10。yzc和sub讨论了F，yzc上机写F，写了一会儿下机思考，cjb上机写G，G1y16。yzc继续上机写F，wa了，和sub讨论了一下，修改了算法，F2y32。sub上机写B，cjb和yzc讨论了M，yzc给出了更加清真的做法，把sub换下来上机M1y48，sub继续写B，之后B1y69。sub读了读D，把题意丢给了cjb，cjb和yzc讲了讲，讨论了一下，之后D1y81。之后cjb和yzc讲了A的做法，上机交替写代码，犯了点小错误，A3y109。sub丢了个dp给yzc，yzc上机E1y125，cjb和sub讨论了之后又丢了个dp给yzc，yzc继续K1y143。之后sub上机写L，cjb和yzc研究J，sub写了一段时间，wa了，yzc上机写J，也获得wa。sub上机改了还是wa，cjb上机写J的对拍，之后sub找到了错误，L3y223。yzc上机调试J，最后J2y265，最后3人一起开H，没搞出来。

总结

chenjb

今天比较放松...不过题目做起来没什么感觉。

oipotato

subconscious

题解

  • I：
    • 题意：每次将一个子串[l,r]置为important或者不important，询问以[l,r]为结尾的串里第k小的important串，n<=100000, q<=200000, k<=50。
    • 解法：将串reverse，先处理出后缀数组，对于前两个操作，相当于选择一个子串，然后将它设置为important或者非important。显然，对于每个子串，以它作为前缀且rank最小的后缀是唯一的，将它作为这个子串的位置，也就是NormalL。然后前两个操作就相当于在线段树上沿路径对节点set进行单点插入或者删除。对于第三个操作，相当于查询一个区间大于len的所有important的子串中长度第K大的有多长。对于询问，因为K比较小，可以在线段树中对应的区间set提取出来大于len的部分塞进vector，然后暴力合并vector，时刻只保留前k个就好了，注意对于询问的串，要找到NormalL和NormalR(即包含该前缀的rk最小和最大后缀)，然后再查询。这题的关键就在于Normal化掉每个子串，就转化为数据结构问题了。
  • Dreadnought
  • TheWaySoFar

补题

  • H by sub
  • I by cjb
附加文件