Glad You Came hdu 6356 —— 线段树区间更新+剪枝

本文主要是介绍Glad You Came hdu 6356 —— 线段树区间更新+剪枝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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<vi (j=li,li+1,⋯,ri),$ where
这里写图片描述

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

没什么好说的，就搞一个最小值然后加一个重要的剪枝，在update里面如果这个区间的最小值已经比加的值大了，就return

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int mod=(1<<30);
const int maxn=100005;
typedef unsigned ll;
ll f[15000000], x,y,z;
int n,m;
unsigned rng()
{unsigned t;x^=x<<11;x^=x>>4;x^=x<<5;x^=x>>14;t=x;x=y;y=z;z=x^y^t;return z;
}
struct node{int minn,lazy;
}e[maxn<<2];
void pushdown(int rt){if(e[rt].lazy){if(e[lson].lazy<e[rt].lazy)e[lson].lazy=e[rt].lazy;if( e[rson].lazy<e[rt].lazy)e[rson].lazy=e[rt].lazy;if( e[lson].minn<e[rt].lazy)e[lson].minn=e[rt].lazy;if( e[rson].minn<e[rt].lazy)e[rson].minn=e[rt].lazy;e[rt].lazy=0;}
}
void update(int nowl,int nowr,int l,int r,int rt,ll aim){if(e[rt].minn>=aim)return ;if(nowl>=l&&nowr<=r){if(e[rt].minn>=aim){return ;}else{e[rt].minn=aim;e[rt].lazy=aim;return ;}}pushdown(rt);int mid=(nowl+nowr)/2;if(mid>=l) update(nowl,mid,l,r,lson,aim);if(mid<r) update(mid+1,nowr,l,r,rson,aim);e[rt].minn=min(e[lson].minn,e[rson].minn);
}
ll query(int nowl,int nowr,int l,int r,int rt){if(nowl>=l&&nowr<=r){return e[rt].minn;}pushdown(rt);int mid=(nowl+nowr)/2;if(mid>=l) return query(nowl,mid,l,r,lson);if(mid<r) return query(mid+1,nowr,l,r,rson);
}
int main(){int t;cin>>t;while(t--){scanf("%d%d%u%u%u",&n,&m,&x,&y,&z);memset(e,0,sizeof(e));for(int i=1;i<=3*m;i++)f[i]=rng();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 aim=f[3*i]%mod;update(1,n,l,r,1,aim);}unsigned long long ans=0;for(int i=1;i<=n;i++){unsigned long long nows=query(1,n,i,i,1);ans^=(i*nows);}cout<<ans<<endl;}
}