2015年8月1日 星期六

2015/08/01 Codeforces 551E. GukiZ and GukiZiana

/*
    發現各種 QlogN的資料結構
    很難維護
    於是思路轉向 QN^(1/2)
    塊狀表!

    插曲嘛...
    把 map 改成 unordered_map
    long long 改成 int 才過 > <
*/
// http://codeforces.com/contest/551/problem/E
#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map>

using namespace std;

typedef long long ll;
unordered_map<int, vector<int> > m[710];
ll add[710];

int N, Q;
ll T[1000000];

int main()
{
    scanf("%d %d", &N, &Q);

    for(int Ni = 0; Ni < N; Ni++)
    {
        int A;
        scanf("%d", &A);

        m[Ni/710][A].push_back(Ni);
    }

    for(int Qi = 0; Qi < Q; Qi++)
    {
        int sp;
        scanf("%d", &sp);

        if( sp == 1 )
        {
            int l, r, x;
            scanf("%d %d %d", &l, &r, &x);
            l--;

            for(int i = 0; i < 710; i++)
                if( l <= i*710 && (i+1)*710 <= r ) add[i] += x;
                else if( r <= i*710 || (i+1)*710 <= l );
                else
                {
                    for(auto it: m[i])
                    {
                        vector<int> &v = it.second;
                        ll num = it.first;

                        for(int vi = 0; vi < v.size(); vi++)
                            T[v[vi] ] = num;
                    }

                    m[i].clear();

                    for(int j = i*710; j < (i+1)*710 && j < N; j++)
                        if( l <= j && j < r )
                        {
                            if( T[j]+x <= 1e9 ) m[i][T[j]+x ].push_back(j);
                            else T[j] = 2e9;
                        }
                        else m[i][T[j] ].push_back(j);

                }
        }
        else if( sp == 2 )
        {
            int y;
            scanf("%d", &y);

            int mx = -1, mn = N;

            for(int i = 0; i < 710; i++)
                if( y-add[i] >= 0 && m[i].find(y-add[i]) != m[i].end() )
                {
                    mn = m[i][y-add[i] ].front();
                    break;
                }

            for(int i = 709; i >= 0; i--)
                if( y-add[i] >= 0 && m[i].find(y-add[i]) != m[i].end() )
                {
                    mx = m[i][y-add[i] ].back();
                    break;
                }

            if( mx == -1 ) puts("-1");
            else printf("%d\n", mx-mn);
        }
    }
}

沒有留言:

張貼留言