题解 P5072 【[Ynoi2015] 盼君勿忘】
devout
2021-01-16 20:07:01
> 在太阳西斜的这个世界里,置身天上之森。
> 等这场战争结束后,不归之人与望眼欲穿的人们,人人本着正义之名。
> 长存不灭的过去,逐渐消逝的未来。
> 我回来了,纵使日薄西山,即便看不到未来,
> 此时此刻的光辉,**盼君勿忘**。
> ——世上最幸福的女孩
珂朵莉,要幸福哦。
****
主页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;
}
```