洛谷 4119 「Ynoi 2018」未来日记

发表于 | 分类于 | 9

「望月悲叹的最初分块」。

区间第 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
120
121
122
#include <cstdio>
#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 = 1e5;
const int BLK = 633;
const int CNT = N / BLK + 1;
const int WBLK = 233;
const int WCNT = N / WBLK + 1;
int n,m,block,wblock;
int a[N + 5],pos[N + 5],wpos[N + 5],fa[N + 5];
int cnt[CNT + 5][WCNT + 5],wcnt[CNT + 5][N + 5];
int sum[CNT + 5][WCNT + 5],wsum[CNT + 5][N + 5];
int tcnt[WCNT + 5],tmp[N + 5];
int fir[CNT + 5][N + 5];
inline int get(int x)
{
    return !fa[x] ? x : (fa[x] = get(fa[x]));
}
void update(int l,int r,int x,int y)
{
    if(x == y)
        return ;
    for(register int p = pos[l] + 1;p < pos[r];++p)
        if(fir[p][x])
        {
            a[fir[p][x]] = y;
            if(wcnt[p][x] > wcnt[p][y] || !fir[p][y])
                fir[p][y] && (fa[fir[p][y]] = fir[p][x]),
                fir[p][y] = fir[p][x];
            else
                fa[fir[p][x]] = fir[p][y];
            cnt[p][wpos[x]] -= wcnt[p][x],cnt[p][wpos[y]] += wcnt[p][x],
            wcnt[p][y] += wcnt[p][x],wcnt[p][x] = 0,
            fir[p][x] = 0;
        }
    for(register int i = (pos[l] - 1) * block + 1;i <= min(pos[l] * block,n);++i)
        a[i] = a[get(i)];
    for(register int i = l;i <= min(pos[l] * block,r);++i)
        a[i] == x && (a[i] = y,--cnt[pos[l]][wpos[x]],++cnt[pos[l]][wpos[y]],--wcnt[pos[l]][x],++wcnt[pos[l]][y]);
    fir[pos[l]][x] = fir[pos[l]][y] = 0;
    for(register int i = (pos[l] - 1) * block + 1;i <= min(pos[l] * block,n);++i)
        if(a[i] == x || a[i] == y)
            !fir[pos[l]][a[i]] ? (fa[i] = 0,fir[pos[l]][a[i]] = i) : (fa[i] = fir[pos[l]][a[i]]);
    if(pos[l] ^ pos[r])
    {
        for(register int i = (pos[r] - 1) * block + 1;i <= min(pos[r] * block,n);++i)
            a[i] = a[get(i)];
        for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
            a[i] == x && (a[i] = y,--cnt[pos[r]][wpos[x]],++cnt[pos[r]][wpos[y]],--wcnt[pos[r]][x],++wcnt[pos[r]][y]);
        fir[pos[r]][x] = fir[pos[r]][y] = 0;
        for(register int i = (pos[r] - 1) * block + 1;i <= min(pos[r] * block,n);++i)
            if(a[i] == x || a[i] == y)
                !fir[pos[r]][a[i]] ? (fa[i] = 0,fir[pos[r]][a[i]] = i) : (fa[i] = fir[pos[r]][a[i]]);
    }
    for(register int i = 1;i <= pos[n];++i)
        sum[i][wpos[x]] = sum[i - 1][wpos[x]] + cnt[i][wpos[x]],
        sum[i][wpos[y]] = sum[i - 1][wpos[y]] + cnt[i][wpos[y]],
        wsum[i][x] = wsum[i - 1][x] + wcnt[i][x],
        wsum[i][y] = wsum[i - 1][y] + wcnt[i][y];
}
int query(int l,int r,int k)
{
    for(register int i = l;i <= min(pos[l] * block,r);++i)
        ++tcnt[wpos[a[get(i)]]],++tmp[a[get(i)]];
    if(pos[l] ^ pos[r])
        for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
            ++tcnt[wpos[a[get(i)]]],++tmp[a[get(i)]];
    int s = 0,ret;
    int L = pos[l],R = pos[r] - 1;
    L > R && (L = R = 0);
    for(register int i = 1;i <= wpos[N];++i)
        if(s + tcnt[i] + sum[R][i] - sum[L][i] >= k)
        {
            for(register int j = (i - 1) * wblock + 1;j <= min(i * wblock,N);++j)
                if((s += tmp[j] + wsum[R][j] - wsum[L][j]) >= k)
                {
                    ret = j;
                    break;
                }
            break;
        }
        else
            s += tcnt[i] + sum[R][i] - sum[L][i];
    for(register int i = l;i <= min(pos[l] * block,r);++i)
        --tcnt[wpos[a[get(i)]]],--tmp[a[get(i)]];
    if(pos[l] ^ pos[r])
        for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
            --tcnt[wpos[a[get(i)]]],--tmp[a[get(i)]];
    return ret;
}
int main()
{
    read(n),read(m),block = BLK,wblock = WBLK;
    for(register int i = 1;i <= N;++i)
        wpos[i] = (i - 1) / wblock + 1;
    for(register int i = 1;i <= n;++i)
        read(a[i]),pos[i] = (i - 1) / block + 1,
        !fir[pos[i]][a[i]] ? (fir[pos[i]][a[i]] = i) : (fa[i] = fir[pos[i]][a[i]]),
        ++cnt[pos[i]][wpos[a[i]]],++wcnt[pos[i]][a[i]];
    for(register int i = 1;i <= wpos[N];++i)
        for(register int j = 1;j <= pos[n];++j)
            sum[j][i] = sum[j - 1][i] + cnt[j][i];
    for(register int i = 1;i <= N;++i)
        for(register int j = 1;j <= pos[n];++j)
            wsum[j][i] = wsum[j - 1][i] + wcnt[j][i];
    for(int op,l,r,x,y;m;--m)
        read(op),read(l),read(r),read(x),op == 1 ? (read(y),update(l,r,x,y),1) : printf("%d\n",query(l,r,x));
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment