BZOJ 3922 Karin的彈幕 線段樹

BZOJ 3922 Karin的彈幕 線段樹

題目大意

給出一個序列，支持單點修改，每次查詢一個位置成等差數列中所有數的最大值。

思路

等差數列如果公差很大的話，那麼整個數列中的數並不會很多；但是如果公差很小，我們就可以用線段樹來亂搞。具體方法是對於每個公差維護一個線段樹，按照對這個公差取模的值來進行劃分。這樣詢問的時候就在一塊了。
具體看代碼。

CODE

#define _CRT_SECURE_NO_WARNINGS

#include 
#include 
#include 
#include 
#define MAX 70010
#define INF 0x3f3f3f3f
using namespace std;
#define LEFT (pos << 1)
#define RIGHT (pos << 1|1)

int cnt, asks;
int src[MAX];

int tree[55][MAX << 2];
int shine[55][MAX];
int _src[55][MAX];
int _end[55][55];

void BuildTree(int tree[], int src[], int l, int r, int pos)
{
    if(l == r) {
        tree[pos] = src[l];
        return ;
    }
    int mid = (l + r) >> 1;
    BuildTree(tree, src, l, mid, LEFT);
    BuildTree(tree, src, mid + 1, r, RIGHT);
    tree[pos] = max(tree[LEFT], tree[RIGHT]);
}

void Modify(int tree[], int l, int r, int x, int c, int pos)
{
    if(l == r) {
        tree[pos] += c;
        return ;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)    Modify(tree, l, mid, x, c, LEFT);
    else    Modify(tree, mid + 1, r, x, c, RIGHT);
    tree[pos] = max(tree[LEFT], tree[RIGHT]);
}

int Ask(int tree[], int l, int r, int x, int y, int pos)
{
    if(l == x && y == r)
        return tree[pos];
    int mid = (l + r) >> 1;
    if(y <= mid)    return Ask(tree, l, mid, x, y, LEFT);
    if(x > mid)     return Ask(tree, mid + 1, r, x, y, RIGHT);
    int left = Ask(tree, l, mid, x, mid, LEFT);
    int right = Ask(tree, mid + 1, r, mid + 1, y, RIGHT);
    return max(left, right);
}

int main()
{
    cin >> cnt;
    for(int i = 1; i <= cnt; ++i)
        scanf("%d", &src[i]);
    int range = min(4, cnt);
    for(int i = 1; i <= range; ++i) {
        int now = 0;
        for(int j = 1; j <= i; ++j) {
            for(int k = j; k <= cnt; k += i) {
                shine[i][k] = ++now;
                _src[i][now] = src[k];
            }
            _end[i][j] = now;
        }
        BuildTree(tree[i], _src[i], 1, cnt, 1);
    }
    cin >> asks;
    for(int flag, x, y, i = 1; i <= asks; ++i) {
        scanf("%d%d%d", &flag, &x, &y);
        if(!flag) {
            src[x] += y;
            for(int j = 1; j <= range; ++j)
                Modify(tree[j], 1, cnt, shine[j][x], y, 1);
        }
        else {
            if(y <= range)
                printf("%d\n", Ask(tree[y], 1, cnt, shine[y][x], _end[y][x % y ? x % y:y], 1));
            else {
                int ans = -INF;
                for(int j = x; j <= cnt; j += y)
                    ans = max(ans, src[j]);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

不知道為什麼，如果把_end數組的第二維開成MAX就會RE。
哪位神犇知道告訴我一下啊。。。