发布于2018年8月21日 由itewqq[单调队列][思维][精度][坑] HDU6319 Problem A. Ascending Rating 一开始脑子里总是想今天听讲时候的set，可是怎么也想不出来这个怎么用set做。然后又以为必须离线因为1e7 ,可是后来发现给了500mb内存。。。就愉快的离线了。离线的话可以从后往前单调队列。坑点一个是运算中间结果long long，另外一个是我自己手残，单调队列的尾指针用了r，和参数r重合然后把他覆盖了。。。。这是最傻的一次错误了吧。。。 //#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #define eps (1e-6) using namespace std; typedef long long LL; const int maxn=5e6+2e5+5; //const int MOD=1e9+7; const int INF=0x4f4f4f4f; const int maxnode=6e6+5; int val[10000005]; int que[10000005],l,r; int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int T,k,p,q,R,MOD,tmp; LL A,B; int n,m; scanf("%d",&T); while(T--) { A=B=0; scanf("%d%d%d%d%d%d%d",&n,&m,&k,&p,&q,&R,&MOD); l=r=n+3; for (int i=1; i<=k; i++) { scanf("%d",&val[i]); //read(val[i]); } for (LL i=k+1; i<=n; i++) { val[i]=(1LL*p*val[i-1]+q*i+R)%MOD; } for (LL i=n;i>=n-m+1;i--) { while(l=val[que[l]])l++; que[--l]=i; } A+=val[que[r-1]]^(n-m+1); B+=(r-l)^(n-m+1); for (LL i=n-m;i>=1;i--) { if(l=val[que[l]])l++; que[--l]=i;//forget TAT A+=val[que[r-1]]^i; B+=(r-l)^i; } printf("%lld %lld\n",A,B); } return 0; }
