【6319 HDU】Problem A. Ascending Rating（单调队列）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6319

题意：输入T组测试样例，每组测试样例包含7个整数n，m，k，p，q，r，mod，接下来一行输入前k个数，后n-k个数用公式a[ i ] =(p×a[ i−1 ]+q×i+r) mod MOD，输出A和B，其中，，max初始值是-1，count初始值是0，当在任意的连续的m长子区间内遇到比max大的值时，就更新max的值，并且count+1；则，max里面存的是任意连续的m长子区间内的最大值，count是指最大值变化的次数。

思路：这道题用到了单调队列的知识点，单调队列是专业用来求数组中任意子区间内的最大值或最小值。然后这道题唯一的区别是单调队列是从后往前遍历的，如果你从前往后遍历的话，可能你在入队的时候把后一个区间里面的比较重要的数删了，所以为了避免这种情况，就从后往前遍历。

单调队列知识点参考博客：https://blog.csdn.net/qq_41181772/article/details/81364243

My  DaiMa：

#include<bits/stdc++.h>
using namespace std;
const int Max = 10000003;
typedef long long ll;
ll a[Max],v[Max];
int main()
{
    int t;
    ll n,m,k,p,q,r,mod;
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&m,&k,&p,&q,&r,&mod);
        for( ll i = 1; i<= k; i++)
            scanf("%lld",&a[i]);//输入前k个数
        for(ll i = k+1; i <= n; i++)
            a[i] = (p*a[i-1]+q*i+r)%mod;//根据公式计算后n-k个数
        ll ans = 0,cunt = 0;
        ll head = 1,tail = 0;//队列的头和尾，维护队列的队首作为答案
        for( ll i = n; i >= 1; i--)//要求最大值，因此此单调队列是单调递减队列
        {
            while(head <= tail && a[v[tail]] <= a[i]) tail--;//当要入队的那个数比队尾要大时，为了维护这个递减队列，就要把队尾去掉，直到找到比要入队的数小的数时跳出循环，此时就保证了这个队列还是递减队列
            v[++tail] = i;//将这个数入队，放在第一个比他小的数的后面
            if(i+m-1 <= n)
            {
                while(v[head] > i+m-1) head++;//如果队首所代表的下标不在此区间内，就需要让队首+1
                ans += i^a[v[head]];//最大值就是队首
                cunt += i^(tail-head+1);//最大值改变的次数就是队列的个数
            }
        }
        printf("%lld %lld\n",ans,cunt);
    }
}