HDU 6319 Ascending Rating（单调队列）

题意：

给定长度为 k (k<=n) 的一个序列，可以通过递推式得到整个 a[i] (i = 1...n) 数组。

现在给定一个长度为 m 的窗口，定义count[i] 为区间 a[i]....a[i+m-1] 内上升序列的元素个数，maxrating[i] 为该区间内的最大值

需求得 A , B 的值。

思路：

由于时间的限制，必须要用 O(n) 的做法，但是正向单调队列不好维护 count[i] ，于是用采用逆向的做法，具体思想见代码及注释。

 1 /*
 2 * @Author: WindyStreet
 3 * @Date:   2018-07-31 09:07:27
 4 * @Last Modified by:   WindyStreet
 5 * @Last Modified time: 2018-07-31 10:21:27
 6 */
 7 #include<bits/stdc++.h>
 8 
 9 using namespace std;
10 
11 #define X first
12 #define Y second
13 #define eps  1e-2
14 #define gcd __gcd
15 #define pb push_back
16 #define PI acos(-1.0)
17 #define lowbit(x) (x)&(-x)
18 #define bug printf("!!!!!
");
19 #define mem(x,y) memset(x,y,sizeof(x))
20 
21 typedef long long LL;
22 typedef long double LD;
23 typedef pair<int,int> pii;
24 typedef unsigned long long uLL;
25 
26 const int maxn = 1e7+2;
27 const int INF  = 1<<30;
28 const int mod  = 1e9+7;
29 
30 int a[maxn],q[maxn];  //q数组用来记录当前区间最大值的下标
31 int n,m,k,P,Q,r,MOD;
32 
33 void solve(){
34     scanf("%d%d%d%d%d%d%d",&n,&m,&k,&P,&Q,&r,&MOD);
35     for(int i=1;i<=k;i++)scanf("%d",a+i);
36     for(int i = k+1;i<=n;i++) a[i] = (1LL*P*a[i-1]+1LL*Q*i+r)%MOD;
37     LL A =0, B = 0 ; int x = 1,y = 0;
38     for(int i = n ;i ; i--){
39         while(x <= y && a[q[y]] <= a[i]) y--;   // 若当前a[i]大于队列中的值，则更新单调队列
40         q[++y] = i;                             // 否则直接加在队列后边
41         if(i + m - 1<= n){                      // 当区间长度达到 m 时就可以开始计算
42             while(q[x]>=i+m)x++;                // 若当前最大值的下标大于区间右端点，则向左移
43             A+=i^a[q[x]];                       // 异或当前区间最大值
44             B+=i^(y - x + 1);                   // count[i] 即为当前单调队列的长度
45         }
46     }
47     printf("%lld %lld
", A,B);
48     return;
49 }
50 
51 int main()
52 {
53 //    freopen("in.txt","r",stdin);
54 //    freopen("out.txt","w",stdout);
55 //    ios::sync_with_stdio(false);
56     int t = 1;
57     scanf("%d",&t);
58     while(t--){
59     //    printf("Case %d: ",cas++);
60         solve();
61     }
62     return 0;
63 }

AB==∑i=1n−m+1(maxratingi⊕i)∑i=1n−m+1(counti⊕i)