题解 AT1828 【雇用計画】

· · 题解

先宣传一下博客(逃

解法

  这题标算是1个log的树状数组，然而由于数据范围（也许）没开满，本sb选手直接写了莫队硬肛2e5，差点被卡常了。（atcoder上最慢的点970ms）
  考虑我们是对一个评价值询问，把这个值作为一个维度，由于有修改所以时间也作为一个维度，我们就得到了一个二维的莫队。其中评价值维度上的移动会触发一次修改，是O(1)的，时间上的移动完整的移动一次会触发O(n)次修改，所以均摊复杂度O(1)。所以分块时如果要按时间轴分块，必须按该时间的修改次数的前缀和分块，而不是按时间分块。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

template <size_t _I_Buffer_Size = 1 << 23, size_t _O_Buffer_Size = 1 << 23>
struct IO_Tp
{
    //这是读入优化板子，为了阅读体验此部分内容省略。
};
 IO_Tp<1<<25,1<<25> IO;
const int maxn = 200000;
struct Change
{
    int p, before, after;
} ch[maxn + 10];
int a[maxn + 10];
struct Query
{
    int l, r, id;
} q[maxn + 10];
int qcnt, ccnt;
int tong[3 * maxn + 10], tcnt;
vector<int> pl[3 * maxn + 10];
int n, m;
int nans;
int l = ccnt, r = tcnt;
bool b[maxn + 10];
void change(int p, int k)
{
    int cnt = 0;
    if (b[p - 1])
        ++cnt;
    if (b[p + 1])
        ++cnt;
    if (k == 1) {
        if (cnt == 0)
            ++nans;
        else if (cnt == 2)
            --nans;
        massert(!b[p]);
        b[p] = true;
    } else {
        if (cnt == 0)
            --nans;
        else if (cnt == 2)
            ++nans;
        massert(b[p]);
        b[p] = false;
    }
}
void movl(int l, int k)
{
    if (ch[l].before <= r && ch[l].after > r)
        change(ch[l].p, k);
    else if (ch[l].before > r && ch[l].after <= r)
        change(ch[l].p, k ^ 1);
    if (k == 1) {
        a[ch[l].p] = ch[l].after;
    } else {
        a[ch[l].p] = ch[l].before;
    }
}
void movr(int r, int k)
{
    for (auto i : pl[r]) {
        if (a[i] == r)
            change(i, k);
    }
}
int ans[maxn + 10];
int sum[maxn+10];
int main()
{
    iopen();
    IO >> n >> m;
    for (int i = 1; i <= n; ++i) {
        IO >> a[i];
        tong[++tcnt] = a[i];
    }
    for (int i = 1; i <= m; ++i) {
        int op;
        IO >> op;
        if (op == 1) {
            int b;
            IO >> b;
            --b;
            tong[++tcnt] = b;
            ++qcnt;
            q[qcnt] = { ccnt, b, qcnt };
        } else {
            int p, after;
            IO >> p >> after;
            ch[++ccnt] = { p, a[p], after };
            tong[++tcnt] = after;
            a[p] = after;
        }
    }
    sort(tong + 1, tong + 1 + tcnt);
    tcnt = unique(tong + 1, tong + 1 + tcnt) - tong - 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(tong + 1, tong + 1 + tcnt, a[i]) - tong;
    }
    for (int i = 1; i <= ccnt; ++i) {
        ch[i].before = lower_bound(tong + 1, tong + 1 + tcnt, ch[i].before) - tong;
        ch[i].after = lower_bound(tong + 1, tong + 1 + tcnt, ch[i].after) - tong;
    }
    for (int i = 1; i <= qcnt; ++i) {
        q[i].r = lower_bound(tong + 1, tong + 1 + tcnt, q[i].r) - tong;
    }
    for (int i = 1; i <= n; ++i) {
        pl[a[i]].push_back(i);
    }
    for (int i = 1; i <= ccnt; ++i) {
        pl[ch[i].before].push_back(ch[i].p);
    }
    for(int i=1; i<=tcnt; ++i) {
        sort(pl[i].begin(),pl[i].end());
        int t=unique(pl[i].begin(),pl[i].end())-pl[i].begin();
        while(pl[i].size()>t) pl[i].pop_back();
        sum[i]=sum[i-1]+t;
    }
    int S = sqrt(sum[tcnt]);
   sort(q + 1, q + 1 + qcnt, [S](const Query &a, const Query &b) {
        if (sum[a.r] / S == sum[b.r] / S)
            return (sum[a.r]/S %2 ==1)?a.l < b.l:a.l>b.l;
        return sum[a.r] / S < sum[b.r] / S;
    });
    l = ccnt;
    r = 0;
    memset(b, true, sizeof(b));
    b[0] = b[n + 1] = false;
    nans = 1;
    for (int i = 1; i <= qcnt; ++i) {
        while (l < q[i].l)
            movl(++l, 1);
        while (l > q[i].l)
            movl(l--, 0);
        while (r < q[i].r)
            movr(++r, 0);
        while (r > q[i].r)
            movr(r--, 1);
        ans[q[i].id] = nans;
    }
    for (int i = 1; i <= qcnt; ++i) {
        IO << ans[i] << '\n';
    }
    return 0;
}