「Ynoi2018」五彩斑斓的世界

写了有一段时间了，忘更博客（咕咕咕）。

Idea：lxl Solution：lxl Std：lxl Data：lxlIdea：lxl Solution：lxl Std：lxl Data：lxl

“突刺贯穿的第二分块” （妈呀这名字好中二啊（谁叫我要用日本轻小说中的东西命名真是作死））

这题的来源比较神奇，大概是 csy 搬了一个全局大于 x 的减 x，查 kth 什么的题，然后我想把这个出区间上

然后直接出会得到一个 $O(n\sqrt{n}\log n)$ 的废物，当时想了很久都没想到什么trick能做值域1e9的情况（有没有人教教我啊）

然后改了改发现值域1e5是可以做的就出了出来

对这题的评价：6/11

顺便这题的 Version4 是查询区间 rank ，我记得当时我用当时感觉挺厉害的 trick 做到了和现在一样的复杂度不过感觉不 practical 所以没有挂出来

[Luogu 4117]

[BZOJ 5143]

[CF 896E]

所以 lxl 啥时候把加强的数据咕出来啊（

好现在咕出来了，然后我过不去了，找时间来改（咕咕咕

题意简述

一个长为 $n$ 的序列，$m$ 个操作。操作可能是以下两种：

• 将区间 $[l, r]$ 内所有大于 $x$ 的数减去 $x$ 。
• 求区间 $[l, r]$ 内 $x$ 的个数。

$1\le n, m, a_i\le 10^5$ 。

主要思路

考虑分块，块长 $O(\sqrt{n})$。显然，每块的最大值总是不增的。

我们用某种数据结构来维护块内的所有数，设将某个数合并到另一个数上的时间复杂度是 $O(k)$，查询某种数的个数的时间复杂度是 $O(t)$。

假设一个块所有大于 $x$ 的数减去 $x$ ，最大值为 $v$ 。

• 当 $v \le 2\times x$ 时，可以把所有 $[x + 1, v]$ 内的数合并到 $[1, x]$ 上。这样，我们用 $O(v - x)\times O(k)$ 的时间让块内的最大值减小了 $v - x$ 。
• 当 $v > 2\times x$ 时，可以把所有 $[1, x]$ 内的数合并到 $[x + 1, 2\times x]$ 上。这样，我们用 $O(x)\times O(k)$ 的时间让块内的最大值减少了 $x$ 。

散块的修改则重构整块，复杂度 $O(k\times\sqrt{n})$。

由于开始时所有块的最大值之和是 $O(n\sqrt{n})$ ，所以修改的复杂度是 $O(n\sqrt{n}\times k)$ 。查询的复杂度是 $O(n\sqrt{n}\times t)$ 。

类似未来日记，使用并查集来维护块内的所有数，则 $k = t = 1$ ，总复杂度 $O(n\sqrt{n})$ ，可以通过此题。

参考代码

#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define reg register
    #define Rint register int
    #define FOR(i,a,b) for(register int i=(a),ed_##i=(b);i<=ed_##i;++i)
    #define ROF(i,a,b) for(register int i=(a),ed_##i=(b);i>=ed_##i;--i)
    #define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)+1;i!=ed_##i;++i)
    #define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)-1;i!=ed_##i;--i)
    #define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
    #define MEM(x,v) memset(x,v,sizeof(x))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define MP make_pair
    typedef long long LL;
    typedef double DB;
    typedef pair<int,int> PII;
    #define Templ(T) template<typename T>
    inline int read(){
        reg int ans=0,f=1; reg char c=getchar();
        while(!isdigit(c)) f^=(c=='-'), c=getchar();
        for(;isdigit(c);c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48);
        return f?ans:-ans;
    }
    Templ(_Tp) inline int chkmin(_Tp &x,_Tp y){ return x>y?x=y,1:0; }
    Templ(_Tp) inline int chkmax(_Tp &x,_Tp y){ return x<y?x=y,1:0; }
    #define using_mod
    const int mod = 998244353;
    #ifdef using_mod
    inline void inc(int &x, const int &y){ x += y; if(x >= mod) x -= mod; }
    inline void dec(int &x, const int &y){ x -= y; if(x < 0) x += mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    #endif
    Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
    inline int VSC_Local(){
        #ifdef VSC_Compile
        while(getchar() != '\n');
        #endif
        return 0;
    }
    #define FILE(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
    #define PBTXDY
}
using namespace my_std;

const int N = 100010, Vmax = 100000, SN = 330;
int blo, Bcnt;
int n, m, a[N], bl[N], fth[N], siz[N];
int ary[N];

int find(int x){ return x == fth[x] ? x : fth[x] = find(fth[x]); }

struct Block{
    int bg, ed, tag, mx;//数 y 实际值为 y - tag 
    int pos[N];
    inline void build(){
        FOR(i, bg, ed) fth[i] = siz[i] = 0;
        tag = 0, mx = 0;
        FOR(i, bg, ed){
            if(!pos[a[i]]) pos[a[i]] = fth[i] = i, siz[i] = 1;
            else ++siz[ fth[i] = pos[a[i]] ];
            chkmax(mx, a[i]);
        }
    }
    inline int query(int x){
        return x + tag <= Vmax && pos[x + tag] ? siz[pos[x + tag]] : 0;
    }
    inline void update(int x){
        if(x >= mx) return;
        if(2 * x >= mx){
            FOR(val, x + 1 + tag, mx + tag) if(pos[val]){
                Rint f = val - x;
                if(pos[f]) fth[pos[val]] = pos[f], siz[pos[f]] += siz[pos[val]];
                else pos[f] = pos[val], a[pos[val]] -= x;
                pos[val] = 0;
            }
            mx = x;
        }
        else{
            ROF(val, x + tag, 1 + tag) if(pos[val]){
                Rint f = val + x;
                if(pos[f]) fth[pos[val]] = pos[f], siz[pos[f]] += siz[pos[val]];
                else pos[f] = pos[val], a[pos[val]] += x;
                pos[val] = 0;
            }
            tag += x, mx -= x;
        }
    }
}B[SN];

inline void SBupd(int p, int l, int r, int x){
    Rint tag = B[p].tag, L = B[p].bg, R = B[p].ed;
    FOR(i, L, R) B[p].pos[a[find(i)]] = 0;
    FOR(i, L, R) ary[i] = a[find(i)] - tag;
    FOR(i, L, R) a[i] = l <= i && i <= r && ary[i] > x ? ary[i] - x : ary[i];
    return B[p].build();
}
inline int SBqry(int p, int l, int r, int x){
    Rint res = 0, rx = x + B[p].tag;
    FOR(i, l, r) res += (a[find(i)] == rx);
    return res;
}

inline void update(int l, int r, int x){
    Rint lb = bl[l], rb = bl[r];
    if(lb == rb) return SBupd(lb, l, r, x);
    SBupd(lb, l, B[lb].ed, x), SBupd(rb, B[rb].bg, r, x);
    FOR(bid, lb + 1, rb - 1) B[bid].update(x);
    return;
}
inline int query(int l, int r, int x){
    Rint lb = bl[l], rb = bl[r];
    if(lb == rb) return SBqry(lb, l, r, x);
    Rint res = SBqry(lb, l, B[lb].ed, x) + SBqry(rb, B[rb].bg, r, x);
    FOR(bid, lb + 1, rb - 1) res += B[bid].query(x);
    return res;
}

inline void init(){
    Rint cb = 1;
    FOR(i, 1, n){
        a[i] = read();
        bl[i] = i % blo ? cb : cb ++;
    }
    Bcnt = bl[n];
    FOR(bid, 1, Bcnt){
        B[bid].bg = (bid - 1) * blo + 1;
        B[bid].ed = bid == Bcnt ? n : bid * blo;
        B[bid].build();
    }
}

int main(){
    n = read(), m = read(), blo = ceil(sqrt(n));
    init();
    Rint sta, l, r, x;
    FOR(o, 1, m){
        sta = read() - 1, l = read(), r = read(), x = read();
        sta ? (void)printf("%d\n", query(l, r, x)) : update(l, r, x);
    }
    return VSC_Local();
}

参考资料

据说询问区间某个数的 rank 也可做？然而我太弱了并不会

lxl 原博客