【题解】[Ynoi2015] 盼君勿忘 题解 莫队+双向链表 Luogu P5072 — Demoe

题目传送门

第一道 Ynoi 纪念一下 qwq

题意

• 给定一个序列，每次求一个区间 $[l,r]$ 中所有子序列分别去重后的和 $\bmod p$。

---

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}}$。

---

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

需要快速插入，删除。

由于与顺序无关，容易想到双向链表。

可在 $O(1)$ 时间完成插入删除操作。

---

我们考虑模数不同，如何迅速求出 $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$ 天才发现。

那么就可以过了。

$\text{Code}$

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back

using namespace std;
typedef long long ll;

template <typename T> inline void rd(T &x){
    int 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');
}

// ---------- IO ---------- //


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;

// ---------- Linked List ---------- //

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;}

// ---------- Fast Fast pow( ---------- //

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 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];
}

// ---------- Mo's Algorithm ---------- //

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;
}

// ---------- Main ---------- //