Description
Link.
无修支持查询：查询一个区间 $[l,r]$ 中所有子序列分别去重后的和 $\bmod\ p$
Solution
这是数据结构一百题的第50题（一半了哦）的纪念题解。
无修改操作，基本确定大方向莫队。
考虑查询的问题，我们可以转化一下。即求区间内每个数出现的次数。
一个区间 $[l,r]$ 的子序列数量为：
$$\sum_{i=0}^{r-l+1}C^{i}_{r-l+1}=2^{r-l+1}$$
比如一个数在区间 $[l,r]$ 出现了 $k$ 次，那么一共有 $2^{r-l+1-k}$ 个子序列不包含这个数。这个很好理解，从组合数的意义可知。那么就有 $2^{r-l+1}-2^{r-l+1-k}$ 个子序列包含了这个数。
那么我们就可以用莫队维护区间中出现了 $k$ 次的所有数的和，然后乘上一个 $2^{r-l+1}-2^{r-l+1-k}$ 就是它的贡献了。
问题又来了：每次询问的模数是不确定的，我们需要每次都需要 $\Theta(n)$ 处理一遍2的幂。
有没有什么方法能把处理这个东西的复杂度降到 $\Theta(\sqrt{n})$ 或以下呢？
对此SyadouHayami表示我们可以打个高精。
方法是有的。
我们可以每次询问都处理出 $2^{1},2^{2},\cdots,2^{\sqrt{n}}$ ，以及 $2^{2\sqrt{n}},2^{3\sqrt{n}},\cdots,2^{n}$，都只需要 $\Theta(\sqrt{n})$。当然，都是在模 $p$ 的意义下的。我们分别记为pow1和pow2。
那么 $2^{x}\operatorname{mod}p=(pow1_{x\operatorname{mod}\sqrt{n}}\times pow2_{\lfloor x\div\sqrt{n}\rfloor})\operatorname{mod}p$。
于是就解决问题了。
我的代码遇到了一下两个玄学问题，贴出来给同样情况的人看看：
- 链表部分的
prev和next如果放在结构体里会T。 pow1,pow2,sum,cnt几个数组的定义如果放在最开头和isa以及ans两个数组一起会RE。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int Maxn = 1e5 + 10;
const int Size = 320;
int n, m, isa[ Maxn ], ans[ Maxn ];
struct Query_Node
{
int l, r, p, id, pos;
} Q[ Maxn ];
struct Linked_List
{
int tot, prev[ Maxn ], next[ Maxn ];
Linked_List( ) { tot = 0; }
void insert( int x )
{
next[ tot ] = x;
prev[ x ] = tot;
tot = x;
}
void erase( int x )
{
if( tot == x ) tot = prev[ x ];
else
{
next[ prev[ x ] ] = next[ x ];
prev[ next[ x ] ] = prev[ x ];
}
prev[ x ] = next[ x ] = 0;
}
} llt;
bool cmp( Query_Node rhs, Query_Node shr )
{
if( rhs.pos != shr.pos ) return rhs.l < shr.l;
else return rhs.r < shr.r;
}
int pow1[ Maxn ], pow2[ Maxn ];
void Pare_Two( int p )
{
pow1[ 0 ] = pow2[ 0 ] = 1;
for( int i = 1; i <= Size; ++ i ) pow1[ i ] = 1ll * 2 * pow1[ i - 1 ] % p;
for( int i = 1; i <= Size; ++ i ) pow2[ i ] = 1ll * pow1[ Size ] * pow2[ i - 1 ] % p;
}
int Get_Two( int x, int p )
{
return 1ll * pow1[ x % Size ] * pow2[ x / Size ] % p;
}
int sum[ Maxn ], cnt[ Maxn ];
void Make_Cont( int x, int f )
{
int pos = isa[ x ];
sum[ cnt[ pos ] ] -= pos;
if ( ! sum[ cnt[ pos ] ] ) llt.erase( cnt[ pos ] );
if( f == 1 ) ++cnt[ pos ];
else --cnt[ pos ];
if ( ! sum[ cnt[ pos ] ] ) llt.insert( cnt[ pos ] );
sum[ cnt[ pos ] ] += pos;
}
void Contribute( )
{
int l = 1, r = 0;
for( int i = 1; i <= m; ++ i )
{
Pare_Two( Q[ i ].p );
while( l > Q[ i ].l ) Make_Cont( --l, 1 );
while( l < Q[ i ].l ) Make_Cont( l++, 0 );
while( r > Q[ i ].r ) Make_Cont( r--, 0 );
while( r < Q[ i ].r ) Make_Cont( ++r, 1 );
for( int s = llt.next[ 0 ]; s; s = llt.next[ s ] )
{
int val = 1ll * sum[ s ] * ( Get_Two( r - l + 1, Q[ i ].p ) - Get_Two( r - l + 1 - s, Q[ i ].p ) + Q[ i ].p ) % Q[ i ].p;
ans[ Q[ i ].id ] += val;
ans[ Q[ i ].id ] %= Q[ i ].p;
}
}
}
signed main( )
{
scanf( "%d %d", &n, &m );
for( int i = 1; i <= n; ++ i ) scanf( "%d", &isa[ i ] );
for( int i = 1; i <= m; ++ i )
{
int l, r, p;
scanf( "%d %d %d", &l, &r, &p );
Q[ i ].l = l, Q[ i ].r = r;
Q[ i ].p = p, Q[ i ].id = i;
Q[ i ].pos = l / Size;
}
sort( Q + 1, Q + 1 + m, cmp );
Contribute( );
for( int i = 1; i <= m; ++ i )
printf( "%d\n", ans[ i ] );
return 0;
}