洛谷 4117 「Ynoi 2018」五彩斑斓的世界

发表于 | 分类于 | 19

「突刺贯穿的第二分块」。

和隔壁第一分块差不多吧（

对于一个块，设最大值为 k，进行参数为 x 的修改操作。
若 k≤2x，则只需要将值域区间 (x,k] 合并到 [1,k−x] 上，那么此时操作完后 k 至少减小 k−x，并且需要合并的数值也是 O(k−x) 种的。
若 k>2x，则只需要将值域区间 [1,x] 合并到 [x,2x] 上，再打上区间减 x 的标记，那么此时操作完后 k 至少减小 x，并且需要合并的数值也是 O(x) 种的。
也即，每次操作后 k 是不增的，并且需要合并的数值也是减少的值级别的。
也就是最终要合并的数值的种类总共是值域级别的。

那么如何 O(1) 合并两个值？
并查集即可，同时简单地维护一下每个块内每个值的个数。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 5e5;
const int BLK = 921;
const int CNT = N / BLK + 1;
int n,m,block;
int a[N + 5],pos[N + 5];
int fa[N + 5],fir[N + 5],mx,tag;
int cnt[N + 5];
inline int get(int x)
{
    return !fa[x] ? x : (fa[x] = get(fa[x]));
}
struct s_query
{
    int op,l,r,x,ans;
} qry[N + 5];
inline void merge(int x,int y)
{
    if(!fir[x])
        return ;
    a[fir[x]] = y;
    if(cnt[x] > cnt[y] || !fir[y])
        fir[y] && (fa[fir[y]] = fir[x]),fir[y] = fir[x];
    else
        fa[fir[x]] = fir[y];
    cnt[y] += cnt[x],cnt[x] = fir[x] = 0;
}
void solve(int p)
{
    memset(fir,0,sizeof fir),memset(cnt,0,sizeof cnt),mx = tag = 0;
    for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
        !fir[a[i]] ? (fir[a[i]] = i,fa[i] = 0) : (fa[i] = fir[a[i]]),++cnt[a[i]],mx = max(mx,a[i]);
    for(register int i = 1;i <= m;++i)
    {
        int op = qry[i].op,l = qry[i].l,r = qry[i].r,x = qry[i].x,&ans = qry[i].ans;
        if(p == pos[l])
        {
            if(op == 1)
            {
                for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
                    fir[a[i] = a[get(i)]] = 0,--cnt[a[i]];
                for(register int i = l;i <= min(p * block,r);++i)
                    a[i] - tag > x && (a[i] -= x);
                mx = 0;
                for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
                    !fir[a[i]] ? (fir[a[i]] = i,fa[i] = 0) : (fa[i] = fir[a[i]]),++cnt[a[i]],mx = max(mx,a[i] - tag);
            }
            else
                for(register int i = l;i <= min(p * block,r);++i)
                    a[get(i)] - tag == x && ++ans;
        }
        else if(p == pos[r])
        {
            if(op == 1)
            {
                for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
                    fir[a[i] = a[get(i)]] = 0,--cnt[a[i]];
                for(register int i = (p - 1) * block + 1;i <= r;++i)
                    a[i] - tag > x && (a[i] -= x);
                mx = 0;
                for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
                    !fir[a[i]] ? (fir[a[i]] = i,fa[i] = 0) : (fa[i] = fir[a[i]]),++cnt[a[i]],mx = max(mx,a[i] - tag);
            }
            else
                for(register int i = (p - 1) * block + 1;i <= r;++i)
                    a[get(i)] - tag == x && ++ans;
        }
        else if(p > pos[l] && p < pos[r])
        {
            if(op == 1)
            {
                if(mx <= x * 2)
                {
                    for(register int i = x + tag + 1;i <= mx + tag;++i)
                        merge(i,i - x);
                    mx > x && (mx -= x,mx = max(mx,x));
                }
                else
                {
                    for(register int i = tag + 1;i <= x + tag;++i)
                        merge(i,i + x);
                    mx -= x,tag += x;
                }
            }
            else
                x + tag <= N && (ans += cnt[x + tag]);
        }
    }
}
int main()
{
    read(n),read(m),block = BLK;
    for(register int i = 1;i <= n;++i)
        read(a[i]),pos[i] = (i - 1) / block + 1;
    for(register int i = 1;i <= m;++i)
        read(qry[i].op),read(qry[i].l),read(qry[i].r),read(qry[i].x);
    for(register int i = 1;i <= pos[n];++i)
        solve(i);
    for(register int i = 1;i <= m;++i)
        qry[i].op == 2 && printf("%d\n",qry[i].ans);
}

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!