题目:http://acm.hdu.edu.cn/showproblem.php?pid=6319
题意:t个测试,第二行六个参数,第三行是k个元素从a[1]到a[k],一共有n个元素,不足的用给出的公式补齐。
要你输出从i=1开始,对于长度为m的区间,假设有number个。
要求求出这个区间最大值,以及从左向右扫描最大值变化的次数,注意遇到第一个数就算变化一次。
再把这number个数异或输出。
题解:逆向构造单调队列,从i+m-1<=n开始记录,此时若正向求是最后一个,逆向是第一个。
队列里的元素存储的是比当前大的,
这样的话,队首元素就是最大值,队列长度就是变化次数(因为每次逆向开始构造,存储的数比当前的数大,顺着看就是遇到了一个比当前数大的元素,变化次数就加一)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=10000005;
int a[maxn],Q[maxn];
int n,m,k,p,q,r,mod;
int head,tail;
ll res1,res2;
int main()
{
int t;
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]=(1ll*p*a[i-1]+1ll*q*i+r)%mod;
}
head=1; tail=0;
res1=res2=0;
for(int i=n;i>0;i--)
{
while(tail>=head&&a[Q[tail]]<=a[i])tail--;
Q[++tail]=i;
if(i+m-1<=n)
{
while(Q[head]>=i+m)head++;
res1+=i^a[Q[head]];
res2+=i^(tail-head+1);
}
}
printf("%lld %lld\n",res1,res2);
}
return 0;
}