[Ynoi2015]盼君勿忘 题解 莫队+双向链表

· · 题解

题目传送门

第一道 Ynoi 纪念一下qwq

题意

Sol

观察题意，可以发现：

  1. 可离线。

  2. 每次模数不同。

  3. 十有八九爆 \text{int}。

对于第 1 点，容易想到用莫队解决问题。

那么时间复杂度已经到 O(n \sqrt n) 了。（

我们考虑每一位对答案的贡献。

对于区间 [l,r]，考虑 a_i 的贡献 。（l \le i \le r）

设 a_i 在区间 [l,r] 中出现 cnt_{a_i} 次。

我们知道，一个元素总数为 k 的集合的子集个数为 2^k 个。

可由 \sum\limits^k_{i=1}\dbinom{k}{i}=2^k 得出结论。

那么我们接下来算单个元素贡献有两种推导方法。

Sol 1

我们直接从选入手。

那么可得贡献即为选的乘上不选的状态数。

即 (2^{cnt_{a_i}}-1)\times 2^{r-l+1-cnt_{a_i}}。

其中 (2^{cnt_{a_i}}-1) 表示选的非空子集。

可化为 2^{r-l+1}-2^{r-l+1-cnt_{a_i}}。

Sol 2

我们转换一下思路，一个子序列只有包含和不包含两种情况。

那么我们可以想到用总数减去不包含的状态数。

即直接可得 2^{r-l+1}-2^{r-l+1-cnt_{a_i}}。

我们考虑在莫队时保存出现次数相同元素的和。

需要快速插入，删除。

由于不需要保证有序，容易想到双向链表。（建议手写）

--- 我们考虑模数不同，如何迅速求出 $2^k \bmod p

我们考虑关于 \sqrt n 分组。

2^k=2^{\left\lfloor\frac{k}{\sqrt n}\right\rfloor \times \sqrt n+k \bmod \sqrt n}=2^{\left\lfloor\frac{k}{\sqrt n}\right\rfloor \times \sqrt n} \times 2^{k \bmod \sqrt n}

那么我们可以预处理出 2^1，2^2，2^3...2^{\sqrt n}，2^{2\sqrt n}，2^{3\sqrt n}...2^n 取模后的值。

并用上面的公式计算。

那么，似乎问题解决完了？qaq

为了卡常，我们全写 \text{int}，想着还有取模呢。qaq

交一发样例，过了。交一发，WAWAWA，抱灵了。（（（

这时候你需要在一些可能爆炸的地方强制类型转换成 \text{long long}。qwq

这样才可能不 WA。（

不要问我怎么知道 我调这个调了 6 天才发现。

那么交一发 A 了qwq。

为啥加了火车头比不加慢啊qaq

给个刚好能过的代码主要在#9被卡。（

/*
***
还要继续努力
成为一名烤咕学家哦
***
*/
#include<bits/stdc++.h>
#define re register int
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,a[N],len,ans[N],cnt[N],sum[N],l=1,r=0,pw1[N],pw2[N];
struct Question{int l,r,p,id,pos;}q[N];
struct LINKED_LIST{
    struct Link{int pre,nxt;}lk[N];int cnt;
    LINKED_LIST(){cnt=0;}
    inline void Insert(int x){
        lk[cnt].nxt=x;
        lk[x].pre=cnt;
        cnt=x;
    }
    inline void Erase(int x){
        if(x^cnt){
            lk[lk[x].pre].nxt=lk[x].nxt;
            lk[lk[x].nxt].pre=lk[x].pre;
        }
        else cnt=lk[x].pre;
        lk[x].pre=lk[x].nxt=0;
    }
}qaq;
template <typename T> inline void rd(T &x){
    re fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(int x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}
bool cmp(Question x,Question y){
    if(x.pos!=y.pos) return x.pos<y.pos;
    if(x.pos&1) return x.r<y.r;
    return x.r>y.r;
}
inline void init_pow(int p){
    pw1[0]=pw2[0]=1;
    for(re i=1;i<=len;i++) pw1[i]=((ll)1ll*pw1[i-1]*2)%p;
    for(re i=1;i<=len;i++) pw2[i]=((ll)1ll*pw2[i-1]*pw1[len])%p;
}
inline int get_pow(int x,int p){return ((ll)pw1[x%len]*pw2[x/len])%p;}
inline void upd(int x,int op){
    sum[cnt[a[x]]]-=a[x];
    if(!sum[cnt[a[x]]]) qaq.Erase(cnt[a[x]]);
    cnt[a[x]]+=op;
    if(!sum[cnt[a[x]]]) qaq.Insert(cnt[a[x]]);
    sum[cnt[a[x]]]+=a[x];
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(m);
    len=(int)sqrt(n);
    for(re i=1;i<=n;i++) rd(a[i]);
    for(re i=1;i<=m;i++) rd(q[i].l),rd(q[i].r),rd(q[i].p),q[i].id=i,q[i].pos=(q[i].l-1)/len+1;
    sort(q+1,q+m+1,cmp);
    for(re i=1;i<=m;i++){
        init_pow(q[i].p);
        while(l>q[i].l) --l,upd(l,1);
        while(r<q[i].r) ++r,upd(r,1);
        while(l<q[i].l) upd(l,-1),l++;
        while(r>q[i].r) upd(r,-1),r--;
        for(re j=qaq.lk[0].nxt;j;j=qaq.lk[j].nxt)
            ans[q[i].id]=((ans[q[i].id]+(ll)1ll*sum[j]*(get_pow(r-l+1,q[i].p)-get_pow(r-l+1-j,q[i].p))+q[i].p)%q[i].p+q[i].p)%q[i].p;
    }
    for(re i=1;i<=m;i++) wr(ans[i]),puts("");
    return 0;
}