[HDU]Glad You Came【ST表】

>link

>Description

一个长度为 n n n，初始全部值都为 0 的数组
给出 m m m 次操作，每次操作把 [ l , r ] [l,r] [l,r] 内所有小于 x x x 的数修改成 x x x
求出最终的数组

n ≤ 5 ∗ 1 0 5 , m ≤ 5 ∗ 1 0 7 nle 5*10^5,mle5*10^7 n≤5∗105,m≤5∗107

>解题思路

看到 m m m 的大小， O ( m l o g n ) O(mlogn) O(mlogn)是会TLE的
用ST表，把每次修改的区间 [ l , r ] [l,r] [l,r] 分成两个ST表上的区间（这两个区间可以重叠），在上边标记一下，这样修改为 O ( 1 ) O(1) O(1)
最后我们再把每个标记往下传，记录最大值（根据题意，每个点上的值为所有修改的最大值）
时间复杂度 O ( m + n l o g n ) O(m+nlogn) O(m+nlogn)

>代码

#include 
#include 
#include 
#include 
#define N 500010
#define rg register
typedef unsigned int uint;
using namespace std;

int n, m, st[N][30], lg[N], p[N], l, r, x, ll, g, ii;
uint X, Y, Z, W, K;

inline int read ()
{
	int ret = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9')
	{
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret;
}
inline void write (int x)
{
	if (x < 10) {putchar (x + '0'); return;}
	write (x / 10);
	putchar (x % 10 + '0');
}
inline uint READ()
{
    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()
{
//	freopen ("check.out", "w", stdout);
	n = read(), m = read();
	X = read(), Y = read(), Z = read(), K = read();
	p[0] = 1;
	for (rg int i = 1; i <= 20; i++) p[i] = p[i - 1] * 2;
    for (rg int i = 1; i <= n; i++)
	  lg[i] = lg[i - 1] + (p[lg[i - 1]] == i);
    for (rg int i = 1; i <= n; i++) lg[i]--;
	for (rg int i = 1; i <= m; i++)
	{
        l = READ() % n + 1, r = READ() % n + 1, x = READ() % K;
        if (l > r)
        {
        	l = l ^ r;
        	r = l ^ r;
        	l = l ^ r;
		}
		g = lg[r - l + 1];
		st[l][g] = max (st[l][g], x);
		ll = r - p[g] + 1;
		st[ll][g] = max (st[ll][g], x);
    }
    for (rg int j = lg[n]; j >= 1; j--)
      for (rg int i = 1; i <= n - p[j] + 1; i++)
      {
		if (!st[i][j]) continue;
		st[i][j - 1] = max (st[i][j - 1], st[i][j]);
		ii = i + p[j - 1];
		st[ii][j - 1] = max (st[ii][j - 1], st[i][j]);
	  }
    for (rg int i = 1; i <= n; i++)
      write (st[i][0]), putchar (' ');
    return 0;
}