fork download
copy 
  1. /*
  2. *************************************************************************
  3. * $ Author : honeyslawyer   $
  4. * $ Name   : shashank gupta $
  5. *************************************************************************
  6. *
  7. * Copyright 2013 @ honeyslawyer and shashank gupta
  8. *
  9. ************************************************************************/
  10. #include<cstdio>
  11. #include<iostream>
  12. #include<cmath>
  13. //#include<conio.h>
  14. #include<cstring>
  15. #include<ctype.h>
  16. #include<algorithm>
  17. #include<vector>
  18. #include<stdlib.h>
  19. #include<map>
  20. #include<queue>
  21. #include<stack>
  22. #include<set>
  23. #include<string>
  24. #include<climits>
  25.  
  26. #define mod 1000000007
  27. #define ll long long
  28. #define total 100005
  29. using namespace std;
  30. ll gcd(ll a,ll b) {if(b==0) return a; return gcd(b,a%b);}
  31. #define gc getchar_unlocked
  32. void scan(int &x)
  33. {
  34.     register int c = gc();
  35.     x = 0;
  36.     int neg = 0;
  37.     for(;((c<48 || c>57) && c != '-');c = gc());
  38.     if(c=='-') {neg=1;c=gc();}
  39.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  40.     if(neg) x=-x;
  41. }
  42. ll power(ll b,ll exp,ll m)
  43.  {ll ans=1;
  44.   b%=m;
  45.   while(exp)
  46.    {if(exp&1)
  47.      ans=(ans*b)%m;
  48.     exp>>=1;
  49. 	b=(b*b)%m;
  50.    }
  51.   return ans;
  52.  }
  53. struct node{
  54.   int msum;
  55.   int m;
  56. 	void merge(node& l, node& r){
  57.         msum=max(l.msum,max(r.msum,r.m+l.m));
  58.         m=max(r.m,l.m);
  59. 	}
  60. 	void split(node& l, node& r){
  61. 	}
  62. };
  63. template<class node>
  64. class segtree{/*{{{*/
  65. 	template<bool b>class param{};
  66. 	inline void spltdwn(int idx,param<true>){splt(idx);}
  67. 	inline void splt(int idx){/*{{{*/
  68. 		idx>>=1;
  69. 		if(idx>0)splt(idx);
  70. 		tree[idx].split(tree[idx<<1],tree[(idx<<1)|1]);
  71. 	}/*}}}*/
  72. 	inline void spltdwn(int,param<false>){};
  73. 	inline void split(node& a, node& b, node& c, param<true> ){return a.split(b,c);}
  74. 	inline void split(node&, node&, node&, param<false>){}
  75. 	template<typename t,void (t::*)(t&,t&)> class T{};
  76. 	template<typename t> static char test(T<t,&t::split>*){return 0;}
  77. 	template<typename t> static long double test(...){return 0;}
  78. 	int u,v;
  79. 	node query(int root, int left_range, int right_range){/*{{{*/
  80. 		if(u<=left_range && right_range<=v)
  81. 			return tree[root];
  82. 		int mid = (left_range + right_range)>>1,
  83. 			l = root<<1,
  84. 			r = l|1;
  85. 		if(has_split)split(tree[root],tree[l],tree[r],param<has_split>());
  86. 		node res;
  87. 		if(u>=mid)res=query(r,mid,right_range);
  88. 		else if(v<=mid)res=query(l,left_range,mid);
  89. 		else{
  90. 			node n1 = query(l,left_range,mid),
  91. 				 n2 = query(r,mid,right_range);
  92. 			res.merge(n1,n2);
  93. 		}
  94.                 if(has_split) tree[root].merge(tree[l],tree[r]);
  95. 		return res;
  96. 	}/*}}}*/
  97.  	template<void(*fn)(node&)>
  98. 	void local_update(int root, int left_range,int right_range){/*{{{*/
  99. 		if(u<=left_range && right_range<=v){
  100. 			return fn(tree[root]);
  101. 		}
  102. 		int mid = (left_range + right_range)>>1,
  103. 			l = root<<1,
  104. 			r = l|1;
  105. 		if(has_split)split(tree[root],tree[l],tree[r],param<has_split>());
  106. 		if(v>mid)local_update<fn>(r,mid,right_range);
  107. 		if(u<mid)local_update<fn>(l,left_range,mid);
  108. 		tree[root].merge(tree[l],tree[r]);
  109. 	}/*}}}*/
  110. 	void mrgup(int idx){/*{{{*/
  111. 		idx>>=1;
  112. 		while(idx>0)
  113. 			tree[idx].merge(tree[idx<<1],tree[(idx<<1)|1]),
  114. 			idx>>=1;
  115. 	}/*}}}*/
  116. public:
  117. 	static bool const has_split = (sizeof(test<node>(0))==sizeof(char));
  118. 	int N;
  119. 	int leftmost_leaf, rightmost_leaf;
  120. 	node* tree;
  121. 	node identity;
  122. 	segtree(){ tree=0; }
  123. 	~segtree(){
  124.                 if(tree) delete[] tree;
  125. 	}
  126. 	void init(int n, const node a[], const node& identity){/*{{{*/
  127.                 if(tree) delete[] tree;
  128. 		this->identity = identity;
  129. 		N=0;
  130. 		while((1<<N)<n)N++;
  131. 		leftmost_leaf = 1<<N;
  132. 		rightmost_leaf = leftmost_leaf<<1;
  133. 		tree = new node[rightmost_leaf];
  134. 		for(int i=0;i<n;i++)
  135. 			tree[i+leftmost_leaf] = a[i];
  136. 		for(int i=n+leftmost_leaf;i<rightmost_leaf;i++)
  137. 			tree[i]=identity;
  138. 		for(int i=leftmost_leaf-1;i;i--)
  139. 			tree[i].merge(tree[i<<1],tree[(i<<1)|1]);
  140. 	}/*}}}*/
  141. 	node query(int u, int v){//[u,v]/*{{{*/
  142. 		this->u=u+leftmost_leaf;
  143. 		this->v=v+leftmost_leaf+1;
  144. 		return query(1,leftmost_leaf,rightmost_leaf);
  145. 	}/*}}}*/
  146. 	node query(int u){//faster version of query(u,u)/*{{{*/
  147. 		//indexing starts from 0
  148. 		u+=leftmost_leaf;
  149. 		spltdwn(u,param<has_split>());
  150. 		return tree[u];
  151. 	}/*}}}*/
  152. 	template<void(*fn)(node&)>
  153. 	void update(int u, int v){/*{{{*/
  154. 		//0-indexed
  155. 		this->u=u+leftmost_leaf;
  156. 		this->v=v+leftmost_leaf+1;
  157. 		return local_update<fn>(1,leftmost_leaf,rightmost_leaf);
  158. 	}/*}}}*/
  159. 	template<void(*fn)(node&)>
  160. 	void update(int u){//faster version of update(u,u)/*{{{*/
  161. 		//indexing starts from 0
  162. 		u+=leftmost_leaf;
  163. 		spltdwn(u,param<has_split>());
  164. 		fn(tree[u]);
  165. 		mrgup(u);
  166. 	}/*}}}*/
  167. 	void split_down(int leaf_idx){/*{{{*/
  168. 		spltdwn(leaf_idx+leftmost_leaf,param<has_split>());
  169. 	}/*}}}*/
  170. 	void merge_up(int leaf_idx){/*{{{*/
  171. 		mrgup(leaf_idx+leftmost_leaf);
  172. 	}/*}}}*/
  173. 	bool is_leaf(int tree_idx){return tree_idx>=leftmost_leaf;}
  174. 	int binary_search(node k){/*{{{*/
  175. 	//search the last place i, such that merge( everyting to the left of i(including i) ) compares less than k
  176.         int root = 1;
  177.         node n=identity;
  178. 		//identity satisfies merge(identity,y) = merge(y,identity) = y for all y.
  179. 		assert(!(k<identity));
  180.         while(!is_leaf(root)){
  181.                 int left_child = root<<1,
  182. 					right_child = left_child|1;
  183.                 if(has_split)
  184. 					split(tree[root],tree[left_child],tree[right_child],param<has_split>());
  185.                 node m;
  186.                 m.merge(n,tree[left_child]);
  187.                 if(m<k){//go to right side
  188.                         n=m;
  189.                         root=right_child;
  190.                 }else root=left_child;
  191.         }
  192.         node m;
  193.         m.merge(n,tree[root]);
  194. 		mrgup(root);
  195.         if(m<k)return root-leftmost_leaf;
  196.         else return root-1-leftmost_leaf;
  197. 	}/*}}}*/
  198. };/*}}}*/
  199. int v,z;
  200. void inc_by_v(node& n){
  201.     n.msum=v;
  202.     n.m=v;
  203.  
  204.  
  205. }
  206. int main(){
  207. 		int N,q;
  208. 		//scanf("%d %d",&N,&q);
  209. 		scan(N);
  210.  
  211. 		node array[N+4];
  212. 		for(int i=0;i<N;i++)
  213. 		{
  214.             int temp;
  215.             scan(temp);
  216. 			array[i].m=temp;array[i].msum=temp;
  217.  
  218.         }
  219. 		node identity;
  220.         identity.m=0,identity.msum=0;
  221. 		segtree<node> s;
  222. 		s.init(N,array,identity);
  223. 		scan(q);
  224. 		while(q--){
  225. 			int t,a,b;
  226. 			char e;
  227. 			scanf("%c",&e);
  228. 			//scanf("%d%d%d",&t,&a,&b);
  229. 			//scan(t);
  230. 			scan(a);
  231. 			scan(b);
  232. 			//printf("%d %d\n",a,b);
  233. 			if(a>b)std::swap(a,b);
  234. 			a--,b--;
  235. 			if(e!='Q')
  236. 			{
  237. 				//scan(v),z=t;
  238. 				v=b+1;
  239. 				//printf("here\n");
  240. 				s.update<&inc_by_v>(a);
  241.             }
  242. 			else
  243. 			{
  244. 				node f=s.query(a,b);
  245. 				printf("%d\n",f.msum);
  246.  
  247. 			}
  248. 		}
  249. 	return 0;
  250. }
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5
stdout
copy 
7
9
11
12
https://ideone.com/7dvrao
language:
C++ (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!