fork(9) download
  1. //Mobius_Treap
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef pair<int,int> II;
  7. typedef vector< II > VII;
  8. typedef vector<int> VI;
  9. typedef vector< VI > VVI;
  10. typedef long long int LL;
  11.  
  12. #define PB push_back
  13. #define MP make_pair
  14. #define F first
  15. #define S second
  16. #define SZ(a) (int)(a.size())
  17. #define ALL(a) a.begin(),a.end()
  18. #define SET(a,b) memset(a,b,sizeof(a))
  19.  
  20. #define si(n) scanf("%d",&n)
  21. #define dout(n) printf("%d\n",n)
  22. #define sll(n) scanf("%lld",&n)
  23. #define lldout(n) printf("%lld\n",n)
  24. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  25.  
  26. //#define TRACE
  27.  
  28. #ifdef TRACE
  29. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  30. template <typename Arg1>
  31. void __f(const char* name, Arg1&& arg1){
  32. cerr << name << " : " << arg1 << std::endl;
  33. }
  34. template <typename Arg1, typename... Args>
  35. void __f(const char* names, Arg1&& arg1, Args&&... args){
  36. const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  37. }
  38. #else
  39. #define trace(...)
  40. #endif
  41.  
  42. //FILE *fin = freopen("in","r",stdin);
  43. //FILE *fout = freopen("out","w",stdout);
  44.  
  45. const int N=100100;
  46. int K,A[N];
  47. pair<II,II> qu[N];
  48. deque<int> Q[N];
  49. multiset<int > my;
  50. int ans[N];
  51. bool cmp(pair<II,II> a,pair<II,II> b)
  52. {
  53. int aa=a.S.S;
  54. int bb=b.S.S;
  55. if(aa!=bb)
  56. return (aa<bb);
  57. return a.F.F<b.F.F;
  58. }
  59. int main()
  60. {
  61. int n,q;
  62. si(n);
  63. si(q);
  64. K=sqrt(2*N);
  65. A[0]=50050;
  66. for(int i=1;i<=n;i++)
  67. {
  68. int x;
  69. si(x);
  70. A[i]=A[i-1]+x;
  71. trace(i,A[i]);
  72. }
  73. for(int i=0;i<q;i++)
  74. {
  75. si(qu[i].F.F),si(qu[i].F.S);
  76. qu[i].F.F--;
  77. qu[i].S.F=i;
  78. qu[i].S.S=qu[i].F.S/K;
  79. }
  80. sort(qu,qu+q,cmp);
  81. int l=0,r=0;
  82. Q[A[0]].push_front(0);
  83. for(int i=0;i<q;i++)
  84. {
  85. int L=qu[i].F.F;
  86. int R=qu[i].F.S;
  87. while(r<R)
  88. {
  89. r++;
  90. if(SZ(Q[A[r]])>1)
  91. {
  92. int prev=Q[A[r]].back()-Q[A[r]].front();
  93. my.erase(my.find(prev));
  94. }
  95. Q[A[r]].push_back(r);
  96. if(SZ(Q[A[r]])>1)
  97. {
  98. int cur=Q[A[r]].back()-Q[A[r]].front();
  99. my.insert(cur);
  100. }
  101. }
  102. while(l>L)
  103. {
  104. l--;
  105. if(SZ(Q[A[l]])>1)
  106. {
  107. int prev=Q[A[l]].back()-Q[A[l]].front();
  108. my.erase(my.find(prev));
  109. }
  110. Q[A[l]].push_front(l);
  111. if(SZ(Q[A[l]])>1)
  112. {
  113. int cur=Q[A[l]].back()-Q[A[l]].front();
  114. my.insert(cur);
  115. }
  116. }
  117. while(l<L)
  118. {
  119. if(SZ(Q[A[l]])>1)
  120. {
  121. int prev=Q[A[l]].back()-Q[A[l]].front();
  122. my.erase(my.find(prev));
  123. }
  124. Q[A[l]].pop_front();
  125. if(SZ(Q[A[l]])>1)
  126. {
  127. int cur=Q[A[l]].back()-Q[A[l]].front();
  128. my.insert(cur);
  129. }
  130. l++;
  131. }
  132. while(r>R)
  133. {
  134. if(SZ(Q[A[r]])>1)
  135. {
  136. int prev=Q[A[r]].back()-Q[A[r]].front();
  137. my.erase(my.find(prev));
  138. }
  139. Q[A[r]].pop_back();
  140. if(SZ(Q[A[r]])>1)
  141. {
  142. int cur=Q[A[r]].back()-Q[A[r]].front();
  143. my.insert(cur);
  144. }
  145. r--;
  146. }
  147. if(!my.empty())
  148. ans[qu[i].S.F]=*my.rbegin();
  149. }
  150. for(int i=0;i<q;i++)
  151. dout(ans[i]);
  152. return 0;
  153. }
Success #stdin #stdout 0.08s 64376KB
stdin
6 4
1 1 1 -1 -1 -1
1 3
1 4
1 5
1 6
stdout
0
2
4
6