P5072 [Ynoi2015]盼君勿忘

一开始理解错题意了……还以为是两个子序列相同的话只算一次……结果是子序列里相同的元素只算一次……

对于一个区间\([l,r]\)，设其中\(x\)出现了\(k\)次，那么它的贡献就是它的权值乘上包含它的序列个数，即\(2^{r-l+1}-2^{r-l+1-k}\)，总的序列个数减去不包含它的序列个数。因为\(x\)和\(k\)无关，所以只要统计出现次数为\(k\)的所有\(x\)的总和即可

不同的\(k\)最多只有\(\sqrt n\)个，于是用个邻接表之类的东西维护一下，然后每次询问就可以\(O(\sqrt n)\)解决了

然而因为模数不同，\(2\)的次幂不能预处理，于是可以设一个\(S=\sqrt n\)，然后用\(O(\sqrt n)\)预处理出\(2^0,2^1,2^2,...,2^S\)和\(2^S,2^{2S},2^{3S},...\)，这样每一个\(2\)的次幂都能\(O(1)\)求得了

然后用莫队维护一下询问就好了，总的时间复杂度为\(O(n\sqrt n)\)

//minamoto

#include<bits/stdc++.h>

#define R register

#define ll long long

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head;i;i=nxt[i])

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(R int x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int N=1e5+5;

int n,m,rt[N],a[N],ans[N],S,Pre[N],nxt[N],vis[N],cnt[N],head=0;

int P,f[1005],g[1005];

ll sum[N];

struct node{

	int l,r,p,id;

	inline bool operator <(const node &b)const

	{return rt[l]==rt[b.l]?rt[b.l]&1?r<b.r:r>b.r:l<b.l;}

}q[N];

inline void add(R int x){nxt[x]=head,Pre[head]=x,head=x,Pre[x]=0;}

inline void del(R int x){x==head?head=nxt[x]:(nxt[Pre[x]]=nxt[x],Pre[nxt[x]]=Pre[x]);}

void update(R int x,R int y){

	if(cnt[a[x]]){

		sum[cnt[a[x]]]-=a[x];

		if(--vis[cnt[a[x]]]==0)del(cnt[a[x]]);

	}cnt[a[x]]+=y;

	if(cnt[a[x]]){

		sum[cnt[a[x]]]+=a[x];

		if(++vis[cnt[a[x]]]==1)add(cnt[a[x]]);

	}

}

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

void init(R int n){

	f[0]=g[0]=1;

	fp(i,1,S)f[i]=add(f[i-1],f[i-1]);

	fp(i,1,n/S)g[i]=mul(g[i-1],f[S]);

}

inline int ksm(R int n){return mul(g[n/S],f[n%S]);}

int query(int l,int r,int p){

	P=p,init(r-l+1);int res=0;

	go(i)res=add(res,mul(sum[i]%P,dec(ksm(r-l+1),ksm(r-l+1-i))));

	return res;

}

int main(){

//	freopen("testdata.in","r",stdin);

	n=read(),m=read(),S=sqrt(n);

	fp(i,1,n)a[i]=read(),rt[i]=(i-1)/S+1;

	fp(i,1,m)q[i].l=read(),q[i].r=read(),q[i].p=read(),q[i].id=i;

	sort(q+1,q+1+m);int l=1,r=0;

	fp(i,1,m){

		while(l>q[i].l)update(--l,1);

		while(r<q[i].r)update(++r,1);

		while(l<q[i].l)update(l++,-1);

		while(r>q[i].r)update(r--,-1);

		ans[q[i].id]=query(q[i].l,q[i].r,q[i].p);

	}fp(i,1,m)print(ans[i]);return Ot(),0;

}

巴特西

P5072 [Ynoi2015]盼君勿忘

最新文章

热门文章