Spoj CONSEC Solution

#include<bits/stdc++.h>

#define N 200010

#define p pair<int, char>

using namespace std;

int parent[N], dp[N];

int Find(int x)

{

    if(parent[x] == x)

        return x;

    return parent[x] = Find(parent[x]);

}

void Union(int a, int b)

{

    int u = Find(a), v = Find(b);

    if(u == v)

        return;

    if(dp[u] > dp[v])

    {

        parent[v] = u;

        dp[u] += dp[v];

    }

    else

    {

        parent[u] = v;

        dp[v] += dp[u];

    }

}

int main()

{

    int t;

    cin >> t;

    for(int k=1; k<=t; k++)

    {

        string s;

        cin >> s;

        int q, x, y;

        cin >> q;

        for(int i=0; i<=s.size(); i++)

        {

            dp[i] = 1;

            parent[i] = i;

        }

        vector<p>v;

        for(int i=1; i<=q; i++)

        {

            cin >> x >> y;

            if(x == 2)

            {

            v.push_back(p(y, s[y]));

                s[y] = '#';

            }

            else

                v.push_back(p(y, '0'));

        }

        for(int i=0; i<s.size()-1; i++)

        {

            if(s[i] == '#')

                continue;

            if(s[i] == s[i+1])

                Union(i, i+1);

        }

        vector<int>result;

        for(int i=v.size()-1; i>=0; i--)

        {

            int x = v[i].first;

            char ch = v[i].second;

            if(ch == '0')

            {

                int y = Find(x);

                result.push_back(dp[y]);

            }

            else

            {

                s[x] = ch;

                if(x+1 < s.size() && s[x] == s[x+1])

                    Union(x, x+1);

                if(x-1 >= 0 && s[x] == s[x-1])

                    Union(x, x-1);

            }

        }

        reverse(result.begin(), result.end());

        cout << "Case " << k << ":" << "\n";

        for(int i=0; i<result.size(); i++)

            cout << result[i] << "\n";

    }

    return 0;

}