[单调队列][思维][精度][坑] 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;
}


发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据