欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 6356(线段树)

程序员文章站 2022-06-09 19:37:56
...

传送门

题面:

Glad You Came

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 829    Accepted Submission(s): 299

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.

HDU 6356(线段树)
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

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.

题目描述:

    给你一个长度为n的最开始为0的数以及m个更新操作以及数据生成器参数X,Y,Z。每次操作,将由数据生成器生成出li,ri,vi。让你从区间[li,ri]中,将所有小于vi的数变为vi。最后让你求从1到n的 i*ai的亦或和。

题目分析:

    对于这个题,我们需要发现,倘若在某个区间[l,r]中,如果这个区间中的最小的数都大于v,那么我们就不需要对这个区间进行任何操作(因为在这段区间一定不用进行操作);而倘若在这个区间中的最大值都小于v,那么证明整个区间的值全都要改变成v。因此,我们考虑用线段树对区间内的最大值以及最小值同时进行维护。

    倘若我们发现一个区间[l,r]的Amax<v,则我们用一个lazy标记标记,使得整个区间的最大值以及最小值同时更新为v,而倘若我们发现一个区间内的Amin>v,则我们直接return掉这个结果。而当我们经过到叶子结点的时候,则我们将叶子结点的最大值和最小值分别更新为。Amax=max(Amax,v),Amin=max(Amin,v)。

    最后我们只需要暴力的获取每一位的置即可。

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
ll a[maxn];
int n,m;
ll ans=0;
struct Tree{
     int minn,maxx;
    int lz;
}tr[maxn<<2];
unsigned int X,Y,Z;
unsigned int functions(){
    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 push_up(int rt){
    tr[rt].maxx=max(tr[rt<<1].maxx,tr[rt<<1|1].maxx);
    tr[rt].minn=min(tr[rt<<1].minn,tr[rt<<1|1].minn);
}
void build(int l,int  r,int rt){
    tr[rt].lz=-1;
    if(l==r){
        //tr[rt].sum=0;
        tr[rt].maxx=0;
        tr[rt].minn=0;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    push_up(rt);
}
void push_down(int rt){
    if(tr[rt].lz!=-1){
        tr[rt<<1].maxx=max(tr[rt].lz,tr[rt<<1].maxx);
        tr[rt<<1|1].maxx=max(tr[rt].lz,tr[rt<<1|1].maxx);
        tr[rt<<1].minn=max(tr[rt].lz,tr[rt<<1].minn);
        tr[rt<<1|1].minn=max(tr[rt].lz,tr[rt<<1|1].minn);
        tr[rt<<1].lz=max(tr[rt].lz,tr[rt<<1].lz);
        tr[rt<<1|1].lz=max(tr[rt].lz,tr[rt<<1|1].lz);
        tr[rt].lz=-1;
    }
}
void update(int L,int R,int l,int r,int rt,int v){
    if(l==r){//到达叶子节点
        tr[rt].minn=max(v,tr[rt].minn);
        tr[rt].maxx=max(v,tr[rt].maxx);
        return ;
    }
    if(L<=l&&R>=r){
        if(tr[rt].maxx<=v){//如果最大值还比v小,则更新整段区间
            tr[rt].maxx=v;
            tr[rt].minn=v;
            tr[rt].lz=max(tr[rt].lz,v);
            return;
        }
        if(tr[rt].minn>=v) return;
    }
    if(tr[rt].minn>=v) return;
    push_down(rt);
    int mid=(l+r)>>1;
    if(L<=mid) update(L,R,l,mid,rt<<1,v);
    if(R>mid) update(L,R,mid+1,r,rt<<1|1,v);
    push_up(rt);
}
int sum(int l,int r,int rt,int pos){//暴力求值
    if (l==r){
         return tr[rt].minn;
    }
    int mid=(l+r)>>1;
    push_down(rt);
    if(pos<=mid) return sum(l,mid,rt<<1,pos);
    else return sum(mid+1,r,rt<<1|1,pos);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%d%d%u%u%u",&n,&m,&X,&Y,&Z);
        build(1,n,1);
        for(int i=1;i<=m;i++){
            int l=functions()%n+1;
            int r=functions()%n+1;
            int v=functions()%(1<<30);
            if(l>r) swap(l,r);
            update(l,r,1,n,1,v);
        }
        for(int i=1;i<=n;i++){
            ans^=1ll*i*sum(1,n,1,i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}