相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4373
神犇题解:http://blog.csdn.net/TA201314/article/details/51177011
解题报告
首先,假如一个区间满足以下三个条件那么该区间一定合法:
$\%k$后相等
每一个数互不相同
区间和等于某一特定值
后两个条件都可以用线段树维护
问题就是第一个条件非常麻烦
先来考虑一种简单的Hash方式:记录区间的平方和
这样的话,我们可以$O(1)$计算基准值,$O(\log n)$判断是否等于基准值
但众所周知,Hash是不优雅的
于是我们可以先做一个差分序列,然后维护差分序列相邻两项的$\gcd$
考虑如果所有数的差都是$k$的整数倍,那么这些数$ \bmod \ k$之后肯定就相等啦!
另外的话,区间GCD配合差分的题,也不是第一次见了
之前NOI还考过一道:魔幻棋盘
以后和GCD相关的题目要想一想差分行不行啊!
Thanks on your marvelous posting! I genuinely enjoyed reading it, you will be a great author.I will ensure that I bookmark your blog and definitely will come back at some point. I want to encourage you to definitely continue your great writing, have a nice day!
490684 210905Extremely nice style and amazing content material material , nothing else we want : D. 176451
534721 681522Some times its a discomfort inside the ass to read what men and women wrote but this web web site is very user friendly ! . 502450
165625 333298I genuinely delighted to locate this internet web site on bing, just what I was searching for : D too saved to fav. 267406
741137 517055Most heavy duty trailer hitches are designed utilizing cutting edge computer aided models and fatigue stress testing to ensure optimal strength. Share new discoveries along with your child and keep your child safe by purchasing the correct design for your lifestyle by following the Perfect Stroller Buyers Guideline. 24847
93325 51562I was suggested this website by my cousin. Im not confident whether this post is written by him as no one else know such detailed about my trouble. You are wonderful! Thanks! xrumer 202209
355676 953158Nie and informative post, your every post worth atleast something. 542543
532651 318133quite good post, i certainly enjoy this amazing site, persist with it 899219
237178 350400This really is something I in fact have to try and do a lot of analysis into, thanks for the post 494580
like
like
417204 890772I come across your webpage from cuil and it is high quality. Thnkx for giving this sort of an incredible post.. 27763
like
like
like
good
lik
I like what you guys are up too. Such clever work and reporting! Carry on the excellent works guys I¦ve incorporated you guys to my blogroll. I think it’ll improve the value of my website 🙂