fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <map>
  7. #include <vector>
  8. #include <list>
  9. #include <string>
  10. #include <set>
  11. #include <queue>
  12.  
  13. #define s(x) scanf("%d",&x)
  14. #define sil(x) scanf("%llu",&x)
  15. #define sd(x) scanf("%ld",&x)
  16.  
  17. #define FOR(i,a,b) for( typeof(a) i=(a); i<(b); ++i)               // exclusive for
  18. #define FORR(i,a,b) for( typeof(a) i=(a-1) ; i>=(b); --i)
  19. #define REP(k,a,b) for(typeof(a) k=(a); k <= (b); ++k)			// inclusive for
  20. #define REPR(i,a,b) for( typeof(a) i=(a) ; i>=(b); --i)
  21. #define ALL(c) (c).begin(), (c).end()  
  22. #define PB push_back 
  23. #define MP make_pair 
  24. #define SZ(x) ((int)((x).size()))
  25. #define SRT(v) std::sort(ALL(v))
  26. #define CTN(x) std::cout<<x<<'\n'								//cout with newline
  27. #define CTS(x) std::cout<<x<<" "                                //cout with space
  28. #define CLR(x) std::memset(x,0,sizeof(x))
  29. #define FILL(x,n) std::fill_n(x,sizeof(x),n)
  30. #define DBGA(x,n) {FOR(i,0,n) cout<<x[i]<<" "; CTN(" ");}
  31. //#define NL printf("\n")
  32.  
  33. typedef std::vector<int> VI;
  34. typedef std::vector<long long int> VL;
  35. typedef std::vector<std::string> VS;
  36. typedef std::map<int,int> MI;
  37. typedef std::pair<int,int> PII;
  38. typedef unsigned long long ull;
  39. typedef long long ll;
  40.  
  41.  
  42. using namespace std;
  43.  
  44.  
  45. struct node{
  46. 	int h;  //number of head
  47. 	int t;  //number of tail
  48. 	int lazy;
  49. 	node()
  50. 	{
  51. 		h=0;
  52. 		t=0;
  53. 		lazy=0;
  54. 	}
  55. }tree[300000];
  56. void build_tree(int n,int a,int b)
  57. {
  58. 	//cout<<"wo"<<endl;
  59. 	if(a>b)
  60. 		return;
  61. 	if(a==b)
  62. 	{
  63. 		tree[n].h=0;
  64. 		tree[n].t=1;
  65. 		//cout<<tree[n]<<" "<<a<<" "<<b<<" "<<n<<endl;
  66. 		return;
  67. 	}
  68. 	build_tree(2*n+1,a,(a+b)/2);
  69. 	build_tree(2*n+2,(a+b)/2+1,b);
  70. 	tree[n].t=tree[2*n+1].t+tree[2*n+2].t;
  71. 	//cout<<tree[n]<<" "<<a<<" "<<b<<" "<<n<<endl;
  72. }
  73. int query(int n,int ql,int qr,int l,int r)
  74. {
  75.  
  76. 	if(tree[n].lazy!=0)
  77. 	{
  78. 		int tmp=tree[n].h;
  79. 		tree[n].h=tree[n].t;
  80. 		tree[n].t=tmp;
  81. 		if(r!=l)
  82. 		{
  83. 			tree[2*n+1].lazy=1;
  84. 			tree[2*n+2].lazy=1;
  85. 		}
  86. 		tree[n].lazy=0;
  87. 	}
  88. 	if(l>qr || r<ql)
  89. 		return 0;
  90. 	if(l>=ql  && r<=qr)
  91. 		return tree[n].h;
  92.  
  93. 		return query(2*n+1,ql,qr,l,(l+r)/2)+query(2*n+2,ql,qr,(l+r)/2+1,r);
  94. }
  95. void update(int n,int ul,int ur,int l,int r)
  96. {
  97. 	if(tree[n].lazy!=0)
  98. 	{
  99. 		int tmp=tree[n].h;
  100. 		tree[n].h=tree[n].t;
  101. 		tree[n].t=tmp;
  102. 		if(r!=l)
  103. 		{
  104. 			tree[2*n+1].lazy=1;
  105. 			tree[2*n+2].lazy=1;
  106. 		}
  107. 		tree[n].lazy=0;
  108. 	}
  109. 	if(l>ur || r<ul)
  110. 		return ;
  111. 	if(l>=ul  && r<=ur)
  112. 		{
  113. 			int tmp=tree[n].h;
  114. 			tree[n].h=tree[n].t;
  115. 			tree[n].t=tmp;
  116. 			if(r!=l)
  117. 			{
  118. 				tree[2*n+1].lazy=1;
  119. 				tree[2*n+2].lazy=1;
  120. 			}
  121. 			return;
  122.  
  123. 		}
  124.  
  125.  
  126. 			update(2*n+1,ul,ur,l,(l+r)/2);
  127. 			update(2*n+2,ul,ur,(l+r)/2+1,r);
  128. 			tree[n].h=tree[2*n+1].h+tree[2*n+2].h;
  129. 			tree[n].t=tree[2*n+1].t+tree[2*n+2].t;
  130.  
  131. }
  132.  
  133.  
  134. int main()
  135. {
  136. 	std::ios_base::sync_with_stdio(false);
  137. 	int n;cin>>n;
  138. 	build_tree(0,0,n-1);
  139. 	int q;cin>>q;
  140. 	while(q--)
  141. 	{
  142. 		int t;cin>>t;int l,r;cin>>l>>r;
  143. 		if(t)
  144. 		{
  145. 			cout<<query(0,l,r,0,n-1)<<'\n';
  146. 		}
  147. 		else
  148. 		{
  149. 			update(0,l,r,0,n-1);
  150. 			/*CTN(" ");
  151. 			FOR(i,0,7)
  152. 				cout<<i<<" "<<tree[i].h<<'\n';
  153. 			CTN(" ");*/
  154.  
  155. 		}
  156. 	}
  157.  
  158.  
  159. }
  160.  
Success #stdin #stdout 0s 6992KB
comments (?)
stdin
copy 
4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3 
1 3 3
stdout
copy 
0
1
0
2
1
https://ideone.com/SHVZ5y
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

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!