Untitled
unknown
c_cpp
a year ago
3.8 kB
6
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