链接：

时间限制：C/C++ 5秒，其他语言10秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

给你一个序列a，有m次，每次查询一个区间[l,r]。

这个区间内一共有2^(r-l+1)-1个非空子序列

一个子序列对答案的贡献是其去重后的和

求所有子序列的贡献的和%p

每次的p不一样

输入描述:

第一行两个数n,m 第二行n个数表示序列a 后面m行每行三个数l,r,p表示查询区间[l,r]，模数是p

输出描述:

对于每个查询输出一行一个数表示答案

示例1

输入

5 51 2 2 3 41 2 2333332 3 3333331 5 2033 5 152 4 8

输出

6617660

说明

[1,2]中有3个子序列(1),(2),(1,2)，贡献分别为1,2,3 [2,3]中有3个子序列(2),(2),(2,2)，贡献分别为2,2,2 [1,5]中有31个子序列 (1),(2),(2),(3),(4),(1,2),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(2,3),(2,4),(3,4),(1,2,2),(1,2,3),(1,2,4),(1,2,3), (1,2,4),(1,3,4),(2,2,3),(2,2,4),(2,3,4),(2,3,4),(1,2,2,3),(1,2,2,4),(1,2,3,4),(1,2,3,4),(2,2,3,4),(1,2,2,3,4) 贡献为:1,2,2,3,4,3,3,4,5,2,5,6,5,6,7,3,6,7,6,7,8,5,6,9,9,6,7,10,10,9,10 [3,5]中有7个子序列 (2),(3),(4),(2,3),(2,4),(3,4),(2,3,4) 贡献为:2,3,4,5,6,7,9 [2,4]中有7个子序列 (2),(2),(3),(2,2),(2,3),(2,3),(2,2,3) 贡献为:2,2,3,2,5,5,5

备注:

对于100%的数据，有1 <= n , m , a[i] <= 100000 , 1 <= p <= 1000000000

看这个题真的是一脸懵逼，看了题解之后算有所收获

贴个题解

/

先考虑单次询问怎么算

对于数x，假设出现了y次，区间长度是len

则x对答案的贡献是

是除了x之外的数有这么多个不同的子序列，这些对x的贡献没有影响

是所有x构成的子序列中有种至少包含一个x，有1种不包含x

如果每次模数一样的话，直接边跑莫队维护就可以了。。。

然而出题人想恶心你，所以每次模数不一样

注意到贡献分为两部分与

其中第一部分非常好维护

第二部分的贡献，可以把出现次数相同的数一起维护贡献

注意到一起区间中只有O( sqrt( n ) )种不同的出现次数

因为1+2+...+sqrt(n) = O(n)

这是一个自然根号

所以我们可以用一个均摊的莫队来维护区间可能的出现次数，从而维护区间中所有出现次数

然后为了O(1)实现快速幂，我们可以每次O( sqrt(n) )算出

2^1,2^2…2^sqrt(n) % p

以及2^sqrt(n),2^2sqrt(n)…2^sqrt(n)*sqrt(n) % p

总复杂度O( nsqrtm + msqrtn ) = O( msqrtn )

//

再贴个自己代码

#include 
     
      #define mst(a,b)    memset((a),(b), sizeof a)#define lowbit(a)   ((a)&(-a))#define IOS         ios::sync_with_stdio(0);cin.tie(0);using namespace std;typedef long long ll;const int mod=1e9+7;const int maxn=1e5+100;int qpow(int b,int p){    ll ret=1;ll a=2;    while(b){        if(b&1)ret=ret*a%p; b>>=1;  a=a*a%p;    }    return (int)ret;}struct node{    int l,r,p,blo,id;    bool operator<(const node&p)const{        return (blo
      
       
        qry[i].r){update(R,-1);--R;}         while(L>qry[i].l){--L;update(L,1);}        while(L
       
      
     

这题的收获主要是在那个sqrt(n)预处理从而o1求出 2^(len-y)%p 那里

之前是做过类似的题目的，然后记忆中一直都是分块分块，很模糊，这次遇到这题才惊叹，哦原来是这么用，还有就是最多只有sqrt(n)种次数，也不知道怎么存，看了别人代码，发现链表完美符合要求，真的是牛批，自己还是太弱了emmm

（这题插入链表开始的时候写错了，调了几个小时，以后要细心点）