Problem A. Ascending Rating

PS：怎么没想到从后往前做呢。。。紫书上做过类似的题，滑动窗口。如果当前元素比栈顶元素大，则不断弹出栈顶元素直到栈顶元素比当前元素小，然后把当前元素压入栈中。如果当前元素比栈顶元素小，则直接入栈。如果当前栈中有元素不再当前区间中，则不断弹出栈底元素。每段区间最大值就是栈底元素，递增个数就是栈的大小。

代码1

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<stack>
#define ll long long
#define P pair<int, int>
#define PP pair<int,pair<int, int>>
#define pb push_back
#define pp pop_back
#define lson root << 1
#define INF (int)2e9 + 7
#define rson root << 1 | 1
#define LINF (unsigned long long int)1e18
#define mem(arry, in) memset(arry, in, sizeof(arry))
using namespace std;

const int N = 1e7 + 5;

int T, n, m, k, p, q, r, mod;
int a[N], b[N];

ll res, ans;

void solve() {
    int l = 0, r = 0;
    for(int i = n; i >= 1; i--) {
        while(r > l && a[b[r - 1]] <= a[i]) r--;
        b[r++] = i;
        if(i > n - m + 1) continue;
        while(r > l && b[l] > i + m - 1) l++;
        res += (r - l) ^ i;
        ans += a[b[l]] ^ i;
    }
}


int main()
{
    scanf("%d", &T);
    while(T--) {
       res = ans = 0;
       b[0] = 0;
       scanf("%d %d %d %d %d %d %d", &n, &m, &k, &p, &q, &r, &mod);
       for(int i = 1; i <= n; i++) {
            b[i] = 0;
            if(i <= k) scanf("%d", &a[i]);
            else a[i] = ((ll)p * a[i - 1] + (ll)q * i  + r ) % mod;
       }
       solve();
       printf("%lld %lld
", ans, res);
    }

    return 0;
}

代码2

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<stack>
#define ll long long
#define P pair<int, int>
#define PP pair<int,pair<int, int>>
#define pb push_back
#define pp pop_back
#define lson root << 1
#define INF (int)2e9 + 7
#define rson root << 1 | 1
#define LINF (unsigned long long int)1e18
#define mem(arry, in) memset(arry, in, sizeof(arry))
using namespace std;

const int N = 1e7 + 5;

int T, n, m, k, p, q, r, mod;
int a[N], b[N], c[N];

int main()
{
    scanf("%d", &T);
    while(T--) {

       c[0] = b[0] = 0;
       scanf("%d %d %d %d %d %d %d", &n, &m, &k, &p, &q, &r, &mod);
       for(int i = 1; i <= n; i++) {
            c[i] = b[i] = 0;
            if(i <= k) scanf("%d", &a[i]);
            else a[i] = ((ll)p * a[i - 1] + (ll)q * i  + r ) % mod;
       }

        ll l = 0, r = 0, tot = 0, tp = n, cont = 0, cnt = 0;
        ll res = 0;

        b[0] = c[0] = 0;
        for(int i = n; i >= 1; i--) {
            tot++;
            if(i == n) {
                c[r] = i;
                b[r++] = a[i];
                if(m == 1) {
                    cnt++;
                    res = b[l] ^ (tp - m + 1);
                    cont = (r - l) ^ (tp - m + 1);
                    tp--;
                }
                continue;
            }
            if(tot > m) {
                tot--;
                while(r > l && c[l] >= n - cnt + 1) l++;
            }
            if(a[i] < b[r - 1] || r == l) {
                c[r] = i;
                b[r++] = a[i];
            }
            else {
                while(r > l && b[r - 1] <= a[i]) r--;
                c[r] = i;
                b[r++] = a[i];
            }
            if(tot == m) {
                res += b[l] ^ (tp - m + 1);
                cont += (r - l) ^ (tp - m + 1);
                cnt++;
                tp--;
            }

        }
        printf("%lld %lld
", res, cont);
    }
    return 0;
}