HDU 6356 Glad You Came (선분 수 구간 업데이트 + 가지치기)

제목: n 길이 의 배열 a 가 있 습 니 다. 초기 값 은 모두 0 이 고 m 조 가 수정 되 었 습 니 다. 제목 에서 준 무 작위 함수 로 l, r, v 를 생 성하 고 a 구간 [l, r] 중 소 v 의 값 을 v 로 수정 하 며 최종 출력 은 10753 ° ni = 1 * 10753 ° i = 1 n ai a i * i (a1 a 1 에서 an a n 까지 차이 점 을 구하 거나 합)
사고방식: 먼저 l r v 를 모두 꺼 내 서 각 구간 a 의 최대 값 과 최소 값 을 유지한다.update 할 때 mina > = v, 업데이트 하지 않 고 return 합 니 다.maxa < = v, 구간 을 직접 업데이트 하고 게 으 름 표 시 를 합 니 다.그렇지 않 으 면 구간 을 계속 분할 하여 아래로 업데이트 합 니 다.

#include
using namespace std;
typedef unsigned int ui;
typedef long long ll;
const int maxn = 1e5 + 5;
const int maxm = 5e6 + 5;
const ui mod = 1 << 30;
ui x, y, z, w, f[3*maxm], Left[maxm], Right[maxm], v[maxm];
ui fun()
{
    x ^= (x << 11);
    x ^= (x >> 4);
    x ^= (x << 5);
    x ^= (x >> 14);
    w = x ^ (y ^ z);
    x = y;
    y = z;
    z = w;
    return z;
}

ll ans, a[maxn], maxa[maxn<<2], mina[maxn<<2], lazy[maxn<<2];
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define getm int m = l + r >> 1
void pushup(int rt)
{
    mina[rt] = min(mina[rt<<1],mina[rt<<1|1]);
    maxa[rt] = max(maxa[rt<<1],maxa[rt<<1|1]);
}

void pushdown(int rt)
{
    if(lazy[rt])
    {
        lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
        maxa[rt<<1] = maxa[rt<<1|1] = lazy[rt];
        mina[rt<<1] = mina[rt<<1|1] = lazy[rt];
        lazy[rt] = 0;
    }
}

void update(ui L,ui R,ui val,int l,int r,int rt)
{
    if(mina[rt] >= val) return ;//     v ，    
    if(L <= l && r <= R)
    {
        if(maxa[rt] <= val)//    v ，    ，   
        {
            maxa[rt] = val;
            lazy[rt] = val;
            return ;
        }
        //        ，    
    }

    getm;
    pushdown(rt);
    if(L<=m)
        update(L,R,val,lson);
    if(R>m)
        update(L,R,val,rson);
    pushup(rt);
}

ll query(int pos,int l,int r,int rt)
{
    if(l==r)
        return maxa[rt];
    getm;
    pushdown(rt);
    if(pos<=m)
        return query(pos,lson);
    else
        return query(pos,rson);
}

int T, N, M;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(a,0,8*(N+1));
        memset(lazy,0,32*(N+1));
        memset(mina,0,32*(N+1));
        memset(maxa,0,32*(N+1));
        scanf("%d%d%u%u%u",&N,&M,&x,&y,&z);
        for(int i=1;i<=3*M;++i)
            f[i] = fun();
        for(int i=1;i<=M;++i)
        {
            Left[i] = min(f[3*i-2] % N, f[3*i-1] % N) + 1;
            Right[i] = max(f[3*i-2] % N, f[3*i-1] % N) + 1;
            v[i] = f[3*i] % mod;
            update(Left[i],Right[i],v[i],1,N,1);
        }
        ans = 0;
        for(int i=1;i<=N;++i)
            ans ^= ((ll)i * query(i,1,N,1));
        printf("%lld
",ans);
    }
    return 0;
}