分块题 求大佬优化

HansLimon @ 2019-10-23 07:16:30

#include <cstdio>
#include <algorithm>

const int N = 1e6 + 7, M = __builtin_sqrt(N) + 7;
int n, q, l, r, w, bef[N];
char opt;
struct readers{
    readers operator >>(int &goal)const {
        goal = 0;
        register char now;
        register bool state = false;
        while (now = getchar(), now < '0' || now > '9')state = now == '-';
        while ('0' <= now && now <= '9'){
            goal = (goal<<1) + (goal<<3) + (now^48);
            now = getchar();
        }
        if (state)goal =-goal;
        return *this;
    }
}reader;
struct blocks{
    int _block, total_block, belong[N], blockary[N], left[M], right[M], lazy[M];
    void build(){
        _block = __builtin_sqrt(n);
        total_block = n/_block + (n%_block?1:0);
        for (register int i = 1;i <= n;i ++)belong[i] = (i - 1)/_block + 1;
        for (register int i = 1;i <= total_block;i ++)left[i] = (i - 1)*_block + 1, right[i] = i*_block;
        right[total_block] = n;
        for (register int i = 1;i <= total_block;i ++)std::sort(blockary + left[i], blockary + right[i] + 1);
    }
    void change(){
        using namespace std;
        if (belong[l] == belong[r]){
            for (register int i = l;i <= r;i ++)bef[i] += w;
            for (register int i = left[belong[l]];i <= right[belong[l]];i ++)blockary[i] = bef[i];
            sort(blockary + left[belong[l]], blockary + right[belong[l]] + 1);
            return;
        }
        for (register int i = l;i <= right[belong[l]];i ++)bef[i] += w;
        for (register int i = left[belong[l]];i <= right[belong[l]];i ++)blockary[i] = bef[i];
        sort(blockary + left[belong[l]], blockary + right[belong[l]] + 1);
        for (register int i = left[belong[r]];i <= r;i ++)bef[i] += w;
        for (register int i = left[belong[r]];i <= right[belong[r]];i ++)blockary[i] = bef[i];
        sort(blockary + left[belong[r]], blockary + right[belong[r]] + 1);
        for (register int i = belong[l] + 1;i < belong[r];i ++)lazy[i] += w;
    }
    int ask(){
        register int ans = 0;
        if (belong[l] == belong[r]){
            for (register int i = l;i <= r;i ++)if (lazy[belong[l]] + bef[i] >= w)ans ++;
            return ans;
        }
        for (register int i = l;i <= right[belong[l]];i ++)if (lazy[belong[l]] + bef[i] >= w)ans ++;
        for (register int i = left[belong[r]];i <= r;i ++)if (lazy[belong[r]] + bef[i] >= w)ans ++;
        for (register int i = belong[l] + 1, _left = left[i], _middle, _right = right[i], sum = 0;i < belong[r];ans += sum, i ++, _left = left[i], _right = right[i], sum = 0)
            while (_left <= _right){
                _middle = (_left + _right)>>1;
                if (blockary[_middle] + lazy[i] >= w){
                    _right = _middle - 1;
                    sum = right[i] - _middle + 1;
                }else _left = _middle + 1;
            }
        return ans;
    }
}block;

int main(){
    freopen("testdata (1) (2).in", "r", stdin);
    freopen("ans.out", "w", stdout);
    reader>>n>>q;
    for (register int i = 1;i <= n;i ++){
        reader>>bef[i];
        block.blockary[i] = bef[i];
    }
    while (q --){
        while (opt = getchar(), opt != 'M' && opt != 'A')continue;
        reader>>l>>r>>w;
        if (opt == 'M')block.change();
        else printf("%d\n", block.ask());
    }
    return 0;
}

by Mystery_Sky @ 2019-10-23 08:00:36

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <cstdio>
#include <algorithm>

const int N = 1e6 + 7, M = __builtin_sqrt(N) + 7;
int n, q, l, r, w, bef[N];
char opt;
struct readers{
    readers operator >>(int &goal)const {
        goal = 0;
        register char now;
        register bool state = false;
        while (now = getchar(), now < '0' || now > '9')state = now == '-';
        while ('0' <= now && now <= '9'){
            goal = (goal<<1) + (goal<<3) + (now^48);
            now = getchar();
        }
        if (state)goal =-goal;
        return *this;
    }
}reader;
struct blocks{
    int _block, total_block, belong[N], blockary[N], left[M], right[M], lazy[M];
    void build(){
        _block = __builtin_sqrt(n);
        total_block = n/_block + (n%_block?1:0);
        for (register int i = 1;i <= n;i ++)belong[i] = (i - 1)/_block + 1;
        for (register int i = 1;i <= total_block;i ++)left[i] = (i - 1)*_block + 1, right[i] = i*_block;
        right[total_block] = n;
        for (register int i = 1;i <= total_block;i ++)std::sort(blockary + left[i], blockary + right[i] + 1);
    }
    void change(){
        using namespace std;
        if (belong[l] == belong[r]){
            for (register int i = l;i <= r;i ++)bef[i] += w;
            for (register int i = left[belong[l]];i <= right[belong[l]];i ++)blockary[i] = bef[i];
            sort(blockary + left[belong[l]], blockary + right[belong[l]] + 1);
            return;
        }
        for (register int i = l;i <= right[belong[l]];i ++)bef[i] += w;
        for (register int i = left[belong[l]];i <= right[belong[l]];i ++)blockary[i] = bef[i];
        sort(blockary + left[belong[l]], blockary + right[belong[l]] + 1);
        for (register int i = left[belong[r]];i <= r;i ++)bef[i] += w;
        for (register int i = left[belong[r]];i <= right[belong[r]];i ++)blockary[i] = bef[i];
        sort(blockary + left[belong[r]], blockary + right[belong[r]] + 1);
        for (register int i = belong[l] + 1;i < belong[r];i ++)lazy[i] += w;
    }
    int ask(){
        register int ans = 0;
        if (belong[l] == belong[r]){
            for (register int i = l;i <= r;i ++)if (lazy[belong[l]] + bef[i] >= w)ans ++;
            return ans;
        }
        for (register int i = l;i <= right[belong[l]];i ++)if (lazy[belong[l]] + bef[i] >= w)ans ++;
        for (register int i = left[belong[r]];i <= r;i ++)if (lazy[belong[r]] + bef[i] >= w)ans ++;
        for (register int i = belong[l] + 1, _left = left[i], _middle, _right = right[i], sum = 0;i < belong[r];ans += sum, i ++, _left = left[i], _right = right[i], sum = 0)
            while (_left <= _right){
                _middle = (_left + _right)>>1;
                if (blockary[_middle] + lazy[i] >= w){
                    _right = _middle - 1;
                    sum = right[i] - _middle + 1;
                }else _left = _middle + 1;
            }
        return ans;
    }
}block;

int main(){
    reader>>n>>q;
    for (register int i = 1;i <= n;i ++){
        reader>>bef[i];
        block.blockary[i] = bef[i];
    }
    while (q --){
        while (opt = getchar(), opt != 'M' && opt != 'A')continue;
        reader>>l>>r>>w;
        if (opt == 'M')block.change();
        else printf("%d\n", block.ask());
    }
    return 0;
}

加上臭氧就过了QWQ

by HansLimon @ 2019-10-23 08:54:15

@Mystery_Sky 谢谢大佬OTZ qwq