7.数列分块入门 7

😊 | Powered By HeartFireY | 分块例题

#6283. 数列分块入门 7 - 题目 - LibreOJ (loj.ac)

给出一个长为n的数列，以及 n n n个操作，操作涉及区间乘法，区间加法，单点询问。

我们需要维护两个 t a g tag tag来表示块内元素的整体性操作。但首先考虑算术运算优先级：乘法>加法。

• 那么我们在进行非完整块维护的时候，需要首先对 l l l和 r r r所在的非完整区间进行乘法、加法两个标记的下放，对标记进行下放后再暴力更新。
• 对于完整块，直接更新标记。但是注意乘法标记更新时需要同时更新两个标记。

查询单点查询，直接查到元素后 ( a [ p o s ] + t a g _ a d d ) ∗ t a g _ m u l (a[pos] +tag\_add) * tag\_mul (a[pos]+tag_add)∗tag_mul即可。

#include 
#define ll long long
using namespace std;

const int N = 2e5 + 10, MOD = 10007;
int id[N], tag_add[N], tag_mul[N], blo;
ll a[N];

inline void push_down(int pos){
    for(int i = (id[pos] - 1) * blo + 1; i > c;
        if(op == 0) add(l, r, c);
        if(op == 1) mul(l, r, c);
        if(op == 2) cout