#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5;
int aint[MAXN * 4 + 1]; // aint cu cate sunt deschise
void update ( int nod , int st , int dr , int poz , int val ) {
    int mij;
    if ( st == dr )
        aint[nod] = val;
    else {
        mij = ( st + dr ) / 2;
        if ( poz <= mij )
            update ( nod * 2 , st , mij , poz , val );
        if ( poz > mij )
            update ( nod * 2 + 1 , mij + 1 , dr , poz , val );
        aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
    }
}
int query ( int nod , int st , int dr , int stq , int drq ) {
    int mij , ans;
    if ( stq <= st && dr <= drq )
        return aint[nod];
    mij = ( st + dr ) / 2;
    ans = 0;
    if ( stq <= mij )
        ans = ans + query ( nod * 2 , st , mij , stq , drq );
    if ( drq > mij )
        ans = ans + query ( nod * 2 + 1 , mij + 1 , dr , stq , drq );
    return ans;
}
long long s[MAXN + 1] , s2[MAXN + 1];
long long sumify ( int poz ) {
    if ( poz == -1 )
        return 0;
    return s2[poz];
}
vector < long long > happy ( int n , int q , vector < int > u , vector < int > v , vector < int > h , vector < int > t , vector < int > l , vector < int > r ) {
    int i , st , dr , mij;
    long long sum;
    vector < long long > ans;

    /*
        vreau sa aflu s[x] - s[x - 1] + s[x] - s[x - 1] + .... s[x] - s[y]
        deci (x - y) * s[x] - ( s[x - 1] + s[x - 2] + ... + s[y] )
        fac sume partiale pe sume partiale
    */

    s[0] = h[0];
    for ( i = 1 ; i < n - 1 ; i++ )
        s[i] = s[i - 1] + h[i];
    s2[0] = s[0];
    for ( i = 1 ; i < n - 1 ; i++ )
        s2[i] = s2[i - 1] + s[i];

    sum = 0;
    for ( i = 0 ; i < q ; i++ ) {
         if ( t[i] == 1 ) {
            update ( 1 , 0 , n - 1 , l[i] , 1 );
            st = -1;
            dr = i;
            while ( dr - st > 1 ) {
                mij = ( st + dr ) / 2;
                if ( query ( 1 , 0 , n - 1 , mij , i ) < i - mij + 1 )
                    st = mij;
                else
                    dr = mij;
            }
            sum = sum + ( i - dr + 1 ) * s[i] - ( s2[i - 1] - sumify ( dr - 1 ) );
            st = i;
            dr = n + 1;
            while ( dr - st > 1 ) {
                mij = ( st + dr ) / 2;
                if ( query ( 1 , 0 , n - 1 , i , mij ) < mij - i + 1 )
                    dr = mij;
                else
                    st = mij;
            }
            sum = sum + ( st - i + 1 ) * s[st] - ( s2[st - 1] - sumify ( i - 1 ) );
         }
         else {
            st = -1;
            dr = i;
            while ( dr - st > 1 ) {
                mij = ( st + dr ) / 2;
                if ( query ( 1 , 0 , n - 1 , mij , i ) < i - mij + 1 )
                    st = mij;
                else
                    dr = mij;
            }
            sum = sum - ( i - dr + 1 ) * s[i] - ( s2[i - 1] - sumify ( dr - 1 ) );
            st = i;
            dr = n + 1;
            while ( dr - st > 1 ) {
                mij = ( st + dr ) / 2;
                if ( query ( 1 , 0 , n - 1 , i , mij ) < mij - i + 1 )
                    dr = mij;
                else
                    st = mij;
            }
            sum = sum - ( st - i + 1 ) * s[st] - ( s2[st - 1] - sumify ( i - 1 ) );
            update ( 1 , 0 , n - 1 , l[i] , 0 );
         }
         ans.push_back ( sum );
    }
    return ans;
}
