Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- long long int tree[400001],propagate[400001];
- void lazy(long long int node ,long long int a,long long int b)
- {
- tree[node]=(propagate[node]*(b-a+1));
- if(a!=b)
- {
- propagate[2*node]=propagate[node];
- propagate[(2*node)+1]=propagate[node];
- }
- propagate[node]=-1;
- }
- void update(long long int node,long long int a,long long int b,long long int x,long long int y,long long int value)
- {
- if(propagate[node]!=-1)
- {
- lazy(node,a,b);
- }
- if(b<x||a>y)
- {
- return ;
- }
- if(a>=x&&b<=y)
- {
- tree[node]=value*(b-a+1);
- if(a!=b)
- {
- propagate[2*node]=value;
- propagate[(2*node)+1]=value;
- }
- return;
- }
- long long int mid;
- mid=(a+b)/2;
- update(2*node,a,mid,x,y,value);
- update((2*node)+1,mid+1,b,x,y,value);
- tree[node]=tree[2*node]+tree[(2*node)+1];
- }
- long long int query(long long int node,long long int a,long long int b,long long int x,long long int y)
- {
- if(propagate[node]!=-1)
- {
- lazy(node,a,b);
- }
- if(b<x||a>y)
- {
- return 0;
- }
- if(a>=x&&b<=y)
- {
- return tree[node];
- }
- long long int mid,p1,p2;
- mid=(a+b)/2;
- p1=query(2*node,a,mid,x,y);
- p2=query((2*node)+1,mid+1,b,x,y);
- return p1+p2;
- }
- int main ()
- {
- long long int n,i,a,b,j,k,x,y,z,p,l;
- scanf("%lld",&n);
- for(i=1;i<=n;i++)
- {
- memset(propagate,-1,sizeof(propagate));
- memset(tree,0,sizeof(tree));
- scanf("%lld %lld",&a,&b);
- printf("Case %lld:\n",i);
- for(j=1;j<=b;j++)
- {
- scanf("%lld",&k);
- if(k==1)
- {
- scanf("%lld %lld %lld",&x,&y,&z);
- update(1,1,a,x+1,y+1,z);
- }
- else
- {
- scanf("%lld %lld",&x,&y);
- p=query(1,1,a,x+1,y+1);
- l=__gcd(y-x+1,p);
- if((y-x+1)/l==1)
- {
- printf("%lld\n",p/l);
- }
- else
- {
- printf("%lld/%lld\n",p/l,(y-x+1)/l);
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement