[线段树 + 尺取法]连续的“包含”子串长度

女爷i 2021-11-23 02:26 140阅读 0赞

### 文章目录 ###

*  题目
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  样例
     *   *  样例输入1
         *  样例输出1
         *  样例输入2
         *  样例输出2
     *  数据范围与提示
 *  解析
 *   *  尺取法
     *  线段树
     *  Code

--------------------

# 题目 #

## 题目描述 ##

区间查询和修改

给定N,K,M（N个整数序列，范围1~K，M次查询或修改）

如果是修改，则输入三个数，第一个数为1代表修改，第二个数为将N个数中第i个数做修改，第三个数为修改成这个数(例如1 3 5就是修改数组中第3个数，使之变为5)

如果是查询，则输入一个数2，查询N个数中包含1~K每一个数的最短连续子序列的长度

## 输入格式 ##

第一行包含整数 N 、 K N、K N、K和 M M M（ 1 ≤ N , M ≤ 100000 1 ≤ N,M ≤ 100000 1≤N,M≤100000, 1 ≤ K ≤ 50 1 ≤ K ≤ 50 1≤K≤50）

第二行输入 N N N个数，用空格隔开，组成该数组

然后 M M M行表示查询或修改

• “ 1 p v 1 p v 1pv” - change the value of the pth number into  v v v ( 1 ≤ p ≤ N , 1 ≤ v ≤ K 1 ≤ p ≤ N,1 ≤ v ≤ K 1≤p≤N,1≤v≤K)

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

简单来说就是， 1 1 1为将 p p p位置的值改为 v v v， 2 2 2则是查询包含 1 − k 1-k 1−k的最短子序列。

## 输出格式 ##

输出必须包含查询的答案，如果不存在则输出-1

## 样例 ##

### 样例输入1 ###

4 3 5
    2 3 1 2
    2
    1 3 3
    2
    1 1 1
    2

### 样例输出1 ###

3
    -1
    4

### 样例输入2 ###

6 3 6
    1 2 3 2 1 1
    2
    1 2 1
    2
    1 4 1
    1 6 2
    2

### 样例输出2 ###

3
    3
    4

## 数据范围与提示 ##

In test cases worth  30 % 30\\% 30% of total points, it will hold  1 ≤ N , M ≤ 5000 1 ≤ N,M ≤ 5000 1≤N,M≤5000.

# 解析 #

不得不说，最近几次考试的好多题都是不可多得的 毒瘤***好题*** 啊！！

反正一如既往的一看就不会，一想就崩溃，最后只能象征性的爆搜以证明自己有想无奈放弃。。。我果然还是太蒟了啊QAQ~~~

emmm先看题：

区间查询+区间修改，一看就是线段树嘛，这个一般都能想到吧。。。

再看，求一个满足某某条件（最开始看也没看懂，但是这个不重要）的最小连续子序列，立马就联系到尺取法了吧。当然，尺取法我没讲，这里就先贴贴同机房的[苣佬博客][Link 1]康康（有没童鞋看过*杰哥不要*的？？）

## 尺取法 ##

既然都说看苣佬的博客了，我肯定也不能跟他抢阅读量不是、、、 那么，我就简单地介绍一下尺取法，好让大家看之前先有个概念

其实吧，尺取法也不是特别难，正如其名，就假设有一把尺子比着，这个尺子模拟的就是需要求的一些满足条件的连续子序列。

那么这个“尺子”到底该如何移动呢？？我们先令其左右端点分别为 L L L和 R R R，首先先向右移动右端点伸长尺子所包含的区间，等到满足条件后再向右移动左端点缩短区间，求得当前的最小状态。

这样的复杂度只需 O ( 2 n ) O(2n) O(2n)，也就是近似 O ( n ) O(n) O(n)!这无疑快了许多

## 线段树 ##

相信各位都会线段树，那么我就不再赘述线段树的概念了，这里就只讨论这道题的线段树的情况。

在这里，线段树中肯定得维护有最后求得的答案，也就是最短的包含 1 − k 1-k 1−k的连续子序列。

那么，线段树又该如何维护这个答案呢？？我们手推一下就能够发现它满足前缀后缀的性质，所以我们即可以通过维护一个前缀和一个后缀来间接维护答案。当然，这个前缀、后缀的长度 l e n len len也是绝对不能少的（前后缀的长度相等，所以用一个代替两个即可）。

接下来就该讨论怎么维护前缀和后缀了。可以想象，当左儿子和右儿子合并到他们的父亲时，父亲的前缀肯定是左儿子的前缀，而他的后缀则是右儿子的后缀，那么我们就可以赋上初值。

当然就这样还是不够的，我们还可以考虑一下合(cè)并(fǎn)右儿子的前缀，如果说合起来还能作新的扩展的话，自然求之不得了。

再然后，就是父亲的中间部分的情况了，也就是左儿子的后缀部分加上右儿子的前缀部分，要是他们中也包含着 1 − k 1-k 1−k的最小连续子序列的话，那么也就更新答案。

最后，具体的细节全在代码中，大家可以看看注释，有助于理解~~~

## Code ##

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <cstring>
    #include <iostream>
    using namespace std;
    #define reg register
    #define LL long long
    #define pll pair<LL, int>
    #define INF 0x3f3f3f3f
    
    template<typename T>
    void re (T &x){ 
        x = 0;
        int f = 1;
        char c = getchar ();
        while (c < '0' || c > '9'){ 
            if (c == '-') f = -1;
            c = getchar ();
        }
        while (c >= '0' && c <= '9'){ 
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
        x *= f;
    }
    
    template<typename T>
    void pr (T x){ 
        if (x < 0){ 
            putchar ('-');
            x = ~x + 1;
        }
        if (x / 10) pr (x / 10);
        putchar (x % 10 + 48);
    }
    
    #define N 262145
    
    struct Tree{     //线段树里存的是前缀后缀集合，存的是这个前（后）缀的状态和坐标
        pll pre[55], suf[55];
        int len, ans;
        Tree (){ 
            ans = INF;
        }
    }tre[N + 5];
    int Maxnode, n, k, m;
    
    void Merge (int t, int l, int r){    //合并操作，将左儿子向右延伸，右向左延伸，并用尺取法更新最小的答案
        int lenpre = 0, lensuf = 0;
        for (int i = 0; i < tre[l].len; i++)    //先将原本的左儿子前缀赋给父亲前缀
            tre[t].pre[lenpre++] = tre[l].pre[i];
        for (int i = 0; i < tre[r].len; i++){    //看能不能和右儿子的前缀结合，形成新的父亲的前缀
            if (!lenpre || ((tre[t].pre[lenpre - 1].first & tre[r].pre[i].first) != tre[r].pre[i].first)){ 
                            //如果说没有之前的，防止越界到负数；或者前一个不包含右边的状态，判重
                            //至于为什么要-1，是因为上面的lenpre最后多加了一个
                tre[t].pre[lenpre] = tre[r].pre[i]; //先更新
                if (lenpre)                         //如果能合并就与前一个合并
                    tre[t].pre[lenpre].first |= tre[t].pre[lenpre - 1].first;
                lenpre ++;
            }
        }
        for (int i = 0; i < tre[r].len; i++)    //右儿子后缀作为父亲的后缀，与上对应
            tre[t].suf[lensuf++] = tre[r].suf[i];
        for (int i = 0; i < tre[l].len; i++){    //同上，看能不能和左儿子后缀结合，形成新的父亲后缀
            if (!lensuf || ((tre[t].suf[lensuf - 1].first & tre[l].suf[i].first) != tre[l].suf[i].first)){ 
                            //判重，防越界
                tre[t].suf[lensuf] = tre[l].suf[i];
                if (lensuf) //和前面的合并
                    tre[t].suf[lensuf].first |= tre[t].suf[lensuf - 1].first;
                lensuf ++;
            }
        }
        tre[t].ans = min (tre[l].ans, tre[r].ans);  //先赋初值为左儿子和右儿子的ans
        tre[t].len = lenpre;    //最后的lenpre和lensuf长度都一样
        int L = tre[l].len - 1, R = 0;  //尺取法，从左儿子的后缀搜到右儿子的前缀，先延伸右边，再收回左边
        while (1){ 
            while (R < tre[r].len){  //延伸右边，如果一直在右儿子的左边
                if ((tre[l].suf[L].first | tre[r].pre[R].first) == ((1ll << k) - 1)){    //左右相加
                                                                    //看是否能得到所有状态，更新ans
                                                                    //开始就是这里的+（|）写成了&，二进制要注意！！
    				tre[t].ans = min (tre[t].ans, tre[r].pre[R].second - tre[l].suf[L].second + 1);
                    break;
    			}
                R ++;
            }
            L --;
            if (L < 0) break;   //如果说左边超过了左儿子的右边部分，就退出
        }
    }
    
    void update (int pos, int val){  //起到赋初值和更新的作用
        pos += Maxnode; //得到这个点的树中的点的编号，即位置
        tre[pos].pre[0] = pll (1ll << val, pos - Maxnode);  //前缀后缀最开始都是自己那一个
        tre[pos].suf[0] = pll (1ll << val, pos - Maxnode);
        tre[pos].len = 1;
        while (pos >> 1){    //更新父亲与左右合并
            pos >>= 1;
            Merge (pos, pos << 1, pos << 1 | 1);
        }
    }
    
    int main (){ 
        re (n); re (k); re (m);
        int tot = 1;
        while (tot < n){     //算出树中满节点最多有多少个
            Maxnode += tot;
            tot <<= 1;
        }
        for (int i = 1; i <= n; i++){ 
            int a; re (a);
            update (i, a - 1);
        }
        for (int i = 1; i <= m; i++){ 
            int x; re (x);
            if (x == 2){ 
                if (tre[1].ans != INF)
                    pr (tre[1].ans);
                else pr (-1);
                putchar (10);
            }
            else{ 
                int p, v; re (p); re (v);
                update (p, v - 1);
            }
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/qq_41814502/article/details/97157741