fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define SZ(X) ((int)(X).size())
  3. #define ALL(X) (X).begin(), (X).end()
  4. #define REP(I, N) for (int I = 0; I < (N); ++I)
  5. #define REPP(I, A, B) for (int I = (A); I < (B); ++I)
  6. #define RREP(I, N) for (int I= (N)-1; I>=0; --I)
  7. #define RREPP(I, A, B) for(int I = (B)-1; I>=A; --I)
  8. #define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
  9. #define MP make_pair
  10. #define PB push_back
  11. #define MS0(X) memset((X), 0, sizeof((X)))
  12. #define MS1(X) memset((X), -1, sizeof((X)))
  13. #define LEN(X) strlen(X)
  14. #define F first
  15. #define S second
  16. #define debug(A) REP(i, A.size()) cerr << A[i] << ' '; cerr << '\n'
  17. using namespace std;
  18.  
  19. typedef pair<int, int> ii;
  20. typedef vector<int> vi;
  21. typedef vector<vi> vvi;
  22.  
  23. typedef long long lld;
  24. typedef unsigned long long ulld;
  25. typedef pair<lld, lld> plld;
  26. typedef vector<lld> vlld;
  27. typedef vector<vlld> vvlld;
  28.  
  29. typedef long double ld;
  30. typedef vector<ld> vld;
  31. typedef vector<vld> vvld;
  32.  
  33. const int inf = 987654321;
  34. struct Result { int minPsum, maxPsum, maxi; };
  35. Result merge(const Result& a, const Result& b){
  36. 	Result ret;
  37. 	ret.minPsum=min(a.minPsum, b.minPsum);
  38. 	ret.maxPsum=max(a.maxPsum, b.maxPsum);
  39. 	ret.maxi=max( max(a.maxi, b.maxi), b.maxPsum - a.minPsum );
  40. 	return ret;
  41. }
  42. struct snode {
  43.     int i, j, p; Result res;
  44.     snode *l, *r;
  45.     snode(int i, int j, const vi& arr): i(i), j(j), p(0) {
  46.         if (j - i == 1) {
  47.             l = r = NULL;
  48.            	res.maxi = -inf; res.minPsum = res.maxPsum = arr[i];
  49.         } else {
  50.             int k = i + j >> 1;
  51.             l = new snode(i, k, arr);
  52.             r = new snode(k, j, arr);
  53.             res = merge( l->res, r->res );
  54.         }
  55.     }
  56.     ~snode() { delete l, r; }
  57.     void visit(){
  58.     	res.maxPsum+=p; res.minPsum+=p;
  59.     	if(l) { l->p+=p; r->p+=p; }
  60.     	p=0;
  61.     }
  62.     void add(int I, int J, int v){
  63.     	visit();
  64.     	if (I <= i && j <= J) {
  65.             p+=v;
  66.     		visit();
  67.         } else if (j <= I || J <= i) {
  68.             return;
  69.         } else {
  70.             l->add(I, J, v); r->add(I, J, v);
  71.             res = merge( l->res , r->res );
  72.         }
  73.     }
  74.     Result query(int I, int J) {
  75.     	visit();
  76.         if (I <= i && j <= J) {
  77.             return res;
  78.         } else if (j <= I || J <= i) {
  79.             return {inf, -inf, -inf};
  80.         } else {
  81.         	auto ret = merge( l->query(I,J), r->query(I,J) );
  82.         	return ret;
  83.         }
  84.     }
  85. };
  86.  
  87. struct segment {
  88.     snode *root;
  89.     segment() : root(0) {}
  90.     void init(int n, const vi& arr) {
  91.         if(root) delete root;
  92.         root = new snode(0, n, arr);
  93.     }
  94.     void add(int i, int j, int v){
  95.     	root->add(i, j+1, v);
  96.     }
  97.     int query(int i, int j) {
  98.     	Result ret = root->query(i, j+1);
  99.         return ret.maxi;
  100.     }
  101. };
  102. int N,Q, a,b,c;
  103. int main(){
  104. 	scanf("%d",&N); vi arr(N+1), val(N+1);
  105. 	REP(i, N){ 
  106. 		scanf("%d",&val[i+1]);
  107. 		arr[i+1]=val[i+1]+arr[i];
  108. 	}
  109. 	segment tree; tree.init(N+1, arr);
  110. 	scanf("%d",&Q);
  111. 	while(Q--){
  112. 		scanf("%d%d%d",&a,&b,&c);
  113. 		if(a==0){
  114. 			tree.add(b, N, -val[b]); val[b]=c;
  115. 			tree.add(b, N, val[b]);
  116. 		}else if(a==1){
  117. 			b--; 
  118. 			printf("%d\n", tree.query(b,c) );
  119. 		}
  120. 	}
  121.     return 0;
  122. }
Success #stdin #stdout 0s 3252KB
comments (?)
stdin
copy 
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
stdout
copy 
6
4
-3
https://ideone.com/bU9jJo
http://w...content-available-to-author-only...j.com/problems/GSS3/
language:
C++14 (gcc 8.3)
created:
10 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!