[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 = 1000001;
int n, q, S, C;
int belong[MAXN], st[MAXN], ed[MAXN];
LL a[MAXN], b[MAXN], add[MAXN];

inline LL read()
{
    LL x = 0, f = 1;
    char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return x * f;
}

inline int find(int x, int y, int z)
{
    int mid;
    while(x < y)
    {
        mid = (x + y) >> 1;
        if(b[mid] >= z) y = mid;
        else x = mid + 1;
    }
    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 + 1);
}

inline void init()
{
    int i, j;
    S = int(sqrt(n)) + 10;
    for(i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(i = 1; i <= n; i += S)
    {
        st[++C] = i;
        ed[C] = std::min(i + S - 1, n);
    }
    for(i = 1; i <= C; i++)
        for(j = st[i]; j <= ed[i]; j++)
            belong[j] = i;
    for(i = 1; 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 + 1; i <= r - 1; 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 = 0;
    if(l == r) return y + 1 - find(x, y + 1, z - add[l]);
    ans += ed[l] - find(x, ed[l] + 1, z - add[l]) + 1;
    for(i = l + 1; i <= r - 1; i++) ans += ed[i] - find(st[i], ed[i] + 1, z - add[i]) + 1;
    ans += y - find(st[r], y + 1, z - add[r]) + 1;
    return ans;
}

int main()
{
    int i, j, x, y;
    LL z;
    char ch;
    n = read();
    q = read();
    init();
    for(i = 1; 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 0;
}

?