zjnu1716 NEKAMELEONI (线段树)

Description

"Hey! I have an awesome task with chameleons, 5 th task for Saturday’s competition."

"Go ahead. . . "

(...)

“That’s too difficult, I have an easier one, they won’t even solve that one.”

“You are given an array of N integers from the interval [1, K]. You need to process M queries. The first type of query requires you to change a number in the array to a different value, and the second type of query requires you to determine the length of the
shortest contiguous subarray of the current array that contains all numbers from 1 to K.”

“Hm, I can do it in O(N^6 ). What’s the limit for N?”

Input

The first line of input contains the integers N, K and M (1 <= N, M <= 100 000, 1 <= K <= 50). The second line of input contains N integers separated by space, the integers from the array. After that, M queries follow, each in one of the following two forms:

• “1 p v” - change the value of the p th number into v (1 <= p <= N, 1 <= v <= K)

• “2” - what is the length of the shortest contiguous subarray of the array containing all the integers from 1 to K

Output

The output must consist of the answers to the queries of the second type, each in its own line. If the required subarray doesn’t exist, output −1.

Sample Input

4 3 5

2 3 1 2

2

1 3 3

2

1 1 1

2

6 3 6

1 2 3 2 1 1

2

1 2 1

2

1 4 1

1 6 2

2

Sample Output

3

-1

4

3

3

题意：给你一段长为n的区间，区间内有k(k<=50)种颜色,让你每次更新后找到最短的连续区间，使得这个区间包含全部k种颜色，颜色可以有重复。

思路：一开始的思路是每次更新都用set维护，维护每一种颜色到区间两端点的最近距离，但是这样已更新所有数据都乱了= =，而且时间复杂度也爆了，所以要用别的方法。我们可以在线段树中开两个vector<pair<ll,int> >lo,re,分别表示左端点往右走的最多50种状态，以及右端点往左走的最多50种状态，那么b[i].mindis=min(b[i*2].mindis,b[i*2+1].mindis),然后就是要中间区间的合并了，我们用两个指针，一个p1指向左子树离b[i*2].r的最远的那种状态，然后另一个p2指向右子树离b[i*2+1].l最近的那种状态，每一次判断它们或起来是不是包含全部k种颜色，如果没有的话，p2往右移，如果恰好包含，那么再使得p1向右移。

ps:用pair写代码减少了很多，看着也舒服..

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

typedef long long ll;

#define inf 600000

#define maxn 100050

int a[maxn],k;

struct node{

    int l,r;

    vector< pair<ll,int> >lo,re;

    ll state;

    int mindis;

}b[4*maxn];

void pushup(int th)

{

    int i,j,siz;

    b[th].lo=b[th*2].lo;

    b[th].re=b[th*2+1].re;

    siz=b[th*2].lo.size();

    ll now=b[th*2].lo[siz-1].first;

    for(i=0;i<b[th*2+1].lo.size();i++ ){

        if((now|b[th*2+1].lo[i].first )==now )continue;

        now=(now|b[th*2+1].lo[i].first);

        b[th].lo.push_back(make_pair(now,b[th*2+1].lo[i].second) );

    }

    siz=b[th*2+1].re.size();

    now=b[th*2+1].re[siz-1].first;

    for(i=0;i<b[th*2].re.size();i++ ){

        if((now|b[th*2].re[i].first )==now )continue;

        now=(now|b[th*2].re[i].first );

        b[th].re.push_back(make_pair(now,b[th*2].re[i].second) );

    }

    b[th].state=(b[th*2].state|b[th*2+1].state);

    b[th].mindis=min(b[th*2].mindis,b[th*2+1].mindis);

    ll state=(1LL<<k)-1;

    int weizhi;

    j=0;

    for(i=b[th*2].re.size()-1;i>=0;i--){

        now=b[th*2].re[i].first;

        weizhi=b[th*2].re[i].second;

        while(j<b[th*2+1].lo.size()){

            if((b[th*2+1].lo[j].first|now)==state ){

                b[th].mindis=min(b[th].mindis,b[th*2+1].lo[j].second-weizhi+1 );break;

            }

            j++;

        }

    }

}

void build(int l,int r,int th)

{

    int mid;

    b[th].l=l;b[th].r=r;

    if(l==r){

        b[th].lo.clear();

        b[th].lo.push_back(make_pair(1LL<<a[l],l) );

        b[th].re.clear();

        b[th].re.push_back(make_pair(1LL<<a[l],r));

        b[th].state=(1LL<<a[l]);

        b[th].mindis=inf;return;

    }

    mid=(l+r)/2;

    build(l,mid,th*2);

    build(mid+1,r,th*2+1);

    pushup(th);

}

void update(int idx,int num,int th)

{

    int mid;

    if(b[th].l==idx && b[th].r==idx){

        b[th].lo.clear();

        b[th].lo.push_back(make_pair(1LL<<num,b[th].l) );

        b[th].re.clear();

        b[th].re.push_back(make_pair(1LL<<num,b[th].r));

        b[th].state=(1LL<<num);

        b[th].mindis=inf;return;

    }

    mid=(b[th].l+b[th].r)/2;

    if(idx<=mid)update(idx,num,th*2);

    else update(idx,num,th*2+1);

    pushup(th);

}

int main()

{

    int n,m,i,j,f,c,d;

    while(scanf("%d%d%d",&n,&k,&m)!=EOF)  //k=1的情况特殊考虑

    {

        if(k==1){

            for(i=1;i<=n;i++){

                scanf("%d",&a[i]);

            }

            for(i=1;i<=m;i++){

                scanf("%d",&f);

                if(f==1){

                    scanf("%d%d",&c,&d);

                }

                else printf("1\n");

            }

            continue;

        }

        for(i=1;i<=n;i++){

            scanf("%d",&a[i]);

            a[i]--;

        }

        build(1,n,1);

        for(i=1;i<=m;i++){

            scanf("%d",&f);

            if(f==1){

                scanf("%d%d",&c,&d);

                d--;

                update(c,d,1);

            }

            else{

                if(b[1].mindis>500000)printf("-1\n");

                else printf("%d\n",b[1].mindis);

            }

        }

    }

    return 0;

}

巴特西

zjnu1716 NEKAMELEONI (线段树)

最新文章

热门文章