题意

给定长为$n$的数组，初始值均为0
执行m个操作，每次操作的行为
如原题面

题解

很多人用线段树弄过去了，但是这个非常考验模板的水平，如果常数比较大这个方法就GG了

官方题解的解法说的不是很清楚，而根据官方标程的实现方式，实际上就是一个标准的RMQ逆向的过程。

首先对于RMQ 我们要学习什么是ST表。附录:ST表
然后我们在m次操作中，把一个区间分成两份:
令 $d$ 等于 $\left \lfloor \log_2(r – l + 1) \right \rfloor$，我们可以用两个操作 $(l, l + 2^d – 1, v)$ 和 $(r – 2^d + 1, r, v)$ 替换此操作。正如RMQ查询过程中把一个区间分成两份一样。(详见算法竞赛入门经典–训练指南P198)
求log的操作应该预处理出log表

然后我们反过来把最大值向长度为1的区间进行合并，这个过程是$\mathcal O(nlogn)$的

最后$\mathcal O(n)$扫一遍长度为0的区间即可。
初始化的过程可以在合并区间的过程进行。

这里有一个小小的优化:
v是要对$2^{30}$取模的，我们知道$2^{30}$用二进制表示只有一个1，后面都是0
因此我们可以用位运算代替模运算。
如模运算$8_{10} = 1000_{2}$ 等价于与运算 $7_{10} = 0111_{2}$

AC代码

#pragma GCC optimize("O3")

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <array>

using namespace std;
using ll = long long;
using LL = ll;
using un = unsigned;
const int maxn = 1e5 + 6, maxd = 17;
int T, n, m, mx, Log[maxn], a[maxd][maxn];
un X, Y, Z;

un rng61() {
    X ^= X << 11;
    X ^= X >> 4;
    X ^= X << 5;
    X ^= X >> 14;
    un tmp = X ^Y ^Z;
    X = Y;
    Y = Z;
    Z = tmp;
    return Z;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 2; i < maxn; ++i)
        Log[i] = Log[i >> 1] + 1;
    cin >> T;
    while (T--) {
        cin >> n >> m >> X >> Y >> Z;
        for (mx = 0; 1 << mx <= n; ++mx);
        while (m--) {
            int L = rng61() % n + 1, R = rng61() % n + 1, v = rng61() & ((1 << 30) - 1);
            if (L > R)
                swap(L, R);
            int d = Log[R - L + 1];
            a[d][L] = max(a[d][L], v);
            a[d][R - (1 << d) + 1] = max(a[d][R - (1 << d) + 1], v);
        }
        for (int i = mx - 1; i > 0; --i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
                a[i - 1][j] = max(a[i - 1][j], a[i][j]);
                a[i - 1][j + (1 << (i - 1))] = max(a[i - 1][j + (1 << (i - 1))], a[i][j]);
                a[i][j] = 0;
            }
        LL ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans ^= (LL) i * a[0][i];
            a[0][i] = 0;
        }
        cout << ans << "\n";
    }
}

附线段树的写法 引用自https://blog.csdn.net/f2935552941/article/details/81460692

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int MAX=1e5+10;
const int MOD=1e9+7;
const double PI=acos(-1.0);
typedef long long ll;

ll ans;
struct node
{
    int l,r,mid;    //维护区间最小值
    ll val;
}t[MAX<<2];

unsigned X,Y,Z,W;
unsigned f()
{
    X=X^(X<<11);
    X=X^(X>>4);
    X=X^(X<<5);
    X=X^(X>>14);
    W=X^(Y^Z);
    X=Y;
    Y=Z;
    Z=W;
    return Z;
}
void pushup(int rt)
{
    t[rt].val=min(t[lson].val,t[rson].val);
}
void pushdown(int rt)
{
    if(t[rt].val)
    {
        t[lson].val=max(t[lson].val,t[rt].val); //pushdown要取较大值
        t[rson].val=max(t[rson].val,t[rt].val);
        t[rt].val=0;
    }
}
void build(int l,int r,int rt)
{
    int mid=(l+r)>>1;
    t[rt].l=l,t[rt].r=r,t[rt].mid=mid;
    t[rt].val=0;
    if(l==r)
        return ;
    build(l,mid,lson);
    build(mid+1,r,rson);
    pushup(rt);
}
void update(int l,int r,ll val,int rt)
{
    if(t[rt].val>=val) return ; //这一步的剪枝很关键
    if(l<=t[rt].l&&t[rt].r<=r)
    {
        if(t[rt].val<=val) t[rt].val=val; //符合要求就更新
        return ;
    }
    pushdown(rt);
    if(l<=t[rt].mid) update(l,r,val,lson);
    if(r>t[rt].mid) update(l,r,val,rson);
    pushup(rt);
}
void query(int l,int r,int rt)
{
    if(t[rt].l==t[rt].r)
    {
        ans=ans^(t[rt].val*t[rt].l); //求答案
        return ;
    }
    pushdown(rt);
    query(l,r,lson);
    query(l,r,rson);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        cin>>X>>Y>>Z;
        build(1,n,1);
        int l,r; ll val;
        for(int i=1;i<=m;i++)
        {
            ll x=f();
            ll y=f();
            l=min(x%n+1,y%n+1);
            r=max(x%n+1,y%n+1);
            val=f()%(1<<30);
            update(l,r,val,1);
        }
        ans=0;
        query(1,n,1);
        printf("%lld\n",ans);
    }
    return 0;
}