题目

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6356
一个长度为 \(n\) 的初始全部为 \(0\) 的数列，\(m\) 次操作，第 \(i\) 次操作让 \(l_i\sim r_i\) 中小于 \(v_i\) 的数变成 \(v_i\)。求最终数列。
\(\sum n\leq 10^6,\sum m\leq 5\times 10^7\)。

思路

由于 \(m\) 很大，我们不得不每次操作 \(O(1)\)。由于操作有关区间最大值，考虑用 ST 表维护。
对于一次操作 \(l,r,v\)，我们像一般的 ST 表查询的方法找到能表示出 \([l,r]\) 的两个区间，并将这两个区间的 \(\max\) 与 \(v\) 更新。
然后从大到小枚举区间长度，更新较大区间对其包含的小区间的贡献。然后最终数字 \(i\) 即为 \(st[i][0]\)。
时间复杂度 \(O(T(m+n\log n))\)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;

const int N=100010,LG=20;
int Q,n,m,ql,qr,v,lg[N],st[N][LG+1];
uint X,Y,Z,W;

uint random()
{
	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;
}

int main()
{
	for (int i=2;i<N;i++)
		lg[i]=lg[i>>1]+1;
	scanf("%d",&Q);
	while (Q--)
	{
		scanf("%d%d%u%u%u",&n,&m,&X,&Y,&Z);
		for (int i=1;i<=n;i++)
			for (int j=0;j<=LG;j++)
				st[i][j]=0;
		for (int i=1;i<=m;i++)
		{
			ql=random()%n+1; qr=random()%n+1; v=random()%1073741824;
			if (ql>qr) swap(ql,qr);
			int k=lg[qr-ql+1];
			st[ql][k]=max(st[ql][k],v);
			st[qr-(1<<k)+1][k]=max(st[qr-(1<<k)+1][k],v);
		}
		for (int j=LG-1;j>=0;j--)
			for (int i=1;i<=n;i++)
			{
				st[i][j]=max(st[i][j],st[i][j+1]);
				if (i>(1<<j)) st[i][j]=max(st[i][j],st[i-(1<<j)][j+1]);
			}
		long long ans=0;
		for (int i=1;i<=n;i++)
			ans^=(1LL*i*st[i][0]);
		printf("%lld\n",ans);
	}
	return 0;
}