苏州网站开发建设服务,广东网站建设商家,用python做网站的步骤,wordpress 绑定手机F-序列查询
v5zsq题解
假设数字xxx在区间[l,r]种出现y次#xff0c;那么包含x的子区间个数为2r−l1−y⋅(2y−1)2^{r-l1-y}(2^y-1)2r−l1−y⋅(2y−1)#xff0c;因此对询问贡献是x⋅2r−l1−y⋅(2y−1)x[2r−l1−2r−l1−y]x2^{r-l1-y}(2^y-1)x[2^{r-l1}-2^{r-l1-y}]x⋅2r…F-序列查询
v5zsq题解
假设数字xxx在区间[l,r]种出现y次那么包含x的子区间个数为2r−l1−y⋅(2y−1)2^{r-l1-y}·(2^y-1)2r−l1−y⋅(2y−1)因此对询问贡献是x⋅2r−l1−y⋅(2y−1)x[2r−l1−2r−l1−y]x·2^{r-l1-y}·(2^y-1)x[2^{r-l1}-2^{r-l1-y}]x⋅2r−l1−y⋅(2y−1)x[2r−l1−2r−l1−y] 其中第一部分非常好维护第二部分的贡献可以把出现次数相同的数一起维护贡献 sum[k]维护出现从次数为k的数字总和是多少。用个链表加快计算。
注意到一起区间中只有O(n)O( \sqrt n )O(n)种不同的出现次数因为12...nO(n)12...\sqrt n O(n)12...nO(n)这是一个自然根号所以我们可以用一个均摊的莫队来维护区间可能的出现次数从而维护区间中所有出现次数然后为了O(1)实现快速幂我们可以每次O(n)O(\sqrt n)O(n)算出21,22…2nmodp2^1,2^2…2^{\sqrt n} \mod p21,22…2nmodp以及2n,22n…2nnmodp2^{\sqrt n},2^{2\sqrt n}…2^{\sqrt n\sqrt n} \mod p2n,22n…2nnmodp
#includebits/stdc.h
#pragma GCC optimize(2)
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
ll qmi(ll a,ll b,ll mod)
{ll v1;while(b){if(b1) vv*a%mod;aa*a%mod;b1;}return v;
}
const int N100005;
int Bs,b[N],a[N],n,m;
struct node
{int l,r,p,id;bool operator(const nodeo)const{if(b[l]b[o.l]){if(b[l]1) return ro.r;return ro.r;}return b[l]b[o.l];}
}q[N];
int num[N],cnt[N];
ll sum[N];
int h,fr[N],ne[N];
int ans[N];
int mod;
void insert(int x)
{ne[x]h;fr[h]x;fr[x]0;hx;
}
void del(int x)
{if(hx) return hne[x],void();ne[fr[x]]ne[x];fr[ne[x]]fr[x];
}
void update(int x,int v)
{// 出现个数为num[x]-xif(num[x]){sum[num[x]]-x;cnt[num[x]]--;if(!cnt[num[x]]) del(num[x]);}num[x]v;if(num[x]){sum[num[x]]x;cnt[num[x]];if(cnt[num[x]]1) insert(num[x]);}
}
int add(int a,int b)
{ab;if(amod) a-mod;return a;
}
int mul(int a,int b)
{ll z1ll*a*b;return z-z/mod*mod;
}
int f[1005],g[1005];
void init(int n)
{f[0]1;for(int i1;iBs;i) f[i]add(f[i-1],f[i-1]);g[0]1;for(int i1;in/Bs;i) g[i]mul(g[i-1],f[Bs]);
}
int Pow(int n)
{return mul(g[n/Bs],f[n%Bs]);
}
int query(int l,int r,int p)
{modp;int lenr-l1;init(n); int ans0;for(int ih;i;ine[i]) ansadd(ans,mul(sum[i]%p,add(Pow(len),p-Pow(len-i))));return ans;
}
int main()
{nrd(),mrd();for(int i1;in;i) a[i]rd();Bssqrt(n)1;for(int i1;in;i) b[i](i-1)/Bs1;for(int i1;im;i) q[i].lrd(),q[i].rrd(),q[i].prd(),q[i].idi;sort(q1,q1m);int l1,r0;for(int i1;im;i){while(rq[i].r) update(a[r],1);while(rq[i].r) update(a[r--],-1);while(lq[i].l) update(a[l],-1);while(lq[i].l) update(a[--l],1);ans[q[i].id]query(q[i].l,q[i].r,q[i].p);}for(int i1;im;i) printf(%d\n,ans[i]);}
