Advertisement
Guest User

Untitled

a guest
Dec 12th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.25 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,no-stack-protector")
  2. #pragma GCC target("avx")
  3. #include <bits/stdc++.h>
  4. //#include <ext/pb_ds/assoc_container.hpp>
  5. //#include <ext/pb_ds/tree_policy.hpp>
  6. //using namespace __gnu_pbds;
  7. using namespace std;
  8. #define re return
  9. #define pb push_back
  10. #define all(x) (x).begin(), (x).end()
  11. #define make_unique(x) sort(all(x)),x.resize(unique(all(x))-x.begin())
  12. #define fi first
  13. #define se second
  14. #define ss second.second
  15. #define sf second.first
  16. #define ff first.first
  17. #define fs first.second
  18. #define sqrt(x) sqrt(abs(x))
  19. #define mp make_pair
  20. #define PI 3.14159265358979323846
  21. #define E 2.71828182845904523536
  22. #define er erase
  23. #define in insert
  24. #define fo(i,n) for(i=0;i<n;i++)
  25. #define ro(i,n) for(i=n-1;i>=0;i--)
  26. #define fr(i,j,n) for(i=j;i<n;i++)
  27. #define rf(i,j,n) for(i=n-1;i>=j;i--)
  28. //template <class T> using _tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  29. typedef vector<int> vi;
  30. typedef vector<vi> vvi;
  31. typedef pair<int,int> ii;
  32. typedef vector<ii> vii;
  33. typedef long double ld;
  34. typedef long long ll;
  35. typedef unsigned int uint;
  36. typedef unsigned long long ull;
  37. typedef pair<ll, ll> pll;
  38. typedef vector<ll> vll;
  39. #define filename ""
  40. const int N=(int)1e5+100;
  41. int l[N];
  42. int r[N];
  43. char c[N];
  44. int a[3*N];
  45. vector<int> v;
  46.  
  47. class node
  48. {
  49. public:
  50. int sum;
  51. int all_sum;
  52. int depth;
  53. node* left;
  54. node* right;
  55. node()
  56. {
  57. all_sum = sum = depth = 0;
  58. left = right = nullptr;
  59. }
  60. ~node()
  61. {
  62. delete left;
  63. delete right;
  64. }
  65. };
  66.  
  67. typedef node* tree;
  68. int lef = 0;
  69. int righ = 0;
  70.  
  71. void Push(tree root, int left, int right, int Lb, int Rb)
  72. {
  73. if (left == Lb && right == Rb)
  74. {
  75. root->depth++;
  76. root->sum = root->all_sum;
  77. return;
  78. }
  79. int middle = (left + right) / 2;
  80. if (Lb < middle)
  81. {
  82. if (!root->left)
  83. {
  84. assert(0);
  85. }
  86. Push(root->left, left, middle, Lb, std::min(Rb, middle));
  87. }
  88. if (Rb>middle)
  89. {
  90. if (!root->right)
  91. {
  92. assert(0);
  93. }
  94. Push(root->right, middle, right, std::max(middle, Lb), Rb);
  95. }
  96. if (!root->depth)
  97. {
  98. root->sum = 0;
  99. root->sum += (root->left ? root->left->sum : 0);
  100. root->sum += (root->right ? root->right->sum : 0);
  101. }
  102. }
  103.  
  104. void Del (tree root, int left, int right, int Lb, int Rb)
  105. {
  106. if (left == Lb && right == Rb)
  107. {
  108. root->depth--;
  109. if (!root->depth)
  110. {
  111. root->sum = 0;
  112. root->sum += (root->left ? root->left->sum : 0);
  113. root->sum += (root->right ? root->right->sum : 0);
  114. }
  115. return;
  116. }
  117. int middle = (left + right) / 2;
  118. if (Lb < middle)
  119. {
  120. Del(root->left, left, middle, Lb, std::min(Rb, middle));
  121. }
  122. if (Rb>middle)
  123. {
  124. Del(root->right, middle, right, std::max(middle, Lb), Rb);
  125. }
  126. if (!root->depth)
  127. {
  128. root->sum = 0;
  129. root->sum += (root->left ? root->left->sum : 0);
  130. root->sum += (root->right ? root->right->sum : 0);
  131. }
  132. }
  133. int create_tree(tree root,int left,int right)
  134. {
  135. if (right-left==1)
  136. {
  137. return root->all_sum=a[left];
  138. }
  139. int middle = (left + right) / 2;
  140. root->left = new(node);
  141. root->all_sum+=create_tree(root->left,left,middle);
  142. root->right = new(node);
  143. root->all_sum+=create_tree(root->right,middle,right);
  144. return root->all_sum;
  145. }
  146. int main()
  147. {
  148. /*
  149. 4
  150. + 1 3
  151. + 2 6
  152. + 5 7
  153. - 2 6
  154. */
  155. tree roo = new(node);
  156. lef=0;
  157. int n,i;
  158. cin>>n;
  159. fo(i,n)
  160. {
  161. cin>>c[i]>>l[i]>>r[i];
  162. v.pb(l[i]);
  163. v.pb(r[i]);
  164. }
  165. make_unique(v);
  166. int m=0;
  167. map<int,int> t;
  168. fo(i,v.size())
  169. {
  170. if (i)
  171. {
  172. a[m++]=v[i]-1-v[i-1];
  173. }
  174. t[v[i]]=m;
  175. a[m++]=1;
  176. }
  177. righ=m;
  178. create_tree(roo,lef,righ);
  179. fo(i,n)
  180. {
  181. l[i]=t[l[i]];
  182. r[i]=t[r[i]];
  183. if (c[i]=='+')
  184. {
  185. Push(roo, lef, righ, l[i], r[i]);
  186. }
  187. else
  188. {
  189. Del(roo, lef, righ, l[i], r[i]);
  190. }
  191. printf("%d\n",roo->sum);
  192. }
  193. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement