fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define MOD (ll) (1e9+7)
  5.  
  6. ll lazy[1000000];
  7. void buildTree(ll *tree,ll ind,ll s,ll e)
  8. {
  9. 	if(s>e)
  10. 		return;
  11. 	if(s==e)
  12. 	{
  13. 		tree[ind] = 0;
  14. 		return;
  15. 	}
  16.  
  17. 	ll mid = (s+e)/2;
  18. 	buildTree(tree,2*ind,s,mid);
  19. 	buildTree(tree,2*ind+1,mid+1,e);
  20.  
  21. 	tree[ind] = 0;
  22. 	return;
  23.  
  24. }
  25.  
  26.  
  27. ll power(ll a,ll p,ll m = MOD)
  28. {
  29. 	ll res=1;
  30. 	while(p>0){
  31. 		if(p&1)
  32. 			res=(res*a)%m;
  33. 		a=(a*a)%m;
  34. 		p>>=1;
  35. 	}
  36. 	return res;
  37. }
  38.  
  39. void lazy_update(ll *t,ll ss,ll se,ll node)
  40. {
  41. 	if(lazy[node]!=-1)
  42. 	{
  43. 		t[node] = (power(2,(se-ss+1),MOD)-1)*lazy[node];
  44. 		if(ss!=se)
  45. 		{
  46. 			lazy[2*node]=lazy[node];
  47. 			lazy[2*node+1]=lazy[node];
  48. 		}
  49. 		lazy[node] = -1;
  50. 	}
  51.  
  52. }
  53.  
  54. void update_range(ll *t,ll ss,ll se,ll l,ll r,ll val,ll node)
  55. {
  56. 	   lazy_update(t,ss,se,node);
  57. 	   if(ss>r || se<l)
  58. 	   {
  59. 	     return;
  60. 	   }
  61. 	   if(ss>=l && se<=r)
  62. 	   {
  63. 	       	t[node] = (power(2,(se-ss+1),MOD)-1)*val;
  64. 	       	if(ss!=se)
  65.         {
  66.             lazy[node*2]=val;
  67.             lazy[node*2+1]=val;
  68.         }
  69.         return;
  70. 	   }
  71. 	   ll mid=ss+se>>1;
  72.     update_range(t,ss,mid,l,r,val,node*2);
  73.     update_range(t,mid+1,se,l,r,val,node*2+1);
  74.     t[node]=(t[node*2]*power(2,se-mid,MOD)%MOD+t[node*2+1])%MOD;
  75. }
  76.  
  77. ll query(ll *t,ll ss,ll se,ll l,ll r,ll node)
  78. {
  79.     lazy_update(t,ss,se,node);
  80. 	   if(ss>r || se<l)
  81. 	   {
  82. 	     return 0;
  83. 	   }
  84. 	   if(ss>=l && se<=r)
  85. 	   {
  86. 	       return t[node];
  87. 	   }
  88. 	   ll mid= (ss+se)/2;
  89.     ll p1 = query(t,ss,mid,l,r,(2*node));
  90.     ll p2 = query(t,mid+1,se,l,r,(2*node)+1);
  91.     return (p1* power(2,min(se,r)-mid,MOD)%MOD+p2)%MOD;
  92. }
  93.  
  94. int main()
  95. {
  96.    ll n,m;
  97.    cin>>n>>m;
  98.    ll t[4*n+2];
  99.    for(int i=0;i<1000000;i++)
  100.    {
  101.       lazy[i] = -1;
  102.    }
  103.    buildTree(t,1,0,n-1);
  104.    while(m--)
  105.    {
  106.         int x,l,r;
  107.         cin>>x>>l>>r;
  108.         if(x == 0 || x==1 )
  109.         {
  110.             update_range(t,0,n-1,l,r,x,1);
  111.         }
  112.         else
  113.         {
  114.             ll ans=query(t,0,n-1,l,r,1);
  115.             cout<<ans<<endl;
  116.         }
  117.     }
  118. }
Success #stdin #stdout 0.01s 11332KB
comments (?)
stdin 
3 6
1 0 1
2 0 2
0 1 1
2 1 1
1 2 2
2 0 2
stdout 
6
0
5
https://ideone.com/51EbAH
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!