Category Archives: Data Structure

(Spoj) 6256. Inversion Count (INVCNT)

0
Posted on by 

#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

#define MAXX 10000002
#define lowBit(x) (x & -(x))


int tree[MAXX];


void update(int pos, int val)
{
    while(pos<= MAXX)
    {
        tree[pos] += val;
        pos = pos + lowBit(pos);
    }
}

ll get(int pos)
{
    ll sum = 0;
    while(pos>0)
    {
        sum += tree[pos];
        pos -= lowBit(pos);
    }
    return sum;
}


int main()
{
    int ara[200000+2];
    int kases;

    take(kases);

    int n;

    while(kases--)
    {
        mem(tree, 0);
        ll res = 0;
        take(n);

        loop(i, n)
        {
            take(ara[i]);
        }

        for(int i=n-1; i>-1; i--)
        {
            update(ara[i], 1);
            res += get(ara[i]-1);
        }

        cout<<res<<endl;


    }


}

(SPOJ) 8425. Coloring Trees

0
Posted on by 
#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 MAXX 100002
char color[MAXX];
int parent[MAXX];
vector<int>graph[MAXX];


int find(int u)
{
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}

int main()
{
    int N;
    int x, a, b;
    sf("%d", &N);
    loop(i, N)
    {
        color[i] = -1;
        parent[i] = i;
    }
    N--;
    loop(i, N)
    {
        sf("%d %d", &a, &b);
        graph[a].pb(b);
        graph[b].pb(a);
    }

    int Q;
    sf("%d", &Q);

    loop(i, Q)
    {
        sf("%d %d %d", &x, &a, &b);
        if(x == 1)
        {
            color[a] = b;
            loop(i, SZ(graph[a]))
            {
                if(color[graph[a][i]] == b)
                {
                    parent[find(a)] = find(graph[a][i]);
                }
            }
        }
        else if(x==2)
        {
            if(find(a) == find(b))
            {
                if(a!=b || color[a] != -1 )
                    pf("YES\n");
                else
                    pf("NO\n");
            }

            else
                pf("NO\n");
        }
    }
    return 0;
}

(UVa) 10226 – Hardwood Species

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1167
*/

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

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


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#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 freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)

using namespace std;


#define ALPHA_LIST 128

struct node{
    int cnt_trees;
    node *child[ALPHA_LIST];

    node()
    {
        cnt_trees = 0;
        loop(i, ALPHA_LIST)
        {
            child[i] = NULL;
        }
    }
}*head;

int total;


/*
void clearTree(node *p)
{
    loop(i, ALPHA_LIST)
    {
        if(p->child[i] != NULL)
        {
            clearTree(p->child[i]);
        }
    }
    delete p;
}

void init()
{
    head = new node();
}


int toint(char c)
{
    if(c== ' ')
        return 26;
    if('a' <= c && c <= 'z')
        return c - 'a';
    else
        return c - 'A';
}
*/

void insert(char *word)
{
    //cout<<"inserting " << word<<endl;
    node *current = head;

    int ch;

    while(*word != '\0')
    {
        ch = *word;

        if(current->child[ch] == NULL)
            current->child[ch] = new node();
        current = current->child[ch];
        word++;
    }
    current->cnt_trees++;
}

vector<char> name_list;

void printTree(node *current)
{
    if(current->cnt_trees)
    {
        FOR(i, 0, SZ(name_list))
        {
            pf("%c", name_list[i]);
        }
        pf(" %.4lf\n", (100.0*current->cnt_trees)/(double)total);
        //current->cnt_trees = 0;
    }

    loop(i, ALPHA_LIST)
    {
        if(current->child[i] != NULL)
        {
            name_list.pb(i);
            printTree(current->child[i]);
            name_list.pop_back();
        }
    }

    delete current;
    //current = NULL;
}


int main()
{
    int kases;
    char names[35];
    bool blank = 0;

    gi(kases);
    cin.ignore();
    cin.ignore();

    while(kases--)
    {
        if(blank) pf("\n");
        blank = 1;

        head = new node();

        //init();

        //cout<<head<<endl;

        total = 0;
        while(gets(names))
        {
            if(strlen(names) == 0) break;
            insert(names);
            total++;
        }

        printTree(head);

        //head = NULL;
        //cout<<head<<endl<<endl<<endl;

        //clearTree(head);
    }


    return 0;
}

(UVa) 514 Rails

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

#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 1<<29
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 1002


int cntCells;


int main()
{
    int id;

    while(getint(cntCells) && cntCells!= 0)
    {

        while(getint(id) && id != 0)
        {


            if(!id) break;

            queue<int>B;


            B.push(id);


            FOR(i, 1, cntCells)
            {
                getint(id);
                B.push(id);
            }

            int pos = 1;

            stack<int>station;

            while( !B.empty()  )
            {
                while(station.empty() || station.top() !=B.front() )
                {
                    if(pos > cntCells) break;
                    station.push(pos);
                    pos++;
                }

                if(station.top() == B.front() )
                {
                    station.pop();
                    B.pop();
                }
                else
                {
                    break;
                }
            }

            if(B.empty())
            {
                pf("Yes\n");
            }
            else
            {
                pf("No\n");
            }
        }
        pf("\n");






    }


    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);
            }
        }




    }
}

(UVa) 12086 – Potentiometers (sqrt approach)

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;
int root;
int ara[MAXX];
ll sum[ 450 ];
int cnt_segment;


char query[5];



ll getSum(int i, int j)
{
    ll total = 0;

    if(int(i/root) == int(j/root))
    {
        while(i <= j)
        {
            total += ara[i++];
        }
        return total;
    }



    int start = (i/root) + 1;
    int end = j/root;


    FOR(t, start, end)
    {
        total+=sum[t];
    }

    end = start * root;

    FOR(t, i, end)
    {
        total += ara[t];
    }


    start = j/root;
    start *= root;
    j++;


    FOR(t, start, j)
    {
        total += ara[t];
    }


    return total;


}


void update(int pos, int value)
{
    int i = pos / root;
    if(i < root)
    {
        sum[i] = sum[i] - ara[pos] + value;
    }
    ara[pos] = value;
}




int main()
{
    //read();
    int p, q;
    int kaseno = 0;
    bool blank = false;

    while(true)
    {
        getint(cnt);
        if(cnt == 0) break;

        loop(i, cnt)
        {
            getint(ara[i]);
        }


        root = sqrt(cnt);

        cnt_segment = cnt / root;

        loop(i, cnt_segment)
        {
            sum[i] = 0;
            int till = (i+1) * root;

            FOR(j, i*root, till )
            {

                sum[i] += ara[j];
            }

        }



        if(blank) pf("\n");
        blank = true;

        pf("Case %d:\n", ++kaseno);
        while(true)
        {
            sf("%s", query);

            if(query[0] == 'E') break;
            getint(p); getint(q);

            if(query[0] == 'M')
            {
                pf("%lld\n", getSum(p-1, q-1));
            }
            else
            {
                update(p-1, 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));
                }

            }

        }


    }
}