Glad You Came (线段树）

Glad You Came (线段树）

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.

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

⎧⎩⎨⎪⎪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

Hint

In the first sample, a = [1031463378] after all the operations. In the second sample, a = [1036205629, 1064909195, 1044643689, 1062944339, 1062944339, 1062944339, 1062944339, 1057472915, 1057472915, 1030626924] after all the operations.

Source

​​2018 Multi-University Training Contest 5​​

题目大概：

给出一个长度为n序列，开始全是0，对这个序列进行区间set，然后把最后数组乘下表的异或输出。

思路：

用线段树，维护最大值和最小值，然后用最大值做lazy标记，用最小值做剪枝。

最后暴力搜索所有值。

实践证明，不用维护最大值，不知道为什么，我把最大值删了，不用进行lazy，比加lazy要快。。。

代码：

加lazy代码

#include #define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int maxn=1e5+10;const int INF=0x3f3f3f3f;const int mod=(1<<30);unsigned x,y,z;unsigned f[15000010];ll min_1[maxn<<2];ll max_1[maxn<<2];ll la[maxn<<2];void pushup(int rt){ max_1[rt]=max(max_1[rt<<1],max_1[rt<<1|1]); min_1[rt]=min(min_1[rt<<1],min_1[rt<<1|1]);}void pushdown(int rt){ if(la[rt]) { max_1[rt<<1]=max_1[rt<<1|1]=la[rt]; min_1[rt<<1]=min_1[rt<<1|1]=la[rt]; la[rt<<1]=la[rt<<1|1]=la[rt]; la[rt]=0; }}void update(int L,int R,ll v,int l,int r,int rt){ if(min_1[rt]>=v)return; if(l==r&&max_1[rt]>v)return; if(L<=l&&r<=R&&max_1[rt]<=v) { max_1[rt]=v; la[rt]=v; return; } pushdown(rt); int m=(l+r)/2; if(m>=L)update(L,R,v,lson); if(m>4); x=x^(x<<5); x=x^(x>>14); unsigned w=x^(y^z); x=y; y=z; z=w; return z;}int main(){ int t; scanf("%d",&t); while(t--) { int n,m; memset(max_1,0,sizeof(max_1)); memset(min_1,0,sizeof(min_1)); memset(la,0,sizeof(la)); scanf("%d%d%d%d%d",&n,&m,&x,&y,&z); for(int i=1;i<=3*m;i++) { f[i]=get(); } 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); int w=f[3*i]%mod; update(l,r,w,1,n,1); } ll sum=0; for(int i=1;i<=n;i++) { ll w=getsum(i,i,1,n,1); //cout<

不加lazy标记代码

#include #define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int maxn=1e5+10;const int INF=0x3f3f3f3f;const int mod=(1<<30);unsigned x,y,z;unsigned f[15000010];ll min_1[maxn<<2];void pushup(int rt){ min_1[rt]=min(min_1[rt<<1],min_1[rt<<1|1]);}void update(int L,int R,ll v,int l,int r,int rt){ if(min_1[rt]>=v)return; if(l==r) { min_1[rt]=v; return; } int m=(l+r)/2; if(m>=L)update(L,R,v,lson); if(m>4); x=x^(x<<5); x=x^(x>>14); unsigned w=x^(y^z); x=y; y=z; z=w; return z;}int main(){ int t; scanf("%d",&t); while(t--) { int n,m; memset(min_1,0,sizeof(min_1)); scanf("%d%d%d%d%d",&n,&m,&x,&y,&z); for(int i=1;i<=3*m;i++) { f[i]=get(); } 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); int w=f[3*i]%mod; update(l,r,w,1,n,1); } ll sum=0; for(int i=1;i<=n;i++) { ll w=getsum(i,i,1,n,1); //cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。