Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast,no-stack-protector")
- #pragma GCC target("avx")
- #include <bits/stdc++.h>
- //#include <ext/pb_ds/assoc_container.hpp>
- //#include <ext/pb_ds/tree_policy.hpp>
- //using namespace __gnu_pbds;
- using namespace std;
- #define re return
- #define pb push_back
- #define all(x) (x).begin(), (x).end()
- #define make_unique(x) sort(all(x)),x.resize(unique(all(x))-x.begin())
- #define fi first
- #define se second
- #define ss second.second
- #define sf second.first
- #define ff first.first
- #define fs first.second
- #define sqrt(x) sqrt(abs(x))
- #define mp make_pair
- #define PI 3.14159265358979323846
- #define E 2.71828182845904523536
- #define er erase
- #define in insert
- #define fo(i,n) for(i=0;i<n;i++)
- #define ro(i,n) for(i=n-1;i>=0;i--)
- #define fr(i,j,n) for(i=j;i<n;i++)
- #define rf(i,j,n) for(i=n-1;i>=j;i--)
- //template <class T> using _tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef pair<int,int> ii;
- typedef vector<ii> vii;
- typedef long double ld;
- typedef long long ll;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- typedef pair<ll, ll> pll;
- typedef vector<ll> vll;
- #define filename ""
- const int N=(int)1e5+100;
- int l[N];
- int r[N];
- char c[N];
- int a[3*N];
- vector<int> v;
- class node
- {
- public:
- int sum;
- int all_sum;
- int depth;
- node* left;
- node* right;
- node()
- {
- all_sum = sum = depth = 0;
- left = right = nullptr;
- }
- ~node()
- {
- delete left;
- delete right;
- }
- };
- typedef node* tree;
- int lef = 0;
- int righ = 0;
- void Push(tree root, int left, int right, int Lb, int Rb)
- {
- if (left == Lb && right == Rb)
- {
- root->depth++;
- root->sum = root->all_sum;
- return;
- }
- int middle = (left + right) / 2;
- if (Lb < middle)
- {
- if (!root->left)
- {
- assert(0);
- }
- Push(root->left, left, middle, Lb, std::min(Rb, middle));
- }
- if (Rb>middle)
- {
- if (!root->right)
- {
- assert(0);
- }
- Push(root->right, middle, right, std::max(middle, Lb), Rb);
- }
- if (!root->depth)
- {
- root->sum = 0;
- root->sum += (root->left ? root->left->sum : 0);
- root->sum += (root->right ? root->right->sum : 0);
- }
- }
- void Del (tree root, int left, int right, int Lb, int Rb)
- {
- if (left == Lb && right == Rb)
- {
- root->depth--;
- if (!root->depth)
- {
- root->sum = 0;
- root->sum += (root->left ? root->left->sum : 0);
- root->sum += (root->right ? root->right->sum : 0);
- }
- return;
- }
- int middle = (left + right) / 2;
- if (Lb < middle)
- {
- Del(root->left, left, middle, Lb, std::min(Rb, middle));
- }
- if (Rb>middle)
- {
- Del(root->right, middle, right, std::max(middle, Lb), Rb);
- }
- if (!root->depth)
- {
- root->sum = 0;
- root->sum += (root->left ? root->left->sum : 0);
- root->sum += (root->right ? root->right->sum : 0);
- }
- }
- int create_tree(tree root,int left,int right)
- {
- if (right-left==1)
- {
- return root->all_sum=a[left];
- }
- int middle = (left + right) / 2;
- root->left = new(node);
- root->all_sum+=create_tree(root->left,left,middle);
- root->right = new(node);
- root->all_sum+=create_tree(root->right,middle,right);
- return root->all_sum;
- }
- int main()
- {
- /*
- 4
- + 1 3
- + 2 6
- + 5 7
- - 2 6
- */
- tree roo = new(node);
- lef=0;
- int n,i;
- cin>>n;
- fo(i,n)
- {
- cin>>c[i]>>l[i]>>r[i];
- v.pb(l[i]);
- v.pb(r[i]);
- }
- make_unique(v);
- int m=0;
- map<int,int> t;
- fo(i,v.size())
- {
- if (i)
- {
- a[m++]=v[i]-1-v[i-1];
- }
- t[v[i]]=m;
- a[m++]=1;
- }
- righ=m;
- create_tree(roo,lef,righ);
- fo(i,n)
- {
- l[i]=t[l[i]];
- r[i]=t[r[i]];
- if (c[i]=='+')
- {
- Push(roo, lef, righ, l[i], r[i]);
- }
- else
- {
- Del(roo, lef, righ, l[i], r[i]);
- }
- printf("%d\n",roo->sum);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement