[UVa Live Archive] 5871 - Arnooks's Defensive Line

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 5871 - Arnooks's Defensive Line
Source            : UVa Live Archive
Category          : Divide and Conquer
Algorithm         : solving Insert-Query Problems Offline
Verdict           : Accepted

#include "bits/stdc++.h"  
#include "ext/pb_ds/assoc_container.hpp"  
#include "ext/pb_ds/tree_policy.hpp"  
   
using namespace std;  
using namespace __gnu_pbds;  
   
template <typename T> using orderSet = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;  
   
#define ll                    long long  
#define pii                   pair <int, int>  
#define pll                   pair <ll, ll>  
#define all(a)                a.begin(), a.end()  
#define eb                    emplace_back  
   
static const int maxn = 5e5 + 5;  
   
struct info  
{  
    int type, pos;  
    ll l, r;  
    info(int type = 0, int pos = 0, ll l = 0, ll r = 0)  
    {  
        this->type = type;  
        this->pos = pos;  
        this->l = l;  
        this->r = r;  
    }  
} arr[maxn];  
   
bool comp(const info &A, const info &B)  
{  
    if (A.l == B.l) return A.r < B.r;  
    return A.l < B.l;  
}  
   
vector <info> Insert, Query;  
orderSet <pll> X;  
ll ans[maxn];  
   
void solve()  
{  
    sort(all(Insert), comp);  
    sort(all(Query), comp);  
    int leni = Insert.size();  
    int lenq = Query.size();  
    int i = 0;  
    ll id = 0;  
    for (int j = 0; j < lenq; j++)  
    {  
        while (i < leni && Insert[i].l <= Query[j].l)  
        {  
            X.insert({Insert[i].r, ++id});  
            i++;  
        }  
        ll cnt = X.size() - X.order_of_key({Query[j].r, -1});  
        ans[ Query[j].pos ] += cnt;  
    }  
    Insert.clear();  
    Query.clear();  
    X.clear();  
}  
   
void divideConquer(int l, int r)  
{  
    if (l >= r) return;  
    int mid = (l + r) >> 1;  
    for (int i = l; i <= mid; i++)  
    {  
        if (arr[i].type == 0) // insert  
            Insert.eb(arr[i]);  
    }  
    for (int i = mid+1; i <= r; i++)  
    {  
        if (arr[i].type == 1) // query  
            Query.eb(arr[i]);  
    }  
    solve();  
    divideConquer(l, mid);  
    divideConquer(mid+1, r);  
}  
   
   
int main()  
{  
    //freopen("in.txt", "r", stdin);  
   
    int N;  
    cin >> N;  
    int pos = 0;  
    for (int i = 1; i <= N; i++)  
    {  
        char type;  
        ll l, r;  
        cin >> type >> l >> r;  
        if (l > r) swap(l, r);  
        if (type == '+') arr[i] = info(0, 0, l, r);  
        else arr[i] = info(1, ++pos, l, r);  
    }  
    divideConquer(1, N);  
    for (int i = 1; i <= pos; i++) cout << ans[i] << endl;  
}