2018 Multi-University Training Contest 3 A题. Ascending Rating（单调队列）

题目大意，就是给你一个序列，在序列中对于每一个长度为m的区间，求区间最大和 每次递增的取区间内数的个数，然后求一个 最大值与i的异或和 和个数与i的异或和

题目分析，我们倒过来用一个递减的单调队列，那么队列中的数，很显然就是正的时候我们需要的递增的数，队列长度即为cnt，队首元素即为最大值，每次当队首的位置不在区间，就出队，维护一个单调队列即可

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
int T;
typedef long long ll;
int n,m,k,p,q,r,mod;
const int maxn=1e7+50;
int a[maxn];
//int que[maxn];
struct node
{
    int id;
    int num;
}que[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {

        scanf("%d%d%d%d%d%d%d",&n,&m,&k,&p,&q,&r,&mod);
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=k+1;i<=n;i++)
        {
             a[i]=((ll)p*a[i-1]%mod+(ll)q*i%mod+r)%mod;
        }
        ll pre=1,cnt=1;
        ll ax=0,bx=0;
        for(int i=n;i>=1;i--)
        {

            while(a[i]>=que[cnt-1].num&&cnt>pre)
            {
                cnt--;
            }
            node tmp;
            tmp.id=i;
            tmp.num=a[i];
            que[cnt++]=tmp;
            if(i<=n-m+1) {
            ax = ax+(que[pre].num^i);
            bx = bx +((cnt-pre)^i);

            }
            if(i<=n-m+1&&cnt!=pre){
                int p =i+m-1;
                if(que[pre].id==p)pre++;
            }
        }
        printf("%lld %lld\n",ax,bx);
    }
    return 0;
}