Luogu3932 - [八连测 R3T1]浮游大陆的68号岛

2017/10/21

题目

辣鸡题面太长了。

给定数轴上的一些点 Xi ,每个点有一个权值 Wi

每次询问 (x, l, r) 要求回答 其中 dis 表示数轴上的距离

点数 n, 询问数 m ≤ 200000
权值和相邻两点距离在 int 范围内。

蒟蒻我的线段树解法

100’

考虑到两个相邻段上的信息满足区间加法,使用线段树维护,开 LL 并且正确取模。

复杂度

40’

(pos[r] - pos[l]) % MOD 写成 (pos[r] - pos[l]),爆 LL 。

其他同学的做法

oscar 爷写了个大力分块卡过去了。

标算

考虑到段上信息不仅满足区间加法,还满足区间减法,用前缀和静态维护。

复杂度

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int SIZ = 8E5 + 1007;
const int MOD = 19260817;

int N, M;
LL sum[SIZ], ll[SIZ], rr[SIZ], l[SIZ], r[SIZ];
LL pos[SIZ], val[SIZ];
int W;

#define lson(x) ((x) << 1)
#define rson(x) (lson(x) | 1)
void up(int x) {
    sum[x] = (sum[lson(x)] + sum[rson(x)]) % MOD;
    ll[x] = (ll[lson(x)] + ll[rson(x)]) % MOD;
    ll[x] = (ll[x] + ((pos[l[rson(x)]] - pos[l[lson(x)]]) % MOD) * sum[rson(x)]) % MOD;
    rr[x] = (rr[lson(x)] + rr[rson(x)]) % MOD;
    rr[x] = (rr[x] + ((pos[r[rson(x)]] - pos[r[lson(x)]]) % MOD) * sum[lson(x)]) % MOD;
}

void mkTree() {
    for(W=1;W<=N;W<<=1);
    // [1, W-1] [W, 2W-1]
    
    for(int i=N+1;i<=W;i++) pos[i] = pos[N];

    for(int i=1;i<=W;i++) {
        sum[W+i-1] = val[i];
        ll[W+i-1] = rr[W+i-1] = 0;
        l[W+i-1] = r[W+i-1] = i;
    }

    for(int i=W-1;i;i--) {
        l[i] = l[lson(i)], r[i] = r[rson(i)];
        up(i);

        //printf("[%lld, %lld], ll = %lld, rr = %lld \n", l[i], r[i], ll[i], rr[i]);
    }
}

struct state {
    LL sum, ll, rr, l, r;
};

state operator+(const state &a, const state &b) {
    state ret;
    ret.l = a.l, ret.r = b.r;
    ret.sum = (a.sum + b.sum) % MOD;
    ret.ll = (a.ll + b.ll) % MOD;
    ret.ll = (ret.ll + ((pos[b.l] - pos[a.l]) % MOD) * b.sum) % MOD;
    ret.rr = (a.rr + b.rr) % MOD;
    ret.rr = (ret.rr + ((pos[b.r] - pos[a.r]) % MOD) * a.sum) % MOD;

    return ret;
}

state query(int Ql, int Qr, int x) {
    int L = l[x], R = r[x];

    if(L == Ql && R == Qr) return state{sum[x], ll[x], rr[x], l[x], r[x]};
    
    int Mid = (L + R) >> 1;

    state ret;
    if(Qr <= Mid) ret = query(Ql, Qr, lson(x));
    else if(Mid < Ql) ret = query(Ql, Qr, rson(x));
    else ret = query(Ql, Mid, lson(x)) + query(Mid+1, Qr, rson(x));

    //printf("Query [%d, %d] on [%lld, %lld], ll = %lld, rr = %lld \n",
    //        Ql, Qr, l[x], r[x], ret.ll, ret.rr);
    
    return ret;
}

int main() {
    scanf("%d %d", &N, &M);

    int x, l, r;
    pos[1] = 0;
    for(int i=2;i<=N;i++) {
        scanf("%d", &x);
        pos[i] = pos[i-1] + x;
    }

    for(int i=1;i<=N;i++)
        scanf("%lld", &val[i]);

    mkTree();

    for(int i=1;i<=N;i++) {
        scanf("%d %d %d", &x, &l, &r);

        LL ans = 0;
        if(x <= l || x >= r) {
            if(x <= l) {
                state s = query(l, r, 1);
                ans = (s.ll + ((pos[s.l] - pos[x]) % MOD) * s.sum) % MOD; 
            } else {
                state s = query(l, r, 1);
                ans = (s.rr + ((pos[x] - pos[s.r]) % MOD) * s.sum) % MOD;
            }
        } else {
            state s1 = query(l, x, 1);
            state s2 = query(x, r, 1);
            ans = (s1.rr + s2.ll) % MOD;
        }

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