P4117 [Ynoi2018] 五彩斑斓的世界 题解

· · 题解

首先，我们先搞清楚一个前置问题：把区间 [l,r] 中所有的 x 变成 y 该怎么做：

我们把拥有同样的值的下标，扔进一个并查集，并建立一个 name 数组表示值 i 所使用的集合。

也就是说，我们这个操作流程是这样的：

我们跑到一个位置，且这个位置的值为 x，我们把这个位置的下标叫做 i 。

如果值 y 目前不存在，我们把 value[i] 设为 y，并把 name[y] 设为 i 。

如果值 y 存在，那就把这个位置的 pre （并查集表示父亲的数组） 设为 name[y] （也就是之前出现过的 y 的位置）。

这个问题搞清楚了，我们就可以来搞第一个操作了：把区间 [l,r] 中大于 x 的数减 x 。

我们设 maxx 为这个区间的最大值。

当 x > maxx \div 2 时，直接暴力把所有大于 x 的数减去 x 。

这一部分是 x + 1 到区间的最大值。

当 x <= maxx \div 2 时，我们把小于 x 的加上 x ，然后标记整个区间减 x 即可。

这一部分是从 0 开始到 x 。

最后都需要加上 lazy 再操作，因为我们的 lazy 是一个减的标记呀。

第二个操作输出 x 的出现次数，这个并查集维护一下大小就行了。

此时我们得到了一个空间复杂度为 O(n\sqrt{n}) 的做法，其中 \sqrt{n} 为块长。

空间限制 64MB，无法通过此题，考虑优化。

我们离线处理，对于每一个块，单独操作，并将答案累加，最后处理完所有的块之后输出。

这样，每一次处理完一个块之后清空并查集，可以做到线性空间，足以通过此题。

然后呢，你需要大力卡常，数组压到最小，坏习惯去掉， x + lazy 大于 10^5 的询问不处理，不在范围内的跳过。

最重要的是，所有的函数前面，加上inline。

no inline

inline

跑的居然还不是特别慢，在第二页。

#include<bits/stdc++.h>

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
    int op;
    int l;
    int r;
    int x;
}q[1000010];

int n,m;
int a[1000010];
int block;
int len;
int pre[1000010];
int name[100010];
int val[1000010];
int siz[100010];
int lazy;
int maxx;
int ans[1000010];

inline void build(int x){//
    maxx = -2147483647;
    lazy = 0;
    int bl,br;
    bl = (x - 1) * block + 1;
    br = x * block;
    if(x == len)br = n;
    for(int i = bl;i <= br;i ++){
        maxx = max(maxx,a[i]);
        if(!name[a[i]]){
            val[i] = a[i];
            name[a[i]] = i;
            pre[i] = i;
        }
        else pre[i] = name[a[i]];
        siz[a[i]] ++;
    }
}

inline int find(int x){
    if(x == pre[x])return x;
    else return pre[x] = find(pre[x]);
}

inline void change(int x,int y){//
    if(name[y]){
        pre[name[x]] = name[y];
        siz[y] += siz[x];
        name[x] = siz[x] = 0;
    }
    else {
        val[name[y] = name[x]] = y;
        siz[y] += siz[x];
        name[x] = siz[x] = 0;
    }
}

inline void update(int num,int l,int r,int x){//
    int bl,br;
    bl = (num - 1) * block + 1;
    br = num * block;
    if(num == len)br = n;
    l = max(l,bl),r = min(r,br);
    for(int i = bl;i <= br;i ++){
        int w = val[find(i)];
        a[i] = w - lazy;
        name[w] = 0;
        siz[w] = 0;
    }
    for(int i = bl;i <= br;i ++)val[i] = 0;
    for(int i = l;i <= r;i ++)if(a[i] > x)a[i] -= x;
    build(num);
}

inline void update1(int x){
    if(x > (maxx - lazy) / 2){
        for(int i = x + 1 + lazy;i <= maxx;i ++)if(name[i])change(i,i - x);
        maxx = min(maxx,x + lazy);
    }
    else {
        for(int i = lazy;i <= x + lazy;i ++)if(name[i])change(i,i + x);
        lazy += x;
    }
}

inline int query(int num,int l,int r,int x){
    int ans = 0;
    int bl,br;
    bl = (num - 1) * block + 1;
    br = num * block;
    if(num == len)br = n;
    l = max(l,bl),r = min(r,br);
    for(int i = l;i <= r;i ++)if(val[find(i)] - lazy == x)ans ++;
    return ans;
}

inline void write(int x){
    if(x < 0)putchar('-'),x = -x;
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
}

signed main(){
    cin>>n>>m;
    block = sqrt(n);
    len = ceil(n * 1.0 / block);
    for(int i = 1;i <= n;i ++)a[i] = read();
    for(int i = 1;i <= m;i ++){
        q[i].op = read();
        q[i].l = read();
        q[i].r = read();
        q[i].x = read();
    }
    for(int i = 1;i <= len;i ++){
        if(i != 1){
            memset(name,0,sizeof(name));
            memset(siz,0,sizeof(siz));
        }
        lazy = 0;
        maxx = -2147483647;
        int bl,br;
        bl = (i - 1) * block + 1;
        br = i * block;
        if(i == len)br = n;
        build(i);
        for(int j = 1;j <= m;j ++){
            int op,l,r,x;
            op = q[j].op;
            l = q[j].l;
            r = q[j].r;
            x = q[j].x;
            if(bl > r || br < l)continue;
            if(op == 1){
                if(!(bl >= l && br <= r))update(i,l,r,x);
                else update1(x);
            }
            else {
                if(x + lazy > 1e5 + 1)continue;
                if(!(bl >= l && br <= r))ans[j] += query(i,l,r,x);
                else ans[j] += siz[x + lazy];
            }
        }
    }
    for(int i = 1;i <= m;i ++)if(q[i].op == 2)write(ans[i]),puts("");
    return 0;
}