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。
哪位神?知道告诉我一下啊。。。

BZOJ 3922 Karin的弹幕 线段树

题目大意

思路

CODE