题解 P5072 【[Ynoi2015] 盼君勿忘】

devout

2021-01-16 20:07:01

Solution

> 在太阳西斜的这个世界里,置身天上之森。 > 等这场战争结束后,不归之人与望眼欲穿的人们,人人本着正义之名。 > 长存不灭的过去,逐渐消逝的未来。 > 我回来了,纵使日薄西山,即便看不到未来, > 此时此刻的光辉,**盼君勿忘**。 > ——世上最幸福的女孩 珂朵莉,要幸福哦。 **** 主页AC 1k祭( 考虑一个数在区间里面会被算上多少次贡献 我们可以用全部区间减去包含这个数的区间,假设这个数在这段区间里出现了 $k$ 次,那么贡献就是 $2^{r-l+1}-2^{r-l+1-k}$ 考虑一个~~经典~~的思想,对于 $\sqrt n$ 分类讨论 对于所有 $\leq \sqrt n$ 的数,我们可以记录出现了 $i$ 次的所有数的和,然后一起计算贡献 对于所有 $> \sqrt n$ 的数,这样的数不超过 $\sqrt n$ 个,所以我们可以把他们弄到一个链表里面暴力求。 在外面套一个莫队,就可以 $\mathcal O(n\sqrt n)$ 搞定了 但是注意有一个问题,就是每次的模数不一样,所以我们每次需要跑快速幂,会多出来一个 log,所以我们应该用光速幂来搞,这样可以保证复杂度不会炸 代码还是很好写的,注意不要炸 int,其他地方就没什么坑了( ```cpp #include <bits/stdc++.h> using namespace std; # define Rep(i,a,b) for(int i=a;i<=b;i++) # define _Rep(i,a,b) for(int i=a;i>=b;i--) # define RepG(i,u) for(int i=head[u];~i;i=e[i].next) typedef long long ll; const int N=1e5+5; template<typename T> void read(T &x){ x=0;int f=1; char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0'; x*=f; } int n,m,sq; int a[N],tim[N]; ll sum[N]; int pow1[N],pow2[N]; int head,tail,pre[N],nxt[N]; int out[N]; int pos[N]; struct texas{ int id,l,r,p; }q[N]; bool cmp(texas x,texas y){ if(pos[x.l]!=pos[y.l])return pos[x.l]<pos[y.l]; if(pos[x.l]&1)return x.r<y.r; else return x.r>y.r; } void init(int p){ pow1[0]=1%p; Rep(i,1,sq)pow1[i]=1ll*pow1[i-1]*2%p; pow2[0]=pow1[0]; Rep(i,1,sq)pow2[i]=1ll*pow2[i-1]*pow1[sq]%p; } int getpow(int k,int p){ if(k<=0)return 1; return 1ll*pow1[k%sq]*pow2[k/sq]%p; } void insert(int x){ nxt[x]=tail; pre[x]=pre[tail]; nxt[pre[tail]]=x; pre[tail]=x; } void dereto(int x){ nxt[pre[x]]=nxt[x]; pre[nxt[x]]=pre[x]; nxt[x]=pre[x]=0; } void add(int x){ sum[tim[x]]-=x; tim[x]++; sum[tim[x]]+=x; if(tim[x]==sq+1)insert(x); } void del(int x){ sum[tim[x]]-=x; tim[x]--; sum[tim[x]]+=x; if(tim[x]==sq)dereto(x); } int main() { read(n),read(m); Rep(i,1,n)read(a[i]); sq=sqrt(n)+1; Rep(i,1,n)pos[i]=(i-1)/sq+1; Rep(i,1,m)q[i].id=i,read(q[i].l),read(q[i].r),read(q[i].p); sort(q+1,q+m+1,cmp); head=n+1,tail=n+2; nxt[head]=tail; pre[tail]=head; Rep(i,1,n)sum[0]+=a[i]; for(int i=1,l=1,r=0;i<=m;i++){ while(l>q[i].l)add(a[--l]); while(r<q[i].r)add(a[++r]); while(l<q[i].l)del(a[l++]); while(r>q[i].r)del(a[r--]); init(q[i].p); int tot=getpow(q[i].r-q[i].l+1,q[i].p); Rep(j,1,sq){ out[q[i].id]+=1ll*sum[j]%q[i].p*(tot-getpow(q[i].r-q[i].l+1-j,q[i].p)+q[i].p)%q[i].p; out[q[i].id]%=q[i].p; } for(int it=nxt[head];it!=tail;it=nxt[it]){ out[q[i].id]+=1ll*it*(tot-getpow(q[i].r-q[i].l+1-tim[it],q[i].p)+q[i].p)%q[i].p; out[q[i].id]%=q[i].p; } } Rep(i,1,m)printf("%d\n",out[i]); return 0; } ```