Glad You Came
Time Limit: 10000/5000 MS (Java/Others)
Problem Description
Steve has an integer array a of length n (1-based). He assigned all the elements as zero at the beginning. After that, he made m operations, each of which is to update an interval of a with some value. You need to figure out ⨁ni=1(i⋅ai) after all his operations are finished, where ⨁ means the bitwise exclusive-OR operator.
In order to avoid huge input data, these operations are encrypted through some particular approach.
There are three unsigned 32-bit integers X,Y and Z which have initial values given by the input. A random number generator function is described as following, where ∧ means the bitwise exclusive-OR operator, << means the bitwise left shift operator and >> means the bitwise right shift operator. Note that function would change the values of X,Y and Z after calling.
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiInBnauETL3ADMx0iMyczQvw1cldWYtl2LcFGdhR2Lc52YuUHZl5SdkhmLtNWYvw1LcpDc0RHaiojIsJye.jpg)
Let the i-th result value of calling the above function as fi (i=1,2,⋯,3m). The i-th operation of Steve is to update aj as vi if aj<vi (j=li,li+1,⋯,ri), where
⎧⎩⎨⎪⎪lirivi=min((f3i−2modn)+1,(f3i−1modn)+1)=max((f3i−2modn)+1,(f3i−1modn)+1)=f3imod230(i=1,2,⋯,m).
Input
The first line contains one integer T, indicating the number of test cases.
Each of the following T lines describes a test case and contains five space-separated integers n,m,X,Y and Z.
1≤T≤100, 1≤n≤105, 1≤m≤5⋅106, 0≤X,Y,Z<230.
It is guaranteed that the sum of n in all the test cases does not exceed 106 and the sum of m in all the test cases does not exceed 5⋅107.
Output
For each test case, output the answer in one line.
Sample Input
4
1 10 100 1000 10000
10 100 1000 10000 100000
100 1000 10000 100000 1000000
1000 10000 100000 1000000 10000000
Sample Output
1031463378
1446334207
351511856
47320301347
題意:給你3*m個數的生成規則,用來生成m個區間和對應的值,将區間内小于此值的改為此值.問最後所有值乘對應位置的異或值.
思路:RMQ思想和ST表,可見另一篇文章https://blog.csdn.net/nka_kun/article/details/81461902
然後就是保留區間最值,然後按照區間從大到小枚舉區間,不斷更新其1/2大小的子區間,直到枚舉的區間長度為1.
代碼:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const unsigned int mod = 1<<30;
const int maxn = 2e5+5;
const double eps = 1e-12;
const int inf = 0x3f3f3f3f;
map<int,int>::iterator it;
int n,m;
int lg[maxn];
unsigned int stmax[maxn][18];
unsigned int x,y,z;
unsigned int rng61()
{
x = x^(x<<11);
x = x^(x>>4);
x = x^(x<<5);
x = x^(x>>14);
unsigned int w = x^(y^z);
x = y;
y = z;
z = w;
return z;
}
void init()
{
lg[0] = -1;
for(int i = 1;i< maxn;i++)
lg[i] = ((i&(i-1)) == 0)?(lg[i-1]+1):lg[i-1];
}
int main()
{
int t;
cin>>t;
init();
while(t--)
{
scanf("%d %d %u %u %u",&n,&m,&x,&y,&z);
for(int i = 1;i<= m;i++)
{
ll f1=rng61();
ll f2=rng61();
unsigned int f3=rng61();
int l=(int)min((f1%n)+1,(f2%n)+1);
int r=(int)max((f1%n)+1,(f2%n)+1);
unsigned int v = f3%mod;
int k = lg[r-l+1];//對應log2的值
stmax[l][k] = max(stmax[l][k],v);
stmax[r-(1<<k)+1][k] = max(stmax[r-(1<<k)+1][k],v);
}
for(int i = lg[n];i>= 1;i--)
{
for(int j = 1;j<= n;j++)
{
stmax[j][i-1] = max(stmax[j][i-1],stmax[j][i]);
stmax[j+(1<<(i-1))][i-1] = max(stmax[j+(1<<(i-1))][i-1],stmax[j][i]);
stmax[j][i] = 0;
}
}
ll ans = 0;
for(ll i = 1;i<= n;i++)
{
ans^= (stmax[i][0]*i);
stmax[i][0] = 0;
}
printf("%lld\n",ans);
}
return 0;
}