fork(1) download
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. long long int s[1000006];
  5. long long int lazy[1000006];
  6. long long int a[100005];
  7. long long int val;
  8. ll int ql;
  9. ll int qr;
  10. ll int ul;
  11. ll int ur;
  12. static struct IO {
  13. char tmp[1 << 10];
  14.  
  15. // fast input routines
  16. char cur;
  17.  
  18. //#define nextChar() (cur = getc_unlocked(stdin))
  19. //#define peekChar() (cur)
  20. inline char nextChar() { return cur = getc_unlocked(stdin); }
  21. inline char peekChar() { return cur; }
  22.  
  23. inline operator bool() { return peekChar(); }
  24. inline static bool isBlank(char c) { return (c < '-' && c); }
  25. inline bool skipBlanks() { while (isBlank(nextChar())); return peekChar() != 0; }
  26.  
  27. inline IO& operator >> (char & c) { c = nextChar(); return *this; }
  28.  
  29. inline IO& operator >> (char * buf) {
  30. if (skipBlanks()) {
  31. if (peekChar()) {
  32. *(buf++) = peekChar();
  33. while (!isBlank(nextChar())) *(buf++) = peekChar();
  34. } *(buf++) = 0; } return *this; }
  35.  
  36. inline IO& operator >> (string & s) {
  37. if (skipBlanks()) { s.clear(); s += peekChar();
  38. while (!isBlank(nextChar())) s += peekChar(); }
  39. return *this; }
  40.  
  41. inline IO& operator >> (double & d) { if ((*this) >> tmp) sscanf(tmp, "%lf", &d); return *this; }
  42.  
  43. #define defineInFor(intType) \
  44. inline IO& operator >>(intType & n) { \
  45. if (skipBlanks()) { \
  46. int sign = +1; \
  47. if (peekChar() == '-') { \
  48. sign = -1; \
  49. n = nextChar() - '0'; \
  50. } else \
  51. n = peekChar() - '0'; \
  52. while (!isBlank(nextChar())) { \
  53. n += n + (n << 3) + peekChar() - 48; \
  54. } \
  55. n *= sign; \
  56. } \
  57. return *this; \
  58. }
  59.  
  60. defineInFor(int)
  61. defineInFor(unsigned int)
  62. defineInFor(long long)
  63.  
  64. // fast output routines
  65.  
  66. //#define putChar(c) putc_unlocked((c), stdout)
  67. inline void putChar(char c) { putc_unlocked(c, stdout); }
  68. inline IO& operator << (char c) { putChar(c); return *this; }
  69. inline IO& operator << (const char * s) { while (*s) putChar(*s++); return *this; }
  70.  
  71. inline IO& operator << (const string & s) { for (int i = 0; i < (int)s.size(); ++i) putChar(s[i]); return *this; }
  72.  
  73. char * toString(double d) { sprintf(tmp, "%lf%c", d, '\0'); return tmp; }
  74. inline IO& operator << (double d) { return (*this) << toString(d); }
  75.  
  76.  
  77. #define defineOutFor(intType) \
  78. inline char * toString(intType n) { \
  79. char * p = (tmp + 30); \
  80. if (n) { \
  81. bool isNeg = 0; \
  82. if (n < 0) isNeg = 1, n = -n; \
  83. while (n) \
  84. *--p = (n % 10) + '0', n /= 10; \
  85. if (isNeg) *--p = '-'; \
  86. } else *--p = '0'; \
  87. return p; \
  88. } \
  89. inline IO& operator << (intType n) { return (*this) << toString(n); }
  90.  
  91. defineOutFor(int)
  92. defineOutFor(long long)
  93.  
  94. #define endl ('\n')
  95. #define cout __io__
  96. #define cin __io__
  97. } __io__;
  98.  
  99. ll int f(long long int x)
  100. {
  101.  
  102. return x && (!(x&(x-1)));
  103. }
  104. ll int build(ll int node,ll int l,ll int r)
  105. {
  106. if(l == r) {
  107. s[node] = a[l];
  108. return s[node];
  109. }
  110. ll int mid = (l + r)/2;
  111. s[node] = build(node*2,l,mid) + build(node*2+1,mid+1,r);
  112. return s[node];
  113.  
  114. }
  115. void update(ll int node,ll int l,ll int r)
  116. {
  117. if(lazy[node] != -1) {
  118. s[node] = (r-l+1)*lazy[node];
  119. if(l != r) {
  120. lazy[node*2] = lazy[node];
  121. lazy[node*2+1] = lazy[node];
  122. }
  123. lazy[node] = -1;
  124. }
  125. if(ur < l || ul > r) {
  126. return;
  127. }
  128. if(r <= ur && ul <= l) {
  129. //cout<<l<<' '<<r<<' '<<node<<endl;
  130. ll int x = f(val);
  131. s[node] = (r-l+1)*x;
  132. //cout<<s[node]<<endl;
  133. if(l != r) {
  134. lazy[node*2] = x;
  135. lazy[node*2+1] = x;
  136. }
  137. return;
  138. }
  139. ll int mid = (l + r)/2;
  140. update(node*2,l,mid);
  141. update(node*2+1,mid+1,r);
  142. s[node] = s[node*2] + s[node*2+1];
  143. }
  144. ll int query(ll int node,ll int l,ll int r)
  145. {
  146. if(lazy[node] != -1) {
  147. s[node] = (r-l+1)*lazy[node];
  148. if(l != r) {
  149. lazy[node*2] = lazy[node];
  150. lazy[node*2+1] = lazy[node];
  151. }
  152. lazy[node] = -1;
  153. }
  154. if(qr < l || ql > r) {
  155. return 0;
  156. }
  157. if(ql <= l && qr >= r) {
  158. return s[node];
  159. }
  160. ll int mid = (l + r)/2;
  161. return query(node*2,l,mid) + query(node*2+1,mid+1,r);
  162. }
  163. int main()
  164. {
  165. ll int n;
  166. ll int i;
  167. ll int q;
  168. ll int c;
  169.  
  170. cin>>n>>q;
  171. for(i = 1; i <= n; i++) {
  172. cin>>a[i];
  173. a[i] = f(a[i]);
  174. }
  175. build(1,1,n);
  176. for(i = 0; i <= 4*n; i++) {
  177. lazy[i] = -1;
  178. }
  179. //print();
  180. while(q--) {
  181. cin>>c;
  182. if(c == 0) {
  183. cin>>ul>>ur>>val;
  184. ul++;
  185. ur++;
  186. update(1,1,n);
  187. //print();
  188. }
  189. else {
  190. cin>>ql>>qr;
  191. ql++;
  192. qr++;
  193. cout<<query(1,1,n)<<endl;
  194. }
  195. }
  196. }
Time limit exceeded #stdin #stdout 5s 19872KB
stdin
Standard input is empty
stdout
Standard output is empty