G. Gentle Jena（单调栈） 2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

题意：
给出b[i]的计算公式，第i回合加上b[i]这个数，第i回合的结果为所有区间最小值的和。求所有回合结果的异或值。

思路：
维护一个递增的单调栈，保证弹出的数都比b[i]大，那么这些数在包含b[i]的区间里面都不会被计算到。

单调栈里面维护这个数的值，以这个数为右端点的区间最小值和，下标。

#include <ctime>
#include <iostream>
#include <assert.h>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int mod = 998244353;
const int maxn = 1e7 + 7;
ll b[maxn],ans[maxn];

struct Node {
    ll val,sum;
    int id;
}stk[maxn];

int main() {
    ll n,p,x,y,z;scanf("%lld%lld%lld%lld%lld%lld",&n,&p,&x,&y,&z,&b[1]);
    int top = 1;
    stk[1] = {b[1],b[1],1};
    ll sum = b[1];
    ans[1] = b[1];
    for(int i = 2;i <= n;i++) {
        b[i] = (x * ans[i - 1] % p + y * b[i - 1] % p + z) % p; //递增单调队列
        sum = (sum + b[i]) % p;
        ll tmp = 0;
        int id = 0;
        while(top && stk[top].val > b[i]) {
            top--;
        }
        tmp = stk[top].sum + (i - stk[top].id) * b[i];
        stk[++top] = {b[i],tmp,i};
        ans[i] = (ans[i - 1] + tmp) % mod;
    }
    
    ll res = 0;
    for(int i = 1;i <= n;i++) {
        res = res ^ ans[i];
    }
    printf("%lld\n",res);
    return 0;
}