一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

题解 P4422 【[COCI2017-2018#1] Deda】

posted on 2018-12-07 19:27:03 | under 题解 |

这题是小JF在学长的考试题里见到的,听同级的dalao说分块要n log n sqrt n ,不信邪的JF就写了个n sqrt n 的做法,代码量自然不大, 思路也不难想。连写带调也就花了20分钟,下面就说一下具体思路。

维护一下快内的最小值,散块直接暴力循环, 整块看维护的最小值是否小于等于查询值,如果不符合的话就可以直接跳过,否则答案就一定在该块中,暴力循环即可,复杂度 n sqrt n , 而且这个最小值是非常好维护的,因为每个点最多被修改一次,所以直接取min就好了,修改的复杂度O1

所以该算法的修改是O1 查询是 O(sqrt n) 足以通过此题

另:因为要求的是第一个小于等于某数的位置,所以分块查询的时候要注意散块和整块的查询顺序, 一开始sb的JF还因为习惯先查散块再查整块WA掉了,顺序应该是: 左散块 -> 中间的整块 -> 右散块

然后就没什么啦,有什么问题可以私信小蒟蒻。

那么代码如下:

#include<iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 200010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, x, y, z, k;
int sq;
int a[maxn], b[maxn], minn[2002];
char t;

inline void in(re int &x){
    x=0;int bl = 1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c == '-')
          bl = -1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x *= bl;
}

void out(re int a){
    if(a < 0) {
        putchar('-');
        a = -a;
    }
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

inline int query(int x, int y, int k) {
    FOR(i, x, min(y, b[x]*sq)) //左散块
      if(a[i] <= k)
        return i;
    FOR(i, b[x]+1, b[y]-1) { //整块
        if(minn[i] > k) //如果不符合直接跳过
          continue;
        FOR(j, (i-1)*sq+1, i*sq) //暴力找
          if(a[j] <= k)
            return j; 
    }   
    if(b[x] != b[y]) //右散块
      FOR(i, (b[y]-1)*sq+1, y)
        if(a[i] <= k)
          return i;
    return -1;
}

int main(){
    in(n), in(m);
    sq = sqrt(n);
    FOR(i, 1, sq+100)
      minn[i] = 0x7fffffff;
    FOR(i, 1, n)
      a[i] = 0x7fffffff, b[i] = (i-1)/sq+1, minn[b[i]] = min(minn[b[i]], a[i]);
    FOR(i, 1, m) {
        cin >> t;
        if(t == 'M') {
            in(x), in(y); // y改成x; 
            a[y] = x;
            minn[b[y]] = min(minn[b[y]], x); //维护最小值
        }
        else {
            in(k), in(x);
            out(query(x, n, k));
            putchar(10);
        }
    }

}