Advertisement
chang2394

Untitled

Sep 23rd, 2014
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /* Uzumaki Naruto */
  5. #define TRACE
  6.  
  7. #ifdef TRACE
  8. #define dbgarr(a,n)   cerr << "["; for(LL i = 0; i < n; ++i) cerr << a[i] << " ";cerr << "\b]\n";
  9. #define dbg(args...)  {debug,args; cerr<<endl;}
  10. #define pause()       cin.get();cin.get();
  11.  
  12. #else
  13. #define dbgarr(a,n)
  14. #define dbg(args...)
  15. #define pause()
  16.  
  17. #endif
  18.  
  19. struct debugger {
  20.     template<typename T> debugger& operator , (const T& v) {
  21.         cerr<<v<<" "; return *this;
  22.     }
  23. } debug;
  24.  
  25. template <typename T1, typename T2>
  26. inline ostream& operator << (ostream& os, const pair<T1, T2>& p) {
  27.     return os << "(" << p.first << ", " << p.second << ")";
  28. }
  29.  
  30. template<typename T>
  31. inline ostream &operator << (ostream & os,const vector<T>& v) {
  32.     bool first = true; os << "[";
  33.     for (typename vector<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
  34.         if(!first) os << ", ";
  35.         os << *ii; first = false;
  36.     }
  37.     return os << "]";
  38. }
  39.  
  40. #define fr first
  41. #define se second
  42. typedef long long LL;
  43. typedef pair<LL,LL> pii;
  44. typedef vector<LL> vi;
  45.  
  46. const LL NN = 251234;
  47. LL seg[4*NN], lazy[4*NN];
  48. LL A[4*NN], D[4*NN];
  49. bool up[4*NN];
  50.  
  51. LL sum(LL a,LL d,LL n){
  52.     LL ans = (n*(2LL*a+(n-1)*d))/2LL;
  53.     return ans;
  54. }
  55.  
  56. void push_down(LL node,LL st,LL en){
  57.     if (up[node]){
  58.         seg[node] = (en-st+1)* lazy[node];
  59.         if (st != en){
  60.             lazy[2*node] = lazy[node], lazy[2*node+1] = lazy[node];
  61.             up[2*node] = up[2*node+1] = true;
  62.             A[2*node] = D[2*node] = A[2*node+1] = D[2*node+1] = 0;
  63.         }
  64.         up[node] = false;
  65.     }
  66.  
  67.     if (A[node] != 0 or D[node] != 0){
  68.         seg[node] += sum(A[node],D[node],en-st+1);
  69.         if (st != en){
  70.             LL mid = (st+en)/2;
  71.             A[2*node] += A[node], D[2*node] += D[node];
  72.             A[2*node+1] += (A[node] + (mid+1LL-st)*D[node]), D[2*node+1] += D[node];
  73.         }
  74.         A[node] = D[node] = 0;
  75.     }
  76. }
  77.  
  78. void update_inc(LL node,LL st,LL en,LL L,LL R,LL fr,LL d){
  79.     push_down(node,st,en);
  80.     if (st > en or st > R or en < L) return;
  81.     if (st >= L and en <= R){
  82.         A[node] += fr, D[node] += d;
  83.         push_down(node,st,en);
  84.         return;
  85.     }
  86.  
  87.     LL mid = (st+en)/2;
  88.     update_inc(2*node,st,mid,L,R,fr,d);
  89.     update_inc(2*node+1,mid+1,en,L,R,fr+(mid+1-L)*d,d);
  90.     seg[node] = seg[2*node] + seg[2*node+1];
  91. }
  92.  
  93. void update_set(LL node,LL st,LL en,LL L,LL R,LL x){
  94.     push_down(node,st,en);
  95.     if (st > en or st > R or en < L) return;
  96.     if (st >= L and en <= R){
  97.         A[node] = D[node] = 0;
  98.         lazy[node] = x;
  99.         up[node] = true;
  100.         push_down(node,st,en);
  101.         return;
  102.     }
  103.  
  104.     LL mid = (st+en)/2;
  105.     update_set(2*node,st,mid,L,R,x);
  106.     update_set(2*node+1,mid+1,en,L,R,x);
  107.     seg[node] = seg[2*node] + seg[2*node+1];
  108. }
  109.  
  110. LL query(LL node,LL st,LL en,LL L,LL R){
  111.     push_down(node,st,en);
  112.     if (st > en or st > R or en < L) return 0LL;
  113.     if (st >= L and en <= R) return seg[node];
  114.  
  115.     LL mid = (st+en)/2;
  116.     LL ans = 0;
  117.     ans += query(2*node,st,mid,L,R);
  118.     ans += query(2*node+1,mid+1,en,L,R);
  119.     return ans;
  120. }
  121.  
  122. void solve(){
  123.     LL n,t,st,en;
  124.     LL x;
  125.     cin >> n;
  126.     while(n--){
  127.         cin >> t >> st >> en;
  128.         if (t == 4)
  129.             cout << query(1,0,NN-1,st-1,en-1) << endl;
  130.         else if (t == 3){
  131.             cin >> x;
  132.             update_set(1,0,NN-1,st-1,en-1,x);
  133.         } else if (t == 1)
  134.             update_inc(1,0,NN-1,st-1,en-1,1LL,1LL);
  135.         else {
  136.             update_inc(1,0,NN-1,st-1,en-1,(en-st+1),-1LL);
  137.         }
  138.     }
  139. }
  140.  
  141. int main()
  142. {
  143.     ios_base::sync_with_stdio(0);
  144.     solve();
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement