4.28测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------
HNOI2016 Day2
--------------------------------------------------------
T1:
首先每个人求一个他作为最小值的区间[l,r]
然后如果没有范围限制,那么答案就是Σa[i]*(r-i+1)*(i-l+1)
对于每个询问,求出询问区间内的Σa[i]*(r-i+1)*(i-l+1)
然后只需减去超出的
两边都超出的最多只有1个,这个特殊处理一下,剩下的要么左边超,要么右边超,要么不超
以左边超为例:
假设一个人的区间是[l,r],询问是[l',r']
那么算总贡献的时候他贡献了a[i]*(i-l+1)*(r-i+1)
实际上的贡献应该是a[i]*(i-l'+1)*(r-i+1)
应该减去的贡献是(l'-l)*a[i]*(r-i+1)=l'*a[i]*(r-i+1)-l*a[i]*(r-i+1)
因此对于每个人记录一个
b[i]=a[i]*(r-i+1)
c[i]=l*a[i]*(r-i+1)
询问的时候用l*Σb[i]-Σc[i]就行了
但是这里只算l<l'的i
怎么办呢?=w=
弄个主席树,把每个人的b(c)记在l[i]这个位置
询问的时候询问前(后)缀和就行了
--------------------------------------------------------
T2:
什么鬼啊?
不会...
--------------------------------------------------------
T3:
设h[i]表示i的哈希值
发现如果[a,b]是P的倍数
那么有h[b]-h[a]*10^(b-a)=0(mod P)
因此h[b]=h[a]*10^(b-a)
两边乘以10^(n-b):
h[b]*10^(n-b)=h[a]*10^(n-a)
设val[i]=h[i]*10^(n-i)
因此相当于要问区间内val相等的有多少对
然后就把val离散化一下就可以莫队辣O(∩_∩)O
这样好像就能A
然后因为2和5是10的约数,因此要特判P=2或者5的情况
说来也巧,P=2或者5的时候答案特别好求
--------------------------------------------------------
评论 (0)
