[Ynoi2015] 盼君勿忘

题传

世纪诈骗题

首先，所有子序列分别去重的和的意思是什么？

令可重集 /(S/) 为序列 /(a_l, a_{l+1}/dots a_r/) 的所有子序契合。

假设我们有一个序列 /(T/)，对 /(T/) 去重后变为 /(T’/)，令 /(f(T)=/sum_{x /in T’} x/)，则题目所求为 /(/sum_{T /in S} f(T)/)。

显然我们不能把所有的子序列都弄出来，那样就是 /(2^{r-l+1}/) 级别的，考虑每种数的贡献。为什么是每种而不是每个呢？因为去重后我们就丢失了原来的下标（意思就是多个随便选），贡献不好统计。

那么这种数的贡献应该是多少呢？

设其出现次数为 /(cnt_x/)，只要出现了这种数贡献 +1，那么应该就是总子序列数 – 没有出现这种数的子序列数。

就是 /(2^{r-l+1}-2^{r-l+1-cnt_x}/)，最后还要乘上这个数本身，即 /(x(2^{r-l+1}-2^{r-l+1-cnt_x})/)。

你发现 /(cnt/) 相同的 /(x/) 珂以合并到一起，然后你实际上就是维护一个 /(sum_{cnt}/)，和 /(2^{r-l+1-cnt}/) 这么个玩意。

首先把询问简单化，如果只询问全局，把底数从 /(2/) 变成 /(3 /dots 114514/) 之类的，怎么做？

其实有个很简单的东西：暴力。

为什么？高斯告诉我们 /(1+2+/dots /sqrt n /to n/)，所以不同的 /(cnt/) 最多 /(/sqrt n/) 种，所以复杂度肥肠正确。

转回到原题，我们需要快速的整出 /(cnt/) 和对应的 /(sum/)，注意到这是对区间信息的一个整体查询，又没有强制在线，所以直接莫队。

在移动的时候，会产生/消失某个 /(cnt/)，我们需要一个能支持 单个插入/删除 和 整体遍历 的数据结构，显然就是链表了。

复杂度 /(O(n/sqrt m + m/sqrt n)/)，非常好写。

Code：

const int N=1e5+5;
const int R=320;//sqrt N 
struct Edge{int lst, nxt;}d[N];//上一个，下一个，下标 出现次数
int n, m, mi1[R], mi2[R], a[N];
int Mp[N], head, vis[N];
long long sum[N];
int Mod, dis, sq, ans[N];
inline int add(int x, int y){return (x+y)%Mod;}
inline int mul(int x, int y){return 1ll*x*y%Mod;}
void pre(int mo){
	Mod=mo;mi1[0]=mi2[0]=1;
	for(int i=1; i<=sq; i++) mi1[i]=add(mi1[i-1], mi1[i-1]);
	mi2[1]=mi1[sq];
	for(int i=2; i*sq<=n; i++) mi2[i]=mul(mi2[i-1], mi2[1]);
	return ;
}
int ksm(int b){
	return 1ll*mi2[b/sq]*mi1[b%sq]%Mod;
}
struct Query{
    int x, y, P, id;
    bool operator < (const Query &S) const{
        if(x/dis!=S.x/dis) return x/dis<S.x/dis;
        return y<S.y;
    }
    void get(int s){x=read(), y=read(), P=read(), id=s;}
}Q[N];
inline void doit(int x, int v){
	#define pos Mp[a[x]]
	if(pos){
		sum[pos]-=a[x];
		if(--vis[pos]==0){
			if(pos==head) head=d[pos].lst;
			else d[d[pos].nxt].lst=d[pos].lst;
			d[d[pos].lst].nxt=d[pos].nxt;
		}
	}
	pos+=v;
	if(pos){
		sum[pos]+=a[x];
		if(++vis[pos]==1){
			d[pos].lst=head;
			d[head].nxt=pos;head=pos;
			d[pos].nxt=0;
		}
	}
	#undef pos
}
inline void add(int x){doit(x, 1);}
inline void del(int x){doit(x, -1);}
inline int mis(int x, int y){return x<y?x-y+Mod:x-y;};
inline void move(int &l, int &r, int x, int y){
    while(l>x) add(--l);
    while(r<y) add(++r);
    while(r>y) del(r--);
    while(l<x) del(l++);
    return ;
}
signed main(){
	n=read(), m=read();if(!m) return 0;dis=n/sqrt(m);sq=sqrt(n);
	for(int i=1; i<=n; i++) a[i]=read();
	for(int i=1; i<=m; i++) Q[i].get(i);
	sort(Q+1, Q+m+1);int L=1, R=0;
	for(int i=1; i<=m; i++){
		pre(Q[i].P);
		move(L, R, Q[i].x, Q[i].y);
		int pwp=Q[i].y-Q[i].x+1, qwq=ksm(pwp);
		for(int s=head; s; s=d[s].lst) 
			ans[Q[i].id]=add(ans[Q[i].id], mul(sum[s]%Mod, mis(qwq, ksm(pwp-s))));
		ans[Q[i].id]=(ans[Q[i].id]%Mod+Mod)%Mod;//(2^len-2^{len-k})*x
	}
	for(int i=1; i<=m; i++) printf("%d/n", ans[i]);
    return 0;
}