Ascending Rating（思维+单调队列）

Ascending Rating

题意

输入n,m,k,p,q,r,MOD,表示一个长度为n的数列，给你前k个数字，（后面的要根据递推式自己写），然后m表示一个[l,l+m]的区间，从l=1开始，在这个区间中有两个值，一个是MAX，一个是CNT，起始都为0，从区间的第一个数开始扫，如果扫到的数字比MAX大，让MAX=ai，并且CNT++。求的是$A =\sum_{i=1}^{n-m+1}{MAX_i 异或i}$ , $B=\sum_{i=1}^{n-m+1}{CNT_i 异或i}$

思路是用一个单调队列从最后一个区间往前倒着维护，如果队列为空，则直接放入ai，若ai>=队首元素，则将队列中的元素全部弹出，同时将ai放入，若ai小于队首元素，则将队尾中小于ai的元素弹出，将ai放入队尾中，每一个区间的cnt值即为队列中元素的个数，而MAX值则为队首元素。如果队首元素的位置不在下一个区间范围内，则弹出。注意STL的双端队列会被卡，这里可以用数组直接模拟。（可以补一个正向写的，但是我WA到死，主要就是用单调栈来维护每一个数字右边的第一个比他大的位置，最后一个栈里的数的stack设为n+1，然后从右到左，dp[n-1]=1，dp[i]=dp[stack[i]]+1，………然后单调队列维护区间最大值）

看！代码

#include <bits/stdc++.h>
using namespace std;
long long a[10000010];
long long que[20000010];
int main()
{
    int t,n,m,k,p,q,r,MOD;
    int size,front,rear;
    scanf("%d",&t);
    while(t--)
    {
        size=0;
        front=rear=1e7+5;
        scanf("%d%d%d%d%d%d%d",&n,&m,&k,&p,&q,&r,&MOD);
        for(int i=1;i<=k;i++)
            scanf("%lld",&a[i]);
        for(int i=k+1;i<=n;i++)
            a[i]=(1LL*p*a[i-1]+1LL*q*i+r)%MOD;
        long long MAX=0,CNT=0;
        for(int i=n;i>=1;i--)
        {
            if(size==0)
            {
                que[front]=i;size=1;
            }
            else
            {
                if(a[que[front]]<=a[i])
                {
                    front=rear=1e7+5;
                    que[front]=i;
                    size=1;
                }
                else
                {
                    while(size>0&&a[que[rear]]<=a[i])
                        size--,rear--;
                    que[rear+1]=i;rear++;
                    size++;
                }
            }
            if(i<=n-m+1)
            {
                MAX+=a[que[front]]^i;
                CNT+=size^i;
                while(que[front]>=(i+m-1))
                    front++,size--;
            }
        }
        printf("%lld %lld\n",MAX,CNT);
    }
    return 0;
}