get到了这题树状数组的做法,感觉非常nice
区间加:直接差分
区间求和:考虑每一位的贡献
$sum_{i = 1}^x (x+1 - i) d_i$
$= sum_{i = 1}^x (x+1)d_i - \sum_{i = 1}^x id_i$
$= (x+1) sum_{i = 1}^x d_i - \sum_{i = 1}^x id_i$
#include<bits/stdc++.h> #define lb(x) (x & (-x)) #define ll long long #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? eof : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf; char obuf[1<<24], *o = obuf; void print(ll x) {if(x > 9) print(x / 10); *o++ = x % 10 + '0';} #define os *o++ = '\n'; #define fout fwrite(obuf, o-obuf, 1 , stdout); using namespace std; const int maxn = 1e5 + 10; inline ll read() { char c = getchar(); ll x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m; ll a[maxn], t1[maxn], t2[maxn]; void insert(ll *t, int pos, ll val) { while(pos <= n) t[pos] += val, pos += lb(pos); } ll sum(ll *t, int pos) { ll ans = 0; while(pos) ans += t[pos], pos -= lb(pos); return ans; } ll query(int pos) { return 1ll * (pos + 1) * sum(t1, pos) - sum(t2, pos); } main() { n = read(); m = read(); for(int i = 1; i <= n; i++) a[i] = read(), insert(t1, i, a[i] - a[i - 1]), insert(t2, i, 1ll * i * (a[i] - a[i - 1])); while(m--) { int opt = read(), l = read(), r = read(); if(opt == 1) { ll val = read(); insert(t1, l, val); insert(t1, r + 1, -val); insert(t2, l, 1ll * l * val); insert(t2, r + 1, 1ll * -(r + 1) * val); } else print(query(r) - query(l - 1)), os; } fout; } /* */
如对本文有疑问, 点击进行留言回复!!
clion+vs编译器+Qt5中使用QPrinter和QprintDialog类
基于open62541在QT编写OPCUA特定的客户端程序(含有源码) + VS2015 C语言搭建OPCUA客户端环境
网友评论