hdu6354 /// 线段树

题目大意：

给定n m x y z

长度为n的序列初始为0

接下来m个操作 l r v 将l r区间内比v小的数都变成v

l r v由x y z和给定的函数生成

线段树维护区间最大值最小值再加 lazy标记

当v大于某个区间的最大值时整个区间都要变成v 用lazy标记

当v小于某个区间的最小值时整个区间都不需要操作

题解：https://blog.csdn.net/weixin_39453270/article/details/81462219

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LL long long

#define mem(i,j) memset(i,j,sizeof(i))

const int N=1e5+;

const int MOD=1e9+;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define root 1,n,1

int maxi[N<<], mini[N<<], lazy[N<<];

void pushUp(int rt) {

    maxi[rt]=max(maxi[rt<<],maxi[rt<<|]);

    mini[rt]=min(mini[rt<<],mini[rt<<|]);

}

void pushDown(int rt) {

    if(lazy[rt]!=-) {

        mini[rt<<]=max(mini[rt<<],lazy[rt]);

        mini[rt<<|]=max(mini[rt<<|],lazy[rt]);

        maxi[rt<<]=max(maxi[rt<<],lazy[rt]);

        maxi[rt<<|]=max(maxi[rt<<|],lazy[rt]);

        lazy[rt<<]=max(lazy[rt<<],lazy[rt]);

        lazy[rt<<|]=max(lazy[rt<<|],lazy[rt]);

        lazy[rt]=-;

    }

}

void build(int l,int r,int rt) {

    lazy[rt]=-;

    if(l==r) {

        mini[rt]=maxi[rt]=;

        return ;

    }

    int m=(l+r)>>;

    build(lson);

    build(rson);

    pushUp(rt);

}

void update(int L,int R,int v,int l,int r,int rt) {

    if(l==r) {

        mini[rt]=max(mini[rt],v);

        maxi[rt]=max(maxi[rt],v);

        return;

    }

    if(L<=l && r<=R) {

        if(maxi[rt]<=v) {

            maxi[rt]=mini[rt]=v;

            lazy[rt]=max(lazy[rt],v);

            return;

        }

    }

    if(mini[rt]>=v) return;

    pushDown(rt);

    int m=(l+r)>>;

    if(L<=m) update(L,R,v,lson);

    if(m<R) update(L,R,v,rson);

    pushUp(rt);

}

LL query(int pos,int l,int r,int rt) {

    if(l==r) return 1LL*pos*mini[rt];

    pushDown(rt);

    int m=(l+r)>>;

    if(pos<=m) return query(pos,lson);

    else return query(pos,rson);

}

int n, m;

unsigned int x, y, z;

unsigned int RNG61() {

    x=x^(x<<);

    x=x^(x>>);

    x=x^(x<<);

    x=x^(x>>);

    unsigned int w=x^(y^z);

    x=y, y=z, z=w;

    return z;

}

int main()

{

    int t; scanf("%d",&t);

    while(t--) {

        scanf("%d%d%u%u%u",&n,&m,&x,&y,&z);

        build(root);

        for(int i=;i<=m;i++) {

            int l=RNG61()%n+;

            int r=RNG61()%n+;

            int v=RNG61()%(<<);

            if(l>r) swap(l,r);

            update(l,r,v,root);

        }

        LL ans=;

        for(int i=;i<=n;i++)

            ans^=query(i,root);

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

hdu6354 /// 线段树

最新文章

热门文章