Category Archives: Segment Tree

(SPOJ) 61. Brackets

0
Posted on by 
//link: http://www.spoj.com/problems/BRCKTS/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here

struct DATA
{
    int needed_opening;
    int needed_closing;
    DATA()
    {
        needed_closing = needed_opening = 0;
    }
};

#define MAXX 30002

DATA sum[4*MAXX];
char str[MAXX];


void insert(int idx, int st, int ed)
{
    if(st == ed)
    {

        if(str[st] == '(')
        {
            sum[idx].needed_closing = 1;
            sum[idx].needed_opening = 0;
        }
        else
        {
            sum[idx].needed_opening = 1;
            sum[idx].needed_closing = 0;
        }
    }
    else
    {
        int l = idx*2;
        int r = l +1;
        int mid = (st+ed)/2;

        insert(l, st, mid);
        insert(r, mid+1, ed);

        int r_closing_min = min(sum[l].needed_closing, sum[r].needed_opening);

        sum[idx].needed_closing = sum[l].needed_closing - r_closing_min + sum[r].needed_closing;

        sum[idx].needed_opening = sum[r].needed_opening - r_closing_min + sum[l].needed_opening;
    }
}

void update(int idx, int st, int ed, int pos)
{
    if(st == ed)
    {
        if(str[pos] == '(')
        {
            sum[idx].needed_closing--;
            sum[idx].needed_opening++;
            str[pos] = ')';
        }
        else
        {
            sum[idx].needed_closing++;
            sum[idx].needed_opening--;
            str[pos] = '(';
        }
    }
    else
    {
        int l = idx*2;
        int r = l + 1;
        int mid = (st+ed)/2;
        if(pos <= mid)
        {
            update(l, st, mid, pos);
        }
        else
        {
            update(r, mid+1, ed, pos);
        }


        int r_closing_min = min(sum[l].needed_closing, sum[r].needed_opening);

        sum[idx].needed_closing = sum[l].needed_closing - r_closing_min + sum[r].needed_closing;

        sum[idx].needed_opening = sum[r].needed_opening - r_closing_min + sum[l].needed_opening;
    }
}

int main()
{
    int stlen, m, k;

    loop(kaseno, 10)
    {
        pf("Test %d:\n", kaseno+1);
        sf("%d", &stlen);
        stlen--;
        sf("%s", str);
        insert(1, 0, stlen);


        sf("%d", &m);
        loop(i, m)
        {
            sf("%d", &k);
            if(k == 0)
            {
                if(sum[1].needed_closing == 0 && sum[1].needed_opening == 0)
                {
                    pf("YES\n");
                }
                else
                {
                    pf("NO\n");
                }
            }
            else
            {
                update(1, 0, stlen, k-1);
            }
        }
    }



    return 0;
}

(lightoj) 1164 – Horrible Queries

0
Posted on by 
/*
link: http://lightoj.com/volume_showproblem.php?problem=1164
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 10000000000
#define mod abs
#define pf printf
#define sf scanf

using namespace std;


#define MAXX 100002

ll sum[4*MAXX];
int lazy[4*MAXX];



void updateNode(int idx, int st, int ed, int value)
{
    sum[idx] += value * (ed - st + 1);
    lazy[idx] += value;
}




void update(int idx, int st, int ed, int i, int j, int value)
{
    if(st == i && ed == j)
    {
        sum[idx] += value * (ed - st + 1);
        lazy[idx] += value;
        return;
    }



    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed)>>1;

    if(lazy[idx] > 0)
    {
        updateNode(l, st, mid, lazy[idx]);
        updateNode(r, mid+1, ed, lazy[idx]);
    }
    lazy[idx] = 0;


    if(j<=mid)
    {
        update(l, st, mid, i, j, value);
    }
    else if(mid < i)
    {
        update(r, mid+1, ed, i, j, value );
    }
    else
    {
        update(l, st, mid, i, mid, value);
        update(r, mid+1, ed, mid+1, j, value);
    }

    sum[idx] = sum[l] + sum[r];



}

ll query(int idx, int st, int ed, int i, int j)
{
    if(st == i && ed == j)
    {
        return sum[idx];
    }

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed)>>1;

    if(lazy[idx] > 0)
    {
        updateNode(l, st, mid, lazy[idx]);
        updateNode(r, mid+1, ed, lazy[idx]);
    }
    lazy[idx] = 0;

    if(j<=mid)
    {
        return query(l, st, mid, i, j);
    }
    else if(mid < i)
    {
        return query(r, mid+1, ed, i, j);
    }
    else
    {
        return query(l, st, mid, i, mid) + query(r, mid+1, ed, mid+1, j);
    }
}






int main()
{
    //read();
    //write();
    int kases, kaseno = 0;
    getint(kases);
    int cmd, x, y, v;

    int elements, cnt_query;

    while(kases--)
    {
        pf("Case %d:\n", ++kaseno);
        getint(elements);
        getint(cnt_query);

        mem(sum, 0);
        mem(lazy, 0);

        loop(t, cnt_query)
        {
            sf("%d%d%d", &cmd, &x, &y);
            x++;
            y++;
            if(cmd == 0)
            {
                getint(v);
                update(1, 1, elements, x, y, v);
            }
            else
            {
                pf("%lld\n", query(1, 1, elements, x, y));
            }
        }

    }

}

(lightoj) 1087 – Diablo

0
Posted on by 
/*
link: http://lightoj.com/volume_showproblem.php?problem=1087
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 10000000000
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 150005

int cnt_elements[4*MAXX];
vector<int>ids;
int cnt;
int cnt_query;
int total;


void update(int idx, int st, int ed, int pos, int value)
{
    //cout<<"calling with "<<idx<<" and start = "<<st<<" and end ="<<ed<<"and pos = "<<pos<<endl;
    if(st == pos && pos == ed)
    {
        cnt_elements[idx] += value;
        return;
    }


    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed) / 2;

    if(pos <= mid)
    {
        update(l, st, mid, pos, value);
    }
    else
    {
        update(r, mid+1, ed, pos, value);
    }

    cnt_elements[idx] = cnt_elements[l] + cnt_elements[r];
}


int get(int idx, int st, int ed, int pos)
{
    //cout<<"calling with "<<idx<<" and start = "<<st<<" and end ="<<ed<<"and pos = "<<pos<<" and number of elements = "<<cnt_elements[idx]<<endl;

    cnt_elements[idx]--;
    if(st == ed  )
    {
        return st;
    }

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed) / 2;

    if( pos <= cnt_elements[l] )
    {
        return get(l, st, mid, pos);
    }
    else
    {
        return get(r, mid +1, ed, pos - cnt_elements[l]);
    }
}





int main()
{
    //read();
    //write();
    int kases, kaseno = 0;
    getint(kases);
    int num;
    char cmd[4];
    int id;
    int temp;

    while(kases--)
    {
        pf("Case %d:\n", ++kaseno);
        getint(cnt); getint(cnt_query);
        total = cnt + cnt_query;
        temp = cnt;
        mem(cnt_elements, 0);
        ids.clear();

        loop(i, cnt)
        {
            getint(num);
            ids.pb(num);
            update(1, 1, total, i+1, 1);
        }



        loop(t, cnt_query)
        {
            sf("%s", cmd);
            getint(num);


            if(cmd[0] == 'c')
            {


                if(num > cnt)
                {
                    pf("none\n");
                    continue;
                }

                cnt--;

                id = get(1,1, total, num);
                pf("%d\n", ids[id-1]);
            }
            else
            {
                ids.pb(num);
                temp++;
                cnt++;
                update(1, 1, total, temp, 1);

            }
        }



    }

    return 0;
}

(LightOj) 1082 – Array Queries

0
Posted on by 
/*
user: php
link: http://lightoj.com/volume_showproblem.php?problem=1082
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define debug cout<<"came here"<<endl

using namespace std;

#define MAXX 200005

int cnt, sum[MAXX * 4];


void insert_update(int idx, int st, int ed, int pos, int value)
{
    if(st == pos && pos == ed)
    {
        sum[idx] = value;
        return;
    }

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed) / 2;

    if(pos <= mid) insert_update(l, st, mid, pos, value);
    else insert_update(r, mid+1, ed, pos, value);

    sum[idx] = min(sum[l] , sum[r]);
}


int quer(int idx, int st, int ed, int i, int j)
{
    if(i==st && j==ed) return sum[idx];

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed) / 2;


    if(j<=mid)
    {
        return quer(l, st, mid, i, j);
    }
    else if(i > mid)
    {
        return quer(r, mid+1, ed, i, j);
    }
    else return min(quer(l, st, mid, i, mid) , quer(r, mid+1, ed, mid+1, j));


}

int main()
{
    int kases, kaseno = 0;
    int number_of_query;
    int numb;
    int p, q;

    getint(kases);

    while(kases--)
    {
        getint(cnt); getint(number_of_query);
        pf("Case %d:\n", ++kaseno);
        for(int i=1; i<=cnt; i++)
        {
            getint(numb);
            insert_update(1, 1, cnt, i, numb );
        }

        loop(i, number_of_query)
        {
            getint(p); getint(q);

            pf("%d\n", quer(1, 1, cnt, p, q));
        }
    }
    return 0;
}

(UVa) 12086 – Potentiometers (segtree)

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3238
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define debug cout<<"came here"<<endl

using namespace std;

#define MAXX 200005

int cnt, sum[MAXX * 4];


void insert_update(int idx, int st, int ed, int pos, int value)
{
    if(st == pos && pos == ed)
    {
        sum[idx] = value;
        return;
    }

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed) / 2;

    if(pos <= mid) insert_update(l, st, mid, pos, value);
    else insert_update(r, mid+1, ed, pos, value);

    sum[idx] = sum[l] + sum[r];
}


int quer(int idx, int st, int ed, int i, int j)
{
    if(i==st && j==ed) return sum[idx];

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed) / 2;


    if(j<=mid)
    {
        return quer(l, st, mid, i, j);
    }
    else if(i > mid)
    {
        return quer(r, mid+1, ed, i, j);
    }
    else return quer(l, st, mid, i, mid) + quer(r, mid+1, ed, mid+1, j);


}



int main()
{
    //read();

    int kaseno = 0;

    int num;
    char query[5];
    int p, q;

    while(1)
    {
        getint(cnt);
        if(!cnt) break;
        mem(sum, 0);
        for(int i=1; i<=cnt; i++)
        {
            getint(num);
            insert_update(1, 1, cnt, i, num);
        }

        if(kaseno) pf("\n");

        pf("Case %d:\n", ++kaseno);

        while(1)
        {
            sf("%s", query);
            if(query[0] == 'E') break;

            getint(p); getint(q);

            if(query[0] == 'M')
            {
                pf("%d\n", quer(1, 1, cnt, p, q));
            }
            else
            {
                insert_update(1, 1, cnt, p, q);
            }
        }




    }
}

(LightOj) 1112 – Curious Robin Hood

0
Posted on by 
/*
user: php
link: http://lightoj.com/volume_showproblem.php?problem=1112
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define debug cout<<"came here"<<endl

using namespace std;

#define MAXX 100005

int cnt, sum[MAXX * 4];
int ara[MAXX];


void insert_update(int idx, int st, int ed, int pos, int value)
{
    if(st == pos && pos == ed)
    {
        sum[idx] = value;
        return;
    }

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed) / 2;

    if(pos <= mid) insert_update(l, st, mid, pos, value);
    else insert_update(r, mid+1, ed, pos, value);

    sum[idx] = sum[l] + sum[r];
}


int quer(int idx, int st, int ed, int i, int j)
{
    if(i==st && j==ed) return sum[idx];

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed) / 2;


    if(j<=mid)
    {
        return quer(l, st, mid, i, j);
    }
    else if(i > mid)
    {
        return quer(r, mid+1, ed, i, j);
    }
    else return quer(l, st, mid, i, mid) + quer(r, mid+1, ed, mid+1, j);
}



int main()
{
    //read();
    int kases, kaseno = 0;

    int count_query;
    int cmd;
    int i, j, k;

    getint(kases);


    while(kases--)
    {
        pf("Case %d:\n", ++kaseno);
        getint(cnt); getint(count_query);
        int num;

        for(int i=1; i<=cnt; i++)
        {
            getint(num);
            ara[i] = num;
            insert_update(1,1, cnt, i,num);
        }


        loop(i, count_query)
        {
            getint(cmd); getint(j);

            if(cmd == 1)
            {

                pf("%d\n", ara[j+1]);
                ara[j+1] = 0;
                insert_update(1, 1, cnt, j+1, 0);
            }
            else
            {
                getint(k);
                if(cmd == 2)
                {
                    ara[j+1] += k;
                    insert_update(1, 1, cnt, j+1, ara[j+1]);
                }
                else
                {
                    pf("%d\n", quer(1, 1, cnt, j+1, k+1));
                }

            }

        }


    }
}

(LightOj) 1080 – Binary Simulation

0
Posted on by 
/*
user: php
link: http://lightoj.com/volume_showproblem.php?problem=1080
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define debug cout<<"came here"<<endl

using namespace std;

#define MAXX 100005

int cnt, sum[MAXX * 4];
int ara[MAXX];
char str[MAXX];


void insert_update(int idx, int st, int ed, int i, int j)
{
    if(st == i && ed == j)
    {
        sum[idx] ++;
        return;
    }

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed)/2;

    if(j<=mid)
    {
        insert_update(l, st, mid, i, j);
    }
    else if(mid < i)
    {
        insert_update(r, mid+1, ed, i, j);
    }
    else
    {
        insert_update(l, st, mid, i, mid);
        insert_update(r, mid+1, ed, mid+1, j);
    }
}



int quer(int idx, int st, int ed, int pos)
{
    if(st == pos && pos == ed)
    {
        return sum[idx];
    }

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed)/2;

    if(pos <= mid)
    {
        return sum[idx] + quer(l, st, mid, pos);
    }
    else
    {
        return sum[idx] + quer(r, mid+1, ed, pos);
    }
}



int main()
{
    //read();
    int kases, kaseno = 0;

    getint(kases);
    char cmd[3];
    int p, q;

    while(kases--)
    {
        pf("Case %d:\n", ++kaseno);
        mem(sum, 0);

        sf("%s", str);
        int len = strlen(str);

        loop(i, len)
        {
            if(str[i] == '1')
            {
                insert_update(1,1,len, i+1, i+1);
            }
        }

        int number_of_query;

        getint(number_of_query);

        loop(i, number_of_query)
        {
            sf("%s", cmd);
            if(cmd[0] == 'I')
            {
                getint(p); getint(q);
                insert_update(1, 1, len, p, q);
            }
            else
            {
                getint(p);
                pf("%d\n", quer(1, 1, len, p) % 2);
            }
        }






    }
}

(SPOJ) 1043. Can you answer these queries I

0
Posted on by 
/*
user: hasib
link: http://www.spoj.com/problems/GSS1/
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define debug cout<<"came here"<<endl

using namespace std;

#define MAXX 50002

int cnt;


struct DATA{
    int prefixsum, suffixsum, fullsum, maxsum;
};

DATA sum[4*MAXX];


DATA merge(DATA a, DATA b)
{
    DATA result;

    result.fullsum = a.fullsum + b.fullsum;


    result.maxsum = max( a.maxsum, b.maxsum );
    result.maxsum = max( result.maxsum, a.suffixsum + b.prefixsum );

    result.prefixsum = max( a.prefixsum, a.fullsum + b.prefixsum  );

    result.suffixsum = max(b.suffixsum, b.fullsum + a.suffixsum);


    return result;
}




void insert_update(int idx, int st, int ed, int pos, int value)
{
    if(st == pos && pos == ed)
    {

        sum[idx].fullsum = sum[idx].maxsum  = sum[idx].prefixsum = sum[idx].suffixsum = value;
        return;
    }


    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed)/2;


    if(pos <= mid)
    {
        insert_update(l, st, mid, pos, value);
    }
    else
    {
        insert_update(r, mid+1, ed, pos, value);
    }

    sum[idx] = merge(sum[l], sum[r]);
}


DATA quer(int idx, int st, int ed, int i, int j)
{
    if(st == i && ed == j) return sum[idx];

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed)/2;

    if(j <= mid)
    {
        return quer(l, st, mid, i, j);
    }
    else if( i> mid)
    {
        return quer(r, mid+1, ed, i, j);
    }
    else
    {
        return merge( quer(l, st, mid, i, mid), quer(r, mid+1, ed, mid+1, j) );
    }


}

int main()
{
    //read();
    DATA result;
    getint(cnt);
    int num;
    for(int i=1; i<=cnt; i++)
    {
        getint(num);
        insert_update(1, 1, cnt, i, num);
    }

    int m;
    getint(m);
    int p, q;
    loop(i, m)
    {
        getint(p); getint(q);

        result = quer(1, 1, cnt, p, q);
        pf("%d\n", result.maxsum);
    }
    return 0;


}