これこそシュタインズ・ゲートの选択だ

luogu P5072 [Ynoi2015]盼君勿忘

luogu P5072 [Ynoi2015]盼君勿忘

这题有毒….反正我的写法常数巨大
[l,r]中出现次数为k的数的和为s[k]
则答案显然为 \sum{s[k]*(2^{r-l+1}-2^{r-l+1-k})}
因为值不为0的s[k]最多有sqrt(n)个,直接用hash表统计,莫队即可
我的做法由于常数原因,得分在60~100左右
代码:

#include<bits/stdc++.h>
using namespace std;
#define reg register
const int N=1e5+5;
typedef long long ll;
inline int read(){
    reg int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
    return s*f;
}
const int block=317;
int n,m;
int a[N],cnt[N],bel[N];
unordered_set<int> s2;
int s[N],ans[N];
struct ask{
    int l,r,id,mod;
}q[N];
inline int cmp(const ask & a,const ask & b){
    return bel[a.l]^bel[b.l] ? bel[a.l]<bel[b.l] : bel[a.l]&1 ? a.r<b.r : a.r>b.r;
}
inline void add(int x){
    if(cnt[x]) {
        s[cnt[x]]-=x;
        if(!s[cnt[x]]) s2.erase(cnt[x]);
    }
    cnt[x]++;
    if(!s[cnt[x]]) s2.insert(cnt[x]);
    s[cnt[x]]+=x;
}
inline void del(int x){
    s[cnt[x]]-=x;
    if(!s[cnt[x]]) s2.erase(cnt[x]);
    cnt[x]--;
    if(cnt[x]){
        if(!s[cnt[x]]) s2.insert(cnt[x]);
        s[cnt[x]]+=x;
    }
}
int pw1[N],pw2[N];
inline ll qpow(int x,int mod){
    return 1ll*pw1[x%block]*pw2[x/block]%mod;
}
inline int calc(int x){
    reg int ans=0;
    for(auto it:s2){
        ans=(ans+s[it]*(qpow(q[x].r-q[x].l+1,q[x].mod)-qpow(q[x].r-q[x].l+1-it,q[x].mod)+q[x].mod)%q[x].mod)%q[x].mod;
    }
    return ans;
}
int main(){
    n=read(),m=read();
    for(reg int i=1;i<=n;i++) a[i]=read();
    for(reg int i=1;i<=n;i++) bel[i]=(i-1)/block+1;
    for(reg int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].mod=read(),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    reg int l=1,r=0;
    for(reg int i=1;i<=m;i++){
        for(;r<q[i].r;r++) add(a[r+1]);
        for(;r>q[i].r;r--) del(a[r]);
        for(;l<q[i].l;l++) del(a[l]);
        for(;l>q[i].l;l--) add(a[l-1]);
        pw1[0]=pw2[0]=1;
        for(reg int j=1;j<=block;j++) pw1[j]=1ll*pw1[j-1]*2%q[i].mod;
        pw2[1]=pw1[block];
        for(reg int j=2;j<=block;j++) pw2[j]=1ll*pw2[j-1]*pw2[1]%q[i].mod;
        ans[q[i].id]=calc(i);
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
} 




发表评论

电子邮件地址不会被公开。 必填项已用*标注