2018HDU多校3-Problem A. Ascending Rating(hdu 6319)-单调队列

题意：

给定一个长度为n的序列，给出前k个值，后面根据公式自己算。现在问你每个区间长度为m的子序列最大值异或上i和最大值变化次数异或上i的求和。

思路：

有些时候若正向考虑不行，就尝试反向考虑，此题应将数列反向存入单调队列中，反向维护递减队列，即是正向的递增。
这样，队列中元素的个数就是所求的count值，队首元素即是最大值

代码：

#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long LL;
const int N=1e7+10;
int a[N];
int qu[N];         //单调队列
int n,m,k,p,q,r,mod;
LL sum,ans;
void getans()
{
    int head,rear;
    head=rear=0;
    for(int i=n;i>=1;i--)
    {
        while(rear>head && a[qu[rear-1]]<=a[i])
            rear--;
        qu[rear++]=i;
        if(i>n-m+1) continue;
        while(qu[head]>i+m-1) head++;
        ans+=(rear-head)^i;
        sum+=a[qu[head]]^i;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        sum=ans=0;
        cin>>n>>m>>k>>p>>q>>r>>mod;
        for(int i=1;i<=k;i++)
            cin>>a[i];
        for(int i=k+1;i<=n;i++)
            a[i]=((LL)p*a[i-1]%mod+(LL)q*i%mod+r%mod)%mod;
        getans();
        cout<<sum<<" "<<ans<<endl;
    }
    return 0;
}