P1Selectivo2015 (Segmentarbol pajero)

#include <iostream>
#include <cstring>
#include <queue>
#include <cstring>
#define forn(i,n) for(int i=0; i<n; i++)

using namespace std;

const int maxN = 1e6;
const int magia = (1<<(20+1));
int L, total;
queue<int> pos[256];
char orig[maxN], modif[maxN];
int ST[magia], lazy[magia];

void build(){
    memset(ST, 0, sizeof ST);
    memset(lazy, 0, sizeof lazy);
}

void update(int index, int s, int e, int qs, int qe, int v){
    if(s>e) return;

    if(lazy[index]){
        ST[index] += lazy[index] * (s-e+1);
        if(s!=e){
            lazy[index*2] += lazy[index];
            lazy[index*2+1] += lazy[index];
        }
        lazy[index] = 0;
    }

    if(s>qe || e<qs) return;
    if(s>=qs && e<=qe){
        ST[index] += v * (s-e+1);
        if(s!=e){
            lazy[index*2] += v;
            lazy[index*2+1] += v;
        }
        return;
    }

    int mid = (s+e)/2;
    update(index*2, s, mid, qs, qe, v);
    update(index*2+1, mid+1, e, qs, qe, v);
}

int query(int index, int s, int e, int qs, int qe){
    if(s>e) return 0;
    if(lazy[index]){
        ST[index] += lazy[index] * (s-e+1);
        if(s!=e){
            lazy[index*2] += lazy[index];
            lazy[index*2+1] += lazy[index];
        }
        lazy[index] = 0;
    }
    if(s>qe || e<qs) return 0;
    if(s>=qs && e<=qe){
        return ST[index];
    }

    int mid = (s+e)/2;
    return query(index*2, s, mid, qs, qe) + query(index*2+1, mid+1, e, qs, qe);
}

int main(){
    cin.getline(orig,maxN);
    cin.getline(modif,maxN);
    L = strlen(orig);
    forn(i,L)
        pos[ int(orig[i]) ].push(i);
    build();
    forn(i,L){
        int j = pos[ int(modif[i]) ].front();
        pos[ int(modif[i]) ].pop();
        total += j - i + query(1, 0, L-1, j, j);
        update(1, 0, L-1, 0, j, 1);
    }
    cout << total << endl;

    return 0;
}