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

传送门

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

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

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

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

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

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

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

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

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

 #include <cmath>

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 const int MAXN = ;

 int n, q, S, C;

 int belong[MAXN], st[MAXN], ed[MAXN];

 LL a[MAXN], b[MAXN], add[MAXN];

 inline LL read()

 {

     LL x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = x *  + ch - '';

     return x * f;

 }

 inline int find(int x, int y, int z)

 {

     int mid;

     while(x < y)

     {

         mid = (x + y) >> ;

         if(b[mid] >= z) y = mid;

         else x = mid + ;

     }

     return x;

 }

 inline void retreat(int x, int y)

 {

     int i;

     for(i = x; i <= y; i++) b[i] = a[i];

     std::sort(b + x, b + y + );

 }

 inline void init()

 {

     int i, j;

     S = int(sqrt(n)) + ;

     for(i = ; i <= n; i++) scanf("%d", &a[i]);

     for(i = ; i <= n; i += S)

     {

         st[++C] = i;

         ed[C] = std::min(i + S - , n);

     }

     for(i = ; i <= C; i++)

         for(j = st[i]; j <= ed[i]; j++)

             belong[j] = i;

     for(i = ; i <= C; i++) retreat(st[i], ed[i]);

 }

 inline void update(int x, int y, LL z)

 {

     int i, l = belong[x], r = belong[y];

     if(l == r)

     {

         for(i = x; i <= y; i++) a[i] += z;

         retreat(st[l], ed[r]);

     }

     else

     {

         for(i = x; i <= ed[l]; i++) a[i] += z;

         for(i = l + ; i <= r - ; i++) add[i] += z;

         for(i = st[r]; i <= y; i++) a[i] += z;

         retreat(st[l], ed[l]);

         retreat(st[r], ed[r]);

     }

 }

 inline int query(int x, int y, LL z)

 {

     int i, l = belong[x], r = belong[y], ans = ;

     if(l == r) return y +  - find(x, y + , z - add[l]);

     ans += ed[l] - find(x, ed[l] + , z - add[l]) + ;

     for(i = l + ; i <= r - ; i++) ans += ed[i] - find(st[i], ed[i] + , z - add[i]) + ;

     ans += y - find(st[r], y + , z - add[r]) + ;

     return ans;

 }

 int main()

 {

     int i, j, x, y;

     LL z;

     char ch;

     n = read();

     q = read();

     init();

     for(i = ; i <= q; i++)

     {

         while ((ch=getchar()) < 'A' || ch > 'Z');

         x = read();

         y = read();

         z = read();

         if(ch == 'M') update(x, y, z);

         else printf("%d\n", query(x, y, z));

     }

     return ;

 }