[luoguP2801] 教主的魔法（二分 + 分块）

传送门

以为对于这类问题线段树都能解决，分块比线段树菜，结果培训完才知道线段树是一种特殊的分块方法，有的分块的题线段树不能做，看来分块还是有必要学的。

对于这个题，先分块，然后另开一个数组对于每个块内排序。

区间加的话，加一个标记，每一个整块区间加，里面的数的相对大小不变，而左右两边零散的块直接暴力重构。

查询可以对于每个块二分查找。

时间复杂度应该是 nlogn + Q√nlog√n，刚好卡过。。

注意：第10个点会被卡，手写二分比stl的lower_bound快一点，可以避免被卡。

　　　也可以在 S = sqrt(n) 后面 + x，x 不要太大也不要太小，不知道为什么，速度也会快点，玄学啊。

%%%有些dalao不知道怎么写的，1000ms

——代码（最终只能优化到1600ms）

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 #define LL long long 6 7 const int MAXN = 1000001; 8 int n, q, S, C; 9 int belong[MAXN], st[MAXN], ed[MAXN]; 10 LL a[MAXN], b[MAXN], add[MAXN]; 11 12 inline LL read() 13 20 21 inline int find(int x, int y, int z) 22 30 return x; 31 } 32 33 inline void retreat(int x, int y) 34 39 40 inline void init() 41 50 for(i = 1; i <= C; i++) 51 for(j = st[i]; j <= ed[i]; j++) 52 belong[j] = i; 53 for(i = 1; i <= C; i++) retreat(st[i], ed[i]); 54 } 55 56 inline void update(int x, int y, LL z) 57 64 else 65 72 } 73 74 inline int query(int x, int y, LL z) 75 83 84 int main() 85 101 return 0; 102 }
View Code

上一篇：[HDU1576] A/B（扩展欧几里得）

下一篇：[luoguP1266] 速度限制（spfa）

---

二分 分块