题意：

给出一个序列，从左往右每次选择一个长度为m的区间，对于每个区间，找出它的最大值max和从左往右扫描该区间时最大值的变化次数cnt。

思路：

max用单调队列维护是常规操作。但是cnt要怎么在O(n)的复杂度内统计呢？

倒着单调队列就可以了。

比如样例3 2 2 1 5 7 6 8 2 9，先把(9,9)放入队尾，因为2比9小，继续吧(2,8)放入队尾，(8,7)比(2,8)更优，这时候应该把(2,8)弹掉，因为要求的是最大值变化的次数，所以最大值能改变的时候一定要改变，所以8比2大，而且8在2的前面，肯定是最优的，这样子下去，每个区间的最大值的变化次数就是单调队列的元素个数。

这里用deque来写会TLE 所以还是手写个双端队列吧。

这样想想的确是很有道理，但是做题的时候怎么就想不到呢QAQ这问题到底是出在哪里呢QAQ难受啊QAQ

以后碰到题目不仅正着想想 倒着也想想吧。

update：还是思考了一下 倒着做是有道理的 因为常规的单调队列是越后面的越优 而这道题目是越前面的越优 只要数字变大了 就一定要选 这就是越前面越优 所以要倒着做。

代码：

typedef long long ll;
struct node
{
    int id;
    ll val;
};
ll a[10000010];
node qq[10000010];
int main()
{
    int t,n,m,k;
    ll p,q,r,MOD;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%lld%lld%lld%lld",&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]=((p*a[i-1])%MOD+(q*i)%MOD+r)%MOD;
        //for(int i=1;i<=n;i++)
            //printf("%lld ",a[i]);
        //printf("\n");
        //deque<node>q;
        int Front=0,Back=0;
        ll ans1=0,ans2=0;
        for(int i=n;i>=1;i--)
        {
            node temp;
            temp.id=i;temp.val=a[i];
            while(Front!=Back&&a[i]>=qq[Back].val)
                Back--;
            //while(!q.empty()&&a[i]>=q.back().val)
                //q.pop_back();
            qq[++Back]=temp;
            //q.push_back(temp);
            //while(!q.empty()&&q.front().id>i+m-1)
                    //q.pop_front();
            while(Front!=Back&&qq[Front+1].id>i+m-1)
                Front++;
            if(i<=n-m+1)
            {
                //printf("%d:%d ",i,q.front().val);
                //printf("%d\n",q.size());
                //ans2+=q.size()^i;
                ans2+=(Back-Front)^i;
                //ans1+=q.front().val^i;
                ans1+=qq[Front+1].val^i;
            }
        }
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}