动态往序列末尾加数字，每次添加完求序列内所有子区间的RMQ(最小值)之和，强制在线求法，求线性做法。
1.考虑某位置上的数x作为区间最小值出现的次数，一旦插入了一个比x大的数，x的贡献就不再变化。
2.当插入一个数时，只有从末尾往前单调递增的数的贡献才会变化，容易想到用一个单调栈维护。
首先，如果这个数已经被弹出栈了，那么不需要考虑；
而对于栈内的数字，假设它的下标为xi?，而它下面的一个数的下标为x i -1，那么根据单调栈的性质，在xi - x i -1中不存在比当前数更小的数，因此每次新加入一个数时
以[xi - 1, xi ]中任意一个数为区间起点，都可以以新数为区间终点构成新的区间，因此它的贡献值会增加。
struct ST { ll val; int idx; }; ST st[10000005]; int n; ll x, y, z, p, b; ll res, pre; int main() { n = readint(); p = readll(); x = readll(); y = readll(); z = readll(); b = readll(); ll now = 0; int top = 0; for (int i = 1; i <= n; i++) { while (top > 0 && b < st[top].val) { pre = (pre - st[top].val * (st[top].idx - st[top - 1].idx) % MOD + MOD) % MOD; top--; } now += b * (i - st[top].idx) % MOD + pre, now %= MOD; res ^= now; pre += b * (i - st[top].idx) % MOD; pre %= MOD; st[++top].val = b; st[top].idx = i; b = (x * now + y * b + z) % p; } Put(res); }
暑期训练1 Gym - 102623G Gentle Jena 单调栈
原文：https://www.cnblogs.com/hznumqf/p/13531599.html