fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <assert.h>
  5. #include <limits.h>
  6. #include <math.h>
  7. #include <time.h>
  8. #include <iostream>
  9. #include <functional>
  10. #include <algorithm>
  11. #include <stack>
  12. #include <queue>
  13. #include <deque>
  14. #include <vector>
  15. #include <string>
  16. #include <bitset>
  17. #include <unordered_map>
  18. #include <set>
  19. using namespace std;
  20. typedef long long lint;
  21. typedef long double llf;
  22. typedef pair<int, int> pi;
  23.  
  24. int n, q;
  25. pi spt[18][140000];
  26. int a[140000], lg[140000];
  27.  
  28. pi query(int s, int e){
  29. 	int lev = lg[e-s+1];
  30. 	return max(spt[lev][s + (1<<lev) - 1], spt[lev][e]);
  31. }
  32.  
  33. void solve(int s, int e);
  34.  
  35. void init(){
  36. 	scanf("%d %d",&n,&q);
  37. 	for(int i=1; i<=n; i++){
  38. 		scanf("%d",&a[i]);
  39. 		spt[0][i] = pi(a[i], i);
  40. 	}
  41. 	int p = 0;
  42. 	for(int i=1; i<=n; i++){
  43. 		while((2 << p) <= i) p++;
  44. 		lg[i] = p;
  45. 	}
  46. 	for(int i=1; i<=17; i++){
  47. 		for(int j=1; j<=n; j++){
  48. 			spt[i][j] = spt[i-1][j];
  49. 			if(j > (1 << (i-1))){
  50. 				spt[i][j] = max(spt[i][j], spt[i-1][j - (1<< (i-1))]);
  51. 			}
  52. 		}
  53. 	}
  54. 	solve(1, n);
  55. }
  56.  
  57. struct seg{
  58. 	lint tree[530000], lazy[530000];
  59. 	void lazydown(int p, int s, int e){
  60. 		int m = (s+e)/2;
  61. 		lazy[2*p] += lazy[p];
  62. 		lazy[2*p+1] += lazy[p];
  63. 		tree[2*p] += lazy[p] * (m - s + 1);
  64. 		tree[2*p+1] += lazy[p] * (e - m);
  65. 		lazy[p] = 0;
  66. 	}
  67. 	void add(int s, int e, int ps, int pe, int p, lint v){
  68. 		if(e < ps || pe < s) return;
  69. 		if(s <= ps && pe <= e){
  70. 			tree[p] += v * (pe - ps + 1);
  71. 			lazy[p] += v;
  72. 			return;
  73. 		}
  74. 		lazydown(p, ps, pe);
  75. 		int pm = (ps + pe) / 2;
  76. 		add(s, e, ps, pm, 2*p, v);
  77. 		add(s, e, pm+1, pe, 2*p+1, v);
  78. 		tree[p] = tree[2*p] + tree[2*p+1];
  79. 	}
  80. 	lint sum(int s, int e, int ps, int pe, int p){
  81. 		if(e < ps || pe < s) return 0;
  82. 		if(s <= ps && pe <= e) return tree[p];
  83. 		lazydown(p, ps, pe);
  84. 		int pm = (ps + pe) / 2;
  85. 		return sum(s, e, ps, pm, 2*p) + sum(s, e, pm+1, pe, 2*p+1);
  86. 	}
  87. }lin, tot;
  88.  
  89. lint ret[140000];
  90.  
  91. struct trapezoid{int s, e, pos, v;};
  92. struct qry{int s, e, idx, buho;};
  93. vector<trapezoid> v;
  94. vector<qry> w[135005];
  95.  
  96.  
  97. void solve(int s, int e){
  98. 	if(s > e) return;
  99. 	pi t = query(s, e);
  100. 	v.push_back({t.second, e, s-1, -t.first});
  101. 	v.push_back({t.second, e, t.second, t.first});
  102. 	solve(s, t.second-1);
  103. 	solve(t.second+1, e);
  104. }
  105.  
  106. int main(){
  107. 	init();
  108. 	for(int i=0; i<q; i++){
  109. 		int s, e;
  110. 		scanf("%d %d",&s,&e);
  111. 		w[s-1].push_back({s, e, i, -1});
  112. 		w[e].push_back({s, e, i, 1});
  113. 	}
  114. 	sort(v.begin(), v.end(), [&](const trapezoid &a, const trapezoid &b){
  115. 		return a.pos < b.pos;
  116. 	});
  117. 	for(auto &k : v){
  118. 		lin.add(k.s, k.e, 1, n, 1, k.v);
  119. 	}
  120. 	int p = 0;
  121. 	for(int i=0; i<=n; i++){
  122. 		for(auto &j : w[i]){
  123. 			ret[j.idx] += 1ll * j.buho * (1ll * i * lin.sum(j.s, j.e, 1, n, 1) + tot.sum(j.s, j.e, 1, n, 1));
  124. 			/*for(auto &k : v){
  125. 				int is = min(j.e, k.e) - max(j.s, k.s) + 1;
  126. 				ret[j.idx] += 1ll * j.buho * max(is, 0) * k.v * min(i, k.pos);
  127. 			}*/
  128. 		}
  129. 		while(p < v.size() && v[p].pos == i){
  130. 			lin.add(v[p].s, v[p].e, 1, n, 1, -v[p].v);
  131. 			tot.add(v[p].s, v[p].e, 1, n, 1, 1ll * v[p].v * v[p].pos);
  132. 			p++;
  133. 		}
  134. 	}
  135. 	for(int i=0; i<q; i++){
  136. 		printf("%lld\n",ret[i]);
  137. 	}
  138. }
Success #stdin #stdout 0s 43480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rLzNjF
language:
C++14 (gcc 8.3)
created:
7 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!