HDU 6356 Glad You Came 线段树或反向RMQ 2018杭电多校第五场

Glad You Came

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

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

⎧⎩⎨⎪⎪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个操作， 这m个操作每个操作是将l到r区间中小于v的数变成v，最终操作结束后给出i * a[i] 的xor和

 

思路：

看着这个题的第一反应就是线段树， 但是这个操作实在是太多了， 高达5e7的操作， 配合上1e6的序列， 这样最坏的复杂度就是大约全跑下来是1e9， 显然是不太够的， 但是我们可以稍微的加一下剪枝呀， 我们的线段树肯定是要维护最小值的嘛， 然后我们在更新l到r这个区间时， 并不是一直往下更新知道这个区间正好等于l到r， 而是再更新的过程中如果发现当前区间的最小值大于等于我们要更新的值了， 我们就直接return， 这样下来， 我们其实是可以减去很多答案的， 再加上给出的5s时限我们可以很优秀的解决， 我的代码实际跑是2300ms

 

当然我们还有另外一种做法， 就是反向rmq做法， 我们知道rmq求的是i到i的2^j - 1这个区间范围内的最大或最小值， 那么我们每次更新l到r区间时我们就参照rmq的更新方式， 只不过我们要更新这个区间包含的两个小区间dp[l][k]和dp[r - (1 << k) + 1][k]， 这个更新是0（1）的， 在所有更新完成后， 我们只需要跑一边n*log(n)的rmq处理， 也是从大的更新小的， 这样我们就可以得到最终的值了

 

线段树代码：

#include <iostream>
#include <cstdio>

const int maxed = 100000 + 10;
typedef unsigned int ll;

struct Node
{
    int l, r;
    int val, lazy;
}node[maxed * 4];

int n, m;
ll w, x, y, z;

int main()
{
    void RNG();
    void bulid(int l, int r, int cur);
    void updata(int l, int r, int val, int cur);
    int query(int x, int cur);
    int N;
    scanf("%d", &N);
    while (N--) {
        scanf("%d%d%u%u%u", &n, &m, &x, &y, &z);
        bulid(1, n, 1);
        int l, r;
        ll v;
        while (m--) {
            RNG();
            l = z % n + 1;
            RNG();
            r = std::max((int)(z % n) + 1, l);
            l = std::min(l, (int)(z % n) + 1);
            RNG();
            //std::cout << l << "=====" << r << "=====" << z % (1LL << 30) << std::endl;
            updata(l, r, z % (1 << 30), 1);
        }
        long long int answer = 0;
        for (int i = 1; i <= n; ++i)
            answer ^= 1LL * query(i, 1) * i;
        std::cout << answer << std::endl;
    }
    return 0;
}

void RNG()
{
    x = x ^ (x << 11), x = x ^ (x >> 4);
    x = x ^ (x << 5), x = x ^ (x >> 14);
    w = x ^ (y ^ z), x = y;
    y = z, z = w;
}

void push_down(int cur)
{
    if (node[cur].lazy) {
        if (node[cur<<1].val < node[cur].lazy) {
            node[cur<<1].val = node[cur].lazy;
            node[cur<<1].lazy = std::max(node[cur<<1].lazy, node[cur].lazy);
        }

        if (node[cur<<1|1].val < node[cur].lazy) {
            node[cur<<1|1].val = node[cur].lazy;
            node[cur<<1|1].lazy = std::max(node[cur<<1|1].lazy, node[cur].lazy);
        }

        node[cur].lazy = 0;
    }
}

void bulid(int l, int r, int cur)
{
    node[cur].l = l;
    node[cur].r = r;
    node[cur].val = 0;
    node[cur].lazy = 0;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    bulid(l, mid, cur << 1);
    bulid(mid + 1, r, cur << 1 | 1);
}

void updata(int l, int r, int val, int cur)
{
    if (node[cur].val >= val)
        return;
    if (l == node[cur].l && r == node[cur].r) {
        if (node[cur].val < val) {
            node[cur].val = val;
            node[cur].lazy = std::max(node[cur].lazy, val);
        }
        return;
    }
    push_down(cur);
    int mid = (node[cur].l + node[cur].r) >> 1;
    if (r <= mid)
        updata(l, r, val, cur << 1);
    else if (l > mid)
        updata(l, r, val, cur << 1 | 1);
    else {
        updata(l, mid, val, cur << 1);
        updata(mid + 1, r, val, cur << 1 | 1);
    }
    node[cur].val = std::min(node[cur<<1].val, node[cur<<1|1].val);
}

int query(int x, int cur)
{
    if (node[cur].l == node[cur].r)
        return node[cur].val;
    push_down(cur);
    int mid = (node[cur].l + node[cur].r) >> 1;
    if (x <= mid)
        return query(x, cur << 1);
    return query(x, cur << 1 | 1);
}

 

反向rmq代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

const int maxed = 100000 + 10;
typedef unsigned int ll;

int n, m;
ll x, y, z, w, dp[maxed][20];

int main()
{
    void fuc();
    void updata(int l, int r, unsigned val);
    int N;
    scanf("%d", &N);
    while (N--) {
        scanf("%d%d%u%u%u", &n, &m, &x, &y, &z);
        memset(dp, 0, sizeof(dp));
        int l, r;
        while (m--) {
            fuc();
            l = z % n + 1;
            fuc();
            r = std::max(l, (int)(z % n + 1));
            l = std::min(l, (int)(z % n + 1));
            fuc();
            updata(l, r, z % (1 << 30));
        }
        for (int j = log2(n); j >= 1; --j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                dp[i][j - 1] = std::max(dp[i][j - 1], dp[i][j]);
                dp[i + (1 << (j - 1))][j - 1] = std::max(dp[i + (1 << (j - 1))][j - 1], dp[i][j]);
            }
        long long int answer = 0;
        for (int i = 1; i <= n; ++i)
            answer ^= 1LL * i * dp[i][0];
        std::cout << answer << std::endl;
    }
    return 0;
}

void fuc()
{
    x = x ^ (x << 11);
    x = x ^ (x >> 4);
    x = x ^ (x << 5);
    x = x ^ (x >> 14);
    w = x ^ (y ^ z);
    x = y;
    y = z;
    z = w;
}

void updata(int l, int r, unsigned val)
{
    int k = 0;
    while ((1 << (k + 1)) <= r - l + 1)
        k += 1;
    dp[l][k] = std::max(val, dp[l][k]);
    dp[r - (1 << k) + 1][k] = std::max(dp[r - (1 << k) + 1][k], val);
}