Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll mx = 1e5+10;
- ll arr[3*mx], tree[mx * 3], lazy[3*mx] ;
- ll t,n,q;
- void Propagation(ll node,ll b,ll e)
- {
- ll Left = node * 2 ;
- ll Right= node * 2 + 1 ;
- if(b != e)
- {
- lazy[Left] = lazy[Right] = lazy[node];
- }
- tree[node] = lazy[node]*((e - b ) + 1);
- lazy[node] = -1;
- }
- void init(ll node, ll b, ll e)
- {
- if (b == e)
- {
- tree[node] = 0;
- lazy[node] = -1 ;
- return;
- }
- ll Left = node * 2;
- ll Right = node * 2 + 1;
- ll mid = (b + e) / 2;
- init(Left, b, mid);
- init(Right, mid + 1, e);
- }
- ll query(ll node, ll b, ll e, ll i, ll j)
- {
- if(lazy[node]!= -1)
- Propagation(node,b,e);
- if (i > e || j < b || b > e)
- return 0;
- if (b >= i and e <= j)
- {
- return tree[node];
- }
- ll Left = node << 1;
- ll Right = (node << 1) + 1;
- ll mid = (b + e) >> 1;
- ll p1 = query(Left, b, mid, i, j);
- ll p2 = query(Right, mid + 1, e, i, j);
- return p1 + p2;
- }
- void update(ll node, ll b, ll e, ll i, ll j, ll x)
- {
- if(lazy[node]!= -1)
- Propagation(node,b,e);
- if (i > e || j < b)
- return;
- ll Left = node * 2;
- ll Right = (node * 2) + 1;
- ll mid = (b + e) / 2;
- if (b >= i && e <= j)
- {
- tree[node] = ((e - b + 1) * x);
- if(b!=e)
- {
- lazy[Left] = lazy[Right] = x ;
- }
- return;
- }
- update(Left, b, mid, i, j, x);
- update(Right, mid + 1, e, i, j, x);
- tree[node] = tree[Left] + tree[Right] ;
- }
- int main()
- {
- int cas=1;
- scanf("%lld",&t);
- while(t--)
- {
- memset(arr, 0, sizeof arr) ;
- memset(tree,0,sizeof tree) ;
- memset(lazy,-1,sizeof lazy) ;
- scanf("%lld%lld",&n,&q);
- for(int i =1 ; i<= n ; i++)
- {
- arr[i]=0;
- }
- init(1,1,n);
- printf("Case %d:\n",cas++);
- while(q--)
- {
- ll no,i,j,val;
- scanf("%lld",&no);
- if(no == 1)
- {
- scanf("%lld%lld%lld",&i,&j,&val);
- i++,j++;
- update(1,1,n,i,j,val);
- }
- else
- {
- scanf("%lld%lld",&i,&j);
- i++,j++;
- ll res = query(1,1,n,i,j);
- ll num = (j - i + 1);
- ll gcd = __gcd(res,num);
- if( res % num )
- printf("%lld/%lld\n",(res)/gcd, (num) /gcd);
- else
- printf("%lld\n",res/num);
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement