Untitled
unknown
c_cpp
a year ago
3.8 kB
10
Indexable
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define edehaLezar cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define cn(v) for(auto &(i):(v))cin>>(i);
#define pr(v) for(auto (i):(v))cout<<(i)<<' ';
#define tc int tc;cin>>tc;while(tc--)
#define all(x) x.begin(),(x).end()
#define allr(x) x.rbegin(),(x).rend()
#define ll long long
#define ull unsigned long long
#define watch(x) cout<<(#x)<<" = "<<x<<endl;
ll const mod = 1e9 + 7;
ll const MOD = 998244353;
using namespace std;
int dx[8] = {-1, 1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, -1, 1, 1, -1, -1, 1};
int const N = 2e5 + 10;
vector<int> prime(N);
void sieve() {
prime[0] = prime[1] = 1;
for (int i = 2; i < N; i += 2)
prime[i] = 2;
for (int i = 3; i < N; i += 2)
if (!prime[i])
for (int j = i; j < N; j += i)prime[j] = i;
}
ll lcm(ll a, ll b) {
return a / __gcd(a, b) * b;
}
ll fastPower(ll n, ll pow, int m) {
ll res = 1;
while (pow)
if (pow & 1)res *= n, res %= m, --pow;
else n *= n, n %= m, pow >>= 1;
return res;
}
struct item {
ll sum;
};
struct segTree {
int size;
vector<item> sumValue;
item NEUTRAL_ELEMENT = {0};
item merge(item a, item b) {
return {a.sum + b.sum};
}
item single(ll v) {
return {v};
}
void init(int n) {
size = 1;
while (size < n)size <<= 1;
sumValue.resize(2 * size,{0});
}
void build(vector<int> &ref, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < ref.size())
sumValue[x] = single(ref[lx]);
return;
}
int m = lx + rx >> 1;
build(ref, 2 * x + 1, lx, m);
build(ref, 2 * x + 2, m, rx);
sumValue[x] = merge(sumValue[2 * x + 1], sumValue[2 * x + 2]);
}
void build(vector<int> &ref) {
build(ref, 0, 0, size);
}
void set(int i, ll v, int x, int lx, int rx) {
if (rx - lx == 1) {
sumValue[x] = single(v);
return;
}
int m = lx + rx >> 1;
if (i < m) {
set(i, v, 2 * x + 1, lx, m);
} else {
set(i, v, 2 * x + 2, m, rx);
}
sumValue[x] = merge(sumValue[2 * x + 1], sumValue[2 * x + 2]);
}
void set(int i, ll v) {
set(i, v, 0, 0, size);
}
item func(int l, int r, int x, int lx, int rx) {
if (lx >= r || l >= rx)return NEUTRAL_ELEMENT;
if (lx >= l && rx <= r)return sumValue[x];
int m = lx + rx >> 1;
auto p1 = func(l, r, 2 * x + 1, lx, m);
auto p2 = func(l, r, 2 * x + 2, m, rx);
return merge(p1, p2);
}
item func(int l, int r) {
return func(l, r, 0, 0, size);
}
};
int n,m;
void solve() {
cin>>n>>m;
segTree sg;
sg.init(2*n);
vector<ll>sumValues(2*n);
for(int i=0;i<m;++i){
int t;cin>>t;
if(t==1){
int l,r,v;
cin>>l>>r>>v;
sumValues[l]+=v;
sumValues[r]-=v;
sg.set(l,sumValues[l]);
sg.set(r,sumValues[r]);
}
else{
int ind;cin>>ind;
cout<<sg.func(0,ind+1).sum<<'\n';
}
}
}
signed main() {
edehaLezar
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1;
// cin >> t;
for (int i = 1; i <= t; ++i) {
solve();
}
}Editor is loading...
Leave a Comment