Advertisement
Saleh127

Light OJ 1183 / Segment Tree Lazy

Nov 16th, 2021
564
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-16-01.14.59
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll tree[400005];
  13. ll lazy[400005];
  14.  
  15. void push_down(ll node,ll b,ll e)
  16. {
  17.     if(lazy[node]==-1) return;
  18.  
  19.     tree[node]=(e-b+1)*lazy[node];
  20.  
  21.     if(b!=e)
  22.     {
  23.         lazy[node*2]=lazy[node];
  24.         lazy[node*2 + 1]=lazy[node];
  25.     }
  26.     lazy[node]=-1;
  27. }
  28.  
  29. void treeconstruct(ll node,ll b,ll e)
  30. {
  31.     if(b==e)
  32.     {
  33.         tree[node]=0;
  34.         return;
  35.     }
  36.     ll left = node*2;
  37.     ll right = node*2 + 1ll;
  38.     ll mid=(b+e)/2;
  39.     treeconstruct(left,b,mid);
  40.     treeconstruct(right,mid+1,e);
  41.     tree[node]=0;
  42.     lazy[node]=(tree[left]+tree[right]);
  43. }
  44.  
  45. void update(ll node,ll b,ll e,ll i,ll j,ll newv)
  46. {
  47.     push_down(node,b,e);
  48.  
  49.     if(i>e || j<b) return;
  50.     if(b>=i && e<=j)
  51.     {
  52.         lazy[node]=newv;
  53.         tree[node]=(e-b+1)*newv;
  54.         push_down(node,b,e);
  55.         return;
  56.     }
  57.  
  58.     ll left = node*2;
  59.     ll right = node*2 + 1ll;
  60.     ll mid=(b+e)/2;
  61.  
  62.     update(left,b,mid,i,j,newv);
  63.     update(right,mid+1,e,i,j,newv);
  64.     tree[node]=(tree[left]+tree[right]);
  65. }
  66.  
  67. ll queries(ll node,ll b,ll e,ll i,ll j)
  68. {
  69.     push_down(node,b,e);
  70.  
  71.     if(i>e || j<b) return 0ll;
  72.     if(b>=i && e<=j) return tree[node];
  73.  
  74.     ll left = node*2;
  75.     ll right = node*2 + 1ll;
  76.     ll mid=(b+e)/2;
  77.  
  78.     ll x=queries(left,b,mid,i,j);
  79.     ll y=queries(right,mid+1,e,i,j);
  80.     return (x+y);
  81. }
  82.  
  83. int main()
  84. {
  85.     ios_base::sync_with_stdio(0);
  86.     cin.tie(0);
  87.     cout.tie(0);
  88.  
  89.     test
  90.     {
  91.         ll q,n,m,i,j,k,l,x,y;
  92.  
  93.         cin>>n>>q;
  94.  
  95.         memset(tree,0,sizeof tree);
  96.         memset(lazy,-1,sizeof lazy);
  97.  
  98.         ///treeconstruct(1ll,1ll,n);
  99.  
  100.         cout<<"Case "<<cs<<":"<<nl;
  101.  
  102.         while(q--)
  103.         {
  104.              cin>>m>>i>>j;
  105.  
  106.              i++,j++;
  107.  
  108.              if(m==1)
  109.              {
  110.                   cin>>k;
  111.                   update(1,1,n,i,j,k);
  112.              }
  113.              else
  114.              {
  115.                   l=queries(1,1,n,i,j);
  116.                   y=(j-i+1);
  117.                   x=__gcd(l,y);
  118.  
  119.                   if(l%y) cout<<l/x<<"/"<<y/x<<nl;
  120.                   else cout<<l/y<<nl;
  121.              }
  122.         }
  123.  
  124.     }
  125.  
  126.     return 0;
  127. }
  128.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement