【BZOJ 4837】LRU算法

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4837

解题报告

维护一个滑动窗口就可以了
时间复杂度是线性的

Code

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
using namespace std;
  
const int N = 1000009; 
  
int n,m,p,A,B,MOD,cnt[N],x[N],last[N];
ULL ans,pre[N];
  
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
  
int main() {
    for (int i=1;i<N;i++) pre[i] = pre[i-1] + (ULL)i;
    for (int T=read();ans=0,T;T--) {
        memset(cnt,0,sizeof(cnt));
        memset(last,60,sizeof(last));
        n = read(); m = read(); p = read(); 
        A = read(); B = read(); MOD = read();
        for (int i=1;i<=m;i++,p=((LL)A*p+B)%MOD) x[i] = p;
        for (int i=m,cur=0,tl=m,r;i;i--) {
            if (++cnt[x[i]] == 1) ++cur;
            while (cur>n) if (--cnt[x[tl--]] == 0) cur--;
            ans += (ULL)x[i] * (pre[min(last[x[i]], tl)] - pre[i-1]); 
            last[x[i]] = i - 1;
        }
        printf("%llu\n",ans);
    }
    return 0;
}