fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define endl '\n'
  4. #define left jhghajkhja
  5. #define right oauighgajk
  6. #define prev aioghajga
  7. #define next ioyhjhfajasj
  8. #define y0 iuadoghasdgj
  9. #define y1 taklahgjkla
  10. #define remainder pogjuakllhga
  11. #define pow pajklgaklha
  12. #define pow10 iopuioadjlgkah
  13. #define div aljghajkghak
  14.  
  15. //#define floor hjakjhaja
  16. //#define time ashjlahjka
  17. //#define double_t double
  18. //#define tm kahjflahaajk
  19.  
  20. using namespace std;
  21.  
  22. const int N = 1<<17;
  23.  
  24. template <typename T>
  25. struct implicit_treap {
  26. private:
  27. 	#define NEUTRAL_VALUE 0
  28. 	#define NEUTRAL_DELTA 0
  29. 	struct xorshift {
  30. 		unsigned long long x,y,z,w;
  31. 		xorshift(): x(1234567891011121314),
  32. 			y(5346754754),
  33. 			z(777777777777777),
  34. 			w(125573887823)
  35. 		{}
  36. 		unsigned long long next() {
  37. 			unsigned long long t=x^(x<<11);
  38. 			x=y;y=z;z=w;
  39. 			return w=w^(w>>19)^t^(t>>8);
  40. 		}
  41. 	};
  42. 	struct node {
  43. 		T node_value;
  44. 		T subtree_value;
  45. 		T delta;
  46. 		unsigned size;
  47. 		unsigned long long priority;
  48. 		node *left, *right;
  49. 	};
  50. 	typedef node *node_ptr;
  51. 	node_ptr root;
  52. 	xorshift rng;
  53. 	T join_values(T a, T b) {
  54. 		return a+b;
  55. 	}
  56. 	T join_deltas(T a, T b) {
  57. 		return a+b;
  58. 	}
  59. 	T join_value_with_delta(T a, T b, int length) {
  60. 		return a+b*length;
  61. 	}
  62. 	unsigned long long next() {
  63. 		return rng.next();
  64. 	}
  65. 	node_ptr new_node(T key) {
  66. 		node_ptr res=(node_ptr)malloc(sizeof(node));
  67. 		res->node_value=key;
  68. 		res->subtree_value=key;
  69. 		res->delta=NEUTRAL_DELTA;
  70. 		res->size=1;
  71. 		res->priority=next();
  72. 		res->left=NULL;
  73. 		res->right=NULL;
  74. 		return res;
  75. 	}
  76. 	unsigned get_size(node_ptr &a) {
  77. 		if(a==NULL) return 0;
  78. 		else return a->size;
  79. 	}
  80. 	T get_subtree_value(node_ptr &a) {
  81. 		if(a==NULL) return NEUTRAL_VALUE;
  82. 		else return a->subtree_value;
  83. 	}
  84. 	void update_node(node_ptr &a) {
  85. 		if(a==NULL) return;
  86. 		a->size=1+get_size(a->left)+get_size(a->right);
  87. 		a->subtree_value=join_values(a->node_value,join_values(get_subtree_value(a->left),get_subtree_value(a->right)));
  88. 	}
  89. 	void apply_delta(node_ptr &a, T delta) {
  90. 		if(a==NULL) return;
  91. 		a->delta=join_deltas(a->delta,delta);
  92. 		a->node_value=join_value_with_delta(a->node_value,delta,1);
  93. 		a->subtree_value=join_value_with_delta(a->subtree_value,delta,a->size);
  94. 	}
  95. 	void push_delta(node_ptr &a) {
  96. 		if(a==NULL) return;
  97. 		apply_delta(a->left,a->delta);
  98. 		apply_delta(a->right,a->delta);
  99. 		a->delta=NEUTRAL_DELTA;
  100. 	}
  101. 	void merge(node_ptr &t, node_ptr l, node_ptr r) {
  102. 		push_delta(l);
  103. 		push_delta(r);
  104. 		if(l==NULL) t=r;
  105. 		else if(r==NULL) t=l;
  106. 		else if(l->priority<r->priority) merge(l->right,l->right,r),t=l;
  107. 		else merge(r->left,l,r->left),t=r;
  108. 		update_node(t);
  109. 	}
  110. 	void split(node_ptr t, node_ptr &l, node_ptr &r, int key) {
  111. 		push_delta(t);
  112. 		if(t==NULL) l=NULL,r=NULL;
  113. 		else if(key<=get_size(t->left)) split(t->left,l,t->left,key),r=t;
  114. 		else split(t->right,t->right,r,key-1-get_size(t->left)),l=t;
  115. 		update_node(l);
  116. 		update_node(r);
  117. 	}
  118. public:
  119. 	implicit_treap(): root(NULL) {}
  120. 	void clear() {
  121. 		root=NULL;
  122. 		rng=xorshift();
  123. 	}
  124. 	unsigned size() {
  125. 		return get_size(root);
  126. 	}
  127. 	void insert(T key, int position) {
  128. 		node_ptr t1=new node(),t2=new node();
  129. 		split(root,t1,t2,position-1);
  130. 		merge(t1,t1,new_node(key));
  131. 		merge(root,t1,t2);
  132. 	}
  133. 	void update(int from, int to, T value) {
  134. 		node_ptr t1=new node(),t2=new node(),t3=new node();
  135. 		split(root,t1,t3,to);
  136. 		split(t1,t1,t2,from-1);
  137. 		apply_delta(t2,value);
  138. 		merge(t1,t1,t2);
  139. 		merge(root,t1,t3);
  140. 	}
  141. 	T query(int from, int to) {
  142. 		node_ptr t1=new node(),t2=new node(),t3=new node();
  143. 		T ans;
  144. 		split(root,t1,t3,to);
  145. 		split(t1,t1,t2,from-1);
  146. 		ans=get_subtree_value(t2);
  147. 		merge(t1,t1,t2);
  148. 		merge(root,t1,t3);
  149. 		return ans;
  150. 	}
  151. };
  152.  
  153. int tests,n,q;
  154. int a[N];
  155. implicit_treap <long long> t;
  156.  
  157. int main() {
  158.     ios_base::sync_with_stdio(false);
  159.     cin.tie(NULL);
  160.     //freopen("test.txt","r",stdin);
  161.     //freopen(IN.c_str(),"r",stdin);
  162.     //freopen(OUT.c_str(),"w",stdout);
  163.     //fread(buff,1,sizeof(buff),stdin);
  164.     int i,type,from,to,w;
  165.  
  166.     scanf("%d", &tests);
  167.     while(tests--) {
  168. 		scanf("%d %d", &n, &q);
  169. 		t.clear();
  170. 		for(i=1;i<=n;i++) {
  171. 			t.insert(0,i);
  172. 		}
  173. 		while(q--) {
  174. 			scanf("%d", &type);
  175. 			if(type==0) {
  176. 				scanf("%d %d %d", &from, &to, &w);
  177. 				t.update(from,to,w);
  178. 			}
  179. 			else {
  180. 				scanf("%d %d", &from, &to);
  181. 				printf("%lld\n", t.query(from,to));
  182. 			}
  183. 		}
  184. 	}
  185.  
  186.     //fprintf(stderr, "Time: %d ms\n", (int)(clock()*1000.0/CLOCKS_PER_SEC));
  187.  
  188.     return 0;
  189. }
  190.  
Success #stdin #stdout 0s 3984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vQtdmN
language:
C++14 (gcc 8.3)
created:
8 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!