2019-Sp021-lyk

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,700px)]]

 [http://10.71.10.90/pia/trac/wiki/2019-team2 返回Runespoor]

== 流水账 ==

签到题： E , F , G , J

中期题： A , B , C

后期题： I < H , D

== 总结 ==

zqq：今天节奏仍然没有打好！

我的F题一开始写的是三维数点，但是死活过不了，卡常的过程中还莫名其妙WA了。到最后4h20m才和lyk讨论出了正确做法。这样的签到速度很不应该！'''复杂度错误的东西，尽量不要期待可以卡常通过。特别是三维数点，它的常数基本无法优化！'''

heltion的I题写错了几个细节，但是调试的时候以为是hash冲突了。没有找到正确的方向。浪费了1小时的调试时间。

lyk一开始的时间耗在A题上，还是应该有队友去和他讨论，否则一个人会陷入思维的死胡同！

最后heltion 的H题没能通过，推式子的细节很难调试。'''我们前期更快的话，完全可以zqq和heltion一起推式子，然后zqq去写，heltion想D题。'''但是我们的节奏太乱了！

== 题解 ==
[http://acm.zju.edu.cn/pia/trac/wiki/2016-E28-team1 Siunaus]

* C ：我们可能做麻烦了。下面是sf的做法：

      按照下标模5分为5个序列，维护每个序列各自的段偏移量和段内位置，询问也拆分为5个。O(q)。

* F : 给出两个序列，询问是否存在(i,j),它们在两个序列中都是逆序对！'''存在性问题可以根据性质贪心！'''    扫第一个序列，用set维护一个值和在第二个序列中出现位置都单增的列表。每次lower_bound找到第一个大于a[i]的元素，如果在第二个序列中出现位置 < p2[a[i]] , 则找到合法逆序对。否则往前删除，知道满足在第二个序列中出现位置单增。这样保留的元素一定不会使答案更劣！'''不能卡常三维数点！'''

* I : 求有多少对多项式相乘后等于询问多项式：直接代入值hash即可。模数取1e18,冲突概率是度数/模数

* J ： 同样是hash，把wa/wb质因数分解，维护每个指数次数的hash值，模数同样要去到1e14级别。

== 补题 ==

* D []

* H []

返回Runespoor

流水账

签到题： E , F , G , J

中期题： A , B , C

后期题： I < H , D

总结

zqq：今天节奏仍然没有打好！

我的F题一开始写的是三维数点，但是死活过不了，卡常的过程中还莫名其妙WA了。到最后4h20m才和lyk讨论出了正确做法。这样的签到速度很不应该！复杂度错误的东西，尽量不要期待可以卡常通过。特别是三维数点，它的常数基本无法优化！

heltion的I题写错了几个细节，但是调试的时候以为是hash冲突了。没有找到正确的方向。浪费了1小时的调试时间。

lyk一开始的时间耗在A题上，还是应该有队友去和他讨论，否则一个人会陷入思维的死胡同！

最后heltion 的H题没能通过，推式子的细节很难调试。我们前期更快的话，完全可以zqq和heltion一起推式子，然后zqq去写，heltion想D题。但是我们的节奏太乱了！

题解

Siunaus

• C ：我们可能做麻烦了。下面是sf的做法：

按照下标模5分为5个序列，维护每个序列各自的段偏移量和段内位置，询问也拆分为5个。O(q)。

• F : 给出两个序列，询问是否存在(i,j),它们在两个序列中都是逆序对！存在性问题可以根据性质贪心！ 扫第一个序列，用set维护一个值和在第二个序列中出现位置都单增的列表。每次lower_bound找到第一个大于a[i]的元素，如果在第二个序列中出现位置 < p2[a[i]] , 则找到合法逆序对。否则往前删除，知道满足在第二个序列中出现位置单增。这样保留的元素一定不会使答案更劣！不能卡常三维数点！
• I : 求有多少对多项式相乘后等于询问多项式：直接代入值hash即可。模数取1e18,冲突概率是度数/模数
• J ： 同样是hash，把wa/wb质因数分解，维护每个指数次数的hash值，模数同样要去到1e14级别。

补题

• D []
• H []

附加文件

• 1.png by zhangqingqi