题意：

有n个数初始都为0，有m次操作，每次操作对于$[l,r]$，如果v大于区间的数，就把这个数变为v，即对区间的每个数取当前值和v的最大值。求这m次操作后的$⨁_{i=1}^n(i⋅a_i)$，$⨁$表示异或和，其中$1≤T≤100, 1≤n≤10^5, 1≤m≤5⋅10^6$。

思路：

因为是区间更新刚开始想到是线段树剪枝啊…然而比赛的时候写gg了…然而想想这复杂度也不可能过啊 是$O(3m+mlogn)$的啊？然而就是很多人是这么过的…这数据有点迷啊？

正解用的是倒着的ST表。

$d[i][j]$：$[i,i+2^j-1]$区间的最大值，即区间长度为$2^j$。

举个栗子，

首先对于一个区间$[5,9]$，可以分成两个区间$[5,8](d[5][2])$和$[6,9](d[6][2])$,给这两个区间打上要取最大值的标记。像这样进行m次操作。

然后对于每一个$d[i][j]$将标记下压，比如$d[6][3]([6,13])$下压给$d[6][2]([6,9])$和$d[10][2]([10,13])$，这样一直压下去，直到区间长度为$2^0$。

最后统计一下要求的东西就好了。

这样的复杂度为$O(m+nlogn)$。

代码：

typedef long long ll;
typedef unsigned int uint;
const uint MOD=1<<30;
ll tot;
uint f[16000010];
ll d[100010][20];
int llog[100010];
uint fx(uint &x,uint &y,uint &z)
{
    x=x^(x<<11);
    x=x^(x>>4);
    x=x^(x<<5);
    x=x^(x>>14);
    uint w=x^(y^z);
    x=y;
    y=z;
    z=w;
    return z;
}
void init()
{
    for(int i=1;i<=1e5;i++)
        llog[i]=(int)log2(i);
}
int main()
{
    int t,n,m;
    uint x,y,z;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%u%u%u",&n,&m,&x,&y,&z);
        for(int i=1;i<=3*m;i++)
            f[i]=fx(x,y,z);
        memset(d,0,sizeof(d));
        for(int i=1;i<=m;i++)
        {
            int l=min(f[3*i-2]%n+1,f[3*i-1]%n+1);
            int r=max(f[3*i-2]%n+1,f[3*i-1]%n+1);
            ll v=f[3*i]%MOD;
            //printf("%d %d %lld\n",l,r,v);
            int temp=llog[r-l+1];
            //printf("%d\n",temp);
            d[l][temp]=max(d[l][temp],v);
            d[r-(1<<temp)+1][temp]=max(d[r-(1<<temp)+1][temp],v);
            //printf("(%d,%d)(%d,%d)\n",l,l+(1<<temp)-1,r-(1<<temp)+1,r);
        }
        for(int i=llog[n];i>=1;i--)
        {
            for(int j=1;j+(1<<i)-1<=n;j++)
            {
                d[j][i-1]=max(d[j][i-1],d[j][i]);
                d[j+(1<<(i-1))][i-1]=max(d[j+(1<<(i-1))][i-1],d[j][i]);
                //注意这里是j+1<<(i-1)，子区间是不重合的区间
            }
        }
        ll tot=0;
        for(int i=1;i<=n;i++)
            tot^=d[i][0]*i;
        printf("%lld\n",tot);
    }
    return 0;
}