luoguP5072 [Ynoi2015]盼君勿忘

luoguP5072 [Ynoi2015]盼君勿忘

原题传送门:>Here<

本来是不会去做Ynoi的毒瘤题的。。。

但是为了珂朵莉怎么都要做一下!!!

不过谁让我水平太差。。。其他的那些神仙题都不会,只能做这道了。


设数字$x​$在查询区间中出现过$b_x​$次,则$x​$出现在$2^{r-l+1}-2^{r-l+1-b_x}​$个子序列内。所以答案就是

$$\sum_{i=1}^{\infty}(2^{r-l+1}-2^{r-l+1-b_i})\cdot i$$

我们用$sum_i$表示出现次数为$i$的数字的和,则答案就变成

$$\sum_{i=1}^{n}(2^{r-l+1}-2^{r-l+1-i})\cdot sum_i​$$

我们发现不同出现次数的数字是$\sqrt{n}$级别的,所以我们可以用一个unordered_set记录所有出现过的次数。

我们只要用莫队统计下每种颜色的出现次数就可以了。

现在还有一个问题就是模数会改变。

我之前还以为要用$exCRT$合并。。。

事实证明是不用的。

我们只需要预处理$2^1,2^2,\cdots,2^{\sqrt{n}}​$以及$2^{2\sqrt{n}},2^{3\sqrt{n}},\cdots,2^n​$对当前模数的余数就可以了,这样复杂度也是$O(\sqrt{n})​$的。


于是这样就做完了。。。?

一道Ynoi的毒瘤题,当然不会让你这么轻易地过去。你要是这样写完就交上去了,会得到T成0分的好成绩。

所以我们需要一些优化:

基础优化(想必不用多说):

  • 莫队奇偶性优化

  • fread,fwrite

  • et cetera

奇葩优化:

  • 乘法优化成

    1
    (ll)x*y-(ll)x*y/P*P
  • 考虑我们的式子:

    $$\sum_{i=1}^{n}(2^{r-l+1}-2^{r-l+1-i})\cdot sum_i$$

    对于每一项,我们都需要做减法,常数较大。我们考虑把式子拆开。

    $$(2^{r-l+1}\sum_{i=1}^{n}sum_i)-\sum_{i=1}^{n}2^{r-l+1-i}\cdot sum_i$$

    我们可以一边莫队一边处理$tot=\sum_{i=1}^{n}sum_i$,然后拆出来计算。

  • unordered_set较慢,我们考虑使用链表记录出现过的次数。

  • 我们发现预处理时$2^1,2^2,\cdots,2^{\sqrt{n}}$只要左移1就可以了,而处理$2^{2\sqrt{n}},2^{3\sqrt{n}},\cdots,2^n$则需要进行乘法,所以我们考虑把预处理范围变成$(r-l+1)^{0.6}$

这样能跑到$16641ms$,是当前最优解($2019/1/13$)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

namespace IO
{
const unsigned int Buffsize=1<<25,Output=1<<25;
static char Ch[Buffsize],*St=Ch,*T=Ch;
inline char getc()
{
return((St==T)&&(T=(St=Ch)+fread(Ch,1,Buffsize,stdin),St==T)?0:*St++);
}
static char Out[Output],*nowps=Out;

inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

inline int read()
{
int x=0;static char ch;
for(ch=getc();!isdigit(ch);ch=getc());
for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
return x;
}

template<typename T>inline void write(T x)
{
if(!x)*nowps++=48;
if(x<0)*nowps++='-',x=-x;
static unsigned int sta[111],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;*nowps++=sta[tp--]^48);
*nowps++='\n';
}
}
using namespace IO;

typedef long long ll;

int pos[100010],a[100010],orig[100010],lim,sn,n,count[100010],m,power[100010],p2[100010],nxt[100010],pre[100010],P,ans[100010],block;
ll sum[100010],tot;
struct point{
int l,r,orig,P;
}num[100010];
inline bool cmp(const point &a,const point &b){return pos[a.l]!=pos[b.l]?a.l<b.l:((pos[a.l]&1)?a.r<b.r:a.r>b.r);}
inline void add(int &y,int x){
static int prev;
if(!(prev=y))tot+=x;
if(sum[y]==x&&y>0&&y<=n){
prev=pre[y];
nxt[pre[y]]=nxt[y];
pre[nxt[y]]=pre[y];
}
if(y>0&&y<=n)sum[y]-=x;
++y;
if(!sum[y]&&y>0&&y<=n){
pre[y]=prev;
nxt[y]=nxt[prev];
nxt[pre[y]]=pre[nxt[y]]=y;
}
if(y>0&&y<=n)sum[y]+=x;
}
inline void Add(int x){add(count[x],orig[x]);}
inline void del(int &y,int x){
static int hence;
hence=y;
if(sum[y]==x&&y>0&&y<=n){
hence=nxt[y];
nxt[pre[y]]=nxt[y];
pre[nxt[y]]=pre[y];
}
if(y>0&&y<=n)sum[y]-=x;
--y;
if(!sum[y]&&y>0&&y<=n){
nxt[y]=hence;
pre[y]=pre[hence];
nxt[pre[y]]=pre[nxt[y]]=y;
}
if(y>0&&y<=n)sum[y]+=x;
if(!y)tot-=x;
}
inline void Del(register int x){del(count[x],orig[x]);}
inline int Mul(register int x,register int y){
return (ll)x*y-(ll)x*y/P*P;
}
inline int qsm(register int b){
return Mul(power[b%block],p2[b/block]);
}
inline int Add(register int x,register int y){
x+=y;
return (x>=P)?x-P:x;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out1.txt","w",stdout);
n=read(),m=read();
sn=sqrt(n);
for(register int i=1;i<=n;++i)orig[i]=a[i]=read();
std::sort(orig+1,orig+n+1);
lim=std::unique(orig+1,orig+n+1)-orig-1;
for(register int i=1;i<=n;++i)a[i]=std::lower_bound(orig+1,orig+lim+1,a[i])-orig,pos[i]=(i-1)/sn+1;
for(register int i=1;i<=m;++i){
num[i].l=read(),num[i].r=read(),num[i].P=read();
num[i].orig=i;
}
std::sort(num+1,num+m+1,cmp);
register int ql=1,qr=0;
power[0]=p2[0]=1;
nxt[0]=++n;
for(register int i=1,tem,length,orig;i<=m;++i){
while(ql>num[i].l)Add(a[--ql]);
while(qr<num[i].r)Add(a[++qr]);
while(ql<num[i].l)Del(a[ql++]);
while(qr>num[i].r)Del(a[qr--]);
length=num[i].r-num[i].l+1;
P=num[i].P;
block=pow(length,0.6)+1;
tem=length/block;
for(register int j=1;j<=block;++j)if((power[j]=(power[j-1]<<1))>=P)power[j]-=P;
for(register int j=1;j<=tem;++j)p2[j]=Mul(p2[j-1],power[block]);
tem=Mul(qsm(length),tot%P);
orig=num[i].orig;
for(register int j=nxt[0];j!=n;j=nxt[j])if((ans[orig]+=Mul(qsm(length-j),sum[j]%P))>=P)ans[orig]-=P;
ans[orig]=tem-ans[orig];
if(ans[orig]<0)ans[orig]+=P;
}
for(register int i=1;i<=m;++i)write(ans[i]);
flush();
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×