题目:
链接 https://loj.ac/problem/6277
题解:
给每个块设置一个加法标记 (就是记录这个块中元素一起加了多少), 每次操作对每个整块直接 O(1) 标记, 而不完整的块由于元素比较少, 暴力修改元素的值.
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #define N 50005
- using namespace std;
- struct Block {int l, r, tag;} block[N];
- int n, size, num;
- int a[N], bel[N];
- int read()
- {
- int x = 0, f = 1; char c = getchar();
- while(c <'0' || c> '9') c = getchar();
- while(c>= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
- return x;
- }
- void build()
- {
- size = (int)sqrt(n), num = n / size;
- if(n % size != 0) num++;
- for(int i = 1; i <= num; i++)
- block[i].l = (i - 1) * size + 1,
- block[i].r = i * size;
- for(int i = 1; i <= num; i++)
- for(int j = block[i].l; j <= block[i].r; j++)
- bel[j] = i;
- }
- void update(int l, int r, int w)
- {
- if(bel[l] == bel[r])
- {
- for(int i = l; i <= r; i++) a[i] += w;
- return;
- }
- for(int i = l; i <= block[bel[l]].r; i++) a[i] += w;
- for(int i = r; i>= block[bel[r]].l; i--) a[i] += w;
- for(int i = bel[l] + 1; i <= bel[r] - 1; i++) block[i].tag += w;
- }
- int ask(int pos) {
- return a[pos] + block[bel[pos]].tag;
- }
- int main()
- {
- cin>> n;
- for(int i = 1; i <= n; i++) a[i] = read();
- build();
- for(int i = 1; i <= n; i++)
- {
- int op = read(), l = read(), r = read(), w = read();
- if(!op) update(l, r, w);
- else if(op == 1) printf("%d\n", ask(r));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3133701.html