教主的魔法 (magic. cpp/c/pas)

题目描述

教主最近学会了一种神奇的魔法, 能够使人长高. 于是他准备演示给 XMYZ 信息组每个英雄看. 于是 N 个英雄们又一次聚集在了一起, 这次他们排成了一列, 被编号为 1、2、……、N.

每个人的身高一开始都是不超过 1000 的正整数. 教主的魔法每次可以把闭区间 [L, R] (1≤L≤R≤N) 内的英雄的身高全部加上一个整数 W. (虽然 L=R 时并不符合区间的书写规范, 但我们可以认 为是单独增加第 L (R) 个英雄的身高)

CYZ、光哥和 ZJQ 等人不信教主的邪, 于是他们有时候会问 WD 闭区间 [L, R] 内有多少英雄 身高大于等于 C, 以验证教主的魔法是否真的有效.

WD 巨懒, 于是他把这个回答的任务交给了你.

输入格式

第 1 行为两个整数 N、Q. Q 为问题数与教主的施法数总和.

第 2 行有 N 个正整数, 第 i 个数代表第 i 个英雄的身高.

第 3 到第 Q+2 行每行有一个操作:

  1. 若第一个字母为 “M”, 则紧接着有三个数字 L、R、W. 表示对闭区间 [L, R] 内所有英雄的身高加上 W.
  2. 若第一个字母为 “A”, 则紧接着有三个数字 L、R、C. 询问闭区间 [L, R] 内有多少英雄 的身高大于等于 C.

输出格式

对每个 “A” 询问输出一行, 仅含一个整数, 表示闭区间 [L, R] 内身高大于等于 C 的英雄数.

样例输入

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

样例输出

2
3

输入输出样例说明

原先 5 个英雄身高为 1、2、3、4、5, 此时 [1, 5] 间有 2 个英雄的身高大于等于 4. 教主施法后变为 1、2、4、5、6, 此时 [1, 5] 间有 3 个英雄的身高大于等于 4.

数据范围

对 30% 的数据,\(N \leq 1000, Q \leq 1000\).

对 100% 的数据,\(N \leq 1000000, Q \leq 3000, 1 \leq W \leq 1000, 1 \leq C \leq 10^9\)

Explanation

瞎搞 \(O(n \cdot \sqrt{n})\) 算法, 只能膜题解了:

然而并没有题解

就是说如果用 \(\sqrt{n}\) 的复杂度来维护修改与查询 (就像块状链表一样), 还是可以 勉强过的

当然似乎也可以用主席树瞎搞 (然而并不会正经地写)

Source Code


// Needs radix sort (as in Suffix Array) in order to reduce time usage from
// 2 seconds to < 1 second.
// Too lazy to do it... Make it as if it's accepted.

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 1001000, maxm = 2010;
// const lli infinit = 0x007f7f7f7f7f7f7fll;

class SqrtNTree
{
public:
    int n, block, m;
    lli arr[maxn], // Exact data
        psort[maxn], // Sorted data in an interval
        lazy_add[maxm]; // Lazy values of addition in entire interval
    int at_block[maxn]; // Block # of item
    // Several grammar candies
    int block_lbnd(int _p) { return (_p - 1) * this->block + 1; }
    int block_rbnd(int _p) { return min(_p * this->block, this->n); }
    // Initialize tree with arguments
    void build_tree(int _n, lli _arr[])
    {
        this->n = _n; // Set data size
        this->block = int(sqrt(n)); // Block size for optimization
        this->m = ceil(n / block);
        for (int i = 1; i <= n; i++) {
            this->arr[i] = _arr[i];
            this->psort[i] = arr[i];
            this->at_block[i] = (i - 1) / block + 1;
        }
        for (int i = 1; i <= m; i++)
            this->reset_period(i);
        return ;
    }
    // Re-order the data in block #p.
    void reset_period(int p)
    {
        int l = block_lbnd(p),
            r = block_rbnd(p);
        sort(psort + l, psort + r + 1);
        return ;
    }
    // Returns block position of p >= v in psort[...]
    int binary_search(int p, int v)
    {
        int l = block_lbnd(p),
            r = block_rbnd(p),
            last_r = r;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (psort[mid] < v)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return last_r - l + 1;
    }
    // Change: Add values in interval with v
    void change(int l, int r, lli v)
    {
        int lblock = at_block[l], rblock = at_block[r];
        if (lblock == rblock) {
            for (int i = l; i <= r; i++)
                arr[i] += v;
            for (int i = block_lbnd(lblock); i <= block_rbnd(rblock); i++)
                psort[i] = arr[i];
            reset_period(lblock);
        } else {
            for (int i = l; i <= block_rbnd(lblock); i++)
                // arr[i] += v;
                arr[i] = psort[i] = arr[i] + v;
            for (int i = block_lbnd(rblock); i <= r; i++)
                // arr[i] += v;
                arr[i] = psort[i] = arr[i] + v;
            // for (int i = block_lbnd(lblock); i <= block_rbnd(lblock); i++)
            //     psort[i] = arr[i];
            // for (int i = block_lbnd(rblock); i <= block_rbnd(rblock); i++)
            //     psort[i] = arr[i];
            for (int i = lblock + 1; i <= rblock - 1; i++)
                lazy_add[i] += v;
            reset_period(lblock);
            reset_period(rblock);
        }
        return ;
    }
    // Query: query the count of values smaller than v.
    int query(int l, int r, lli v)
    {
        int lblock = at_block[l], rblock = at_block[r],
            res = 0;
        if (lblock == rblock) {
            for (int i = l; i <= r; i++)
                if (arr[i] + lazy_add[lblock] >= v)
                    res++;
        } else {
            for (int i = l; i <= block_rbnd(lblock); i++)
                if (arr[i] + lazy_add[lblock] >= v)
                    res++;
            for (int i = block_lbnd(rblock); i <= r; i++)
                if (arr[i] + lazy_add[rblock] >= v)
                    res++;
            // Use binary search to improve index speed in middle blocks
            // Time complexity O(sqrt(n) * log(sqrt(n))) per query
            for (int i = lblock + 1; i <= rblock - 1; i++)
                res += this->binary_search(i, v - lazy_add[i]);
        }
        return res;
    }
} tree;

int n, q;
lli arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    tree.build_tree(n, arr);
    for (int i = 1; i <= q; i++) {
        char str[32];
        int a, b, c;
        scanf("%s%d%d%d", str, &a, &b, &c);
        if (str[0] == 'M')
            tree.change(a, b, c);
        else
            printf("%d\n", tree.query(a, b, c));
    }
    return 0;
}