Paste #BUZ -- näytä pelkkänä tekstinä -- uusi tämän pohjalta
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <iostream> #include <cstdlib> using namespace std; const int n = 1<<18; const int N = 1<<18; int t[2*N]; int lz[2*N]; void lol(int k, int l, int r) { t[k] += lz[k]; if(l < r) { lz[2*k] += lz[k]; lz[2*k+1] += lz[k]; } lz[k] = 0; } int inc(int k, int l, int r, int x, int y, int v) { lol(k, l, r); if(l > y || r < x) { return t[k]; } if(l >= x && r <= y) { lz[k] += v; return lz[k] + t[k]; } int mid = (l+r)>>1; return t[k] = max(inc(k*2, l, mid, x, y, v), inc(k*2+1, mid+1, r, x, y, v)); } int query(int k, int l, int r, int x, int y) { lol(k, l, r); if(l > y || r < x) { return -2e9; } if(l >= x && r <= y) { return t[k]; } int mid = (l+r)>>1; return max(query(k*2, l, mid, x, y), query(k*2+1, mid+1, r, x, y)); } int main() { ios_base::sync_with_stdio(0); for(int i = 0; i < 1e7; ++i) { if(rand()&1) { int q = rand()%n; int w = rand()%n; if(q > w) swap(q, w); int e = rand()%100; inc(1, 0, N-1, q, w, e); } else { int q = rand()%n; int w = rand()%n; if(q > w) swap(q, w); int ans = query(1, 0, N-1, q, w); cout<<ans<<'\n'; } } } |