洛谷 6578. 「Ynoi 2019」魔法少女网站

第十分块。

看到题第一反应肯定是想把询问按排序。
但是有修改。
假设能较快地支持一次修改，那么如果直接暴力类似带修莫队在上一次询问的基础上转移的话，复杂度是的。

这启发我们什么？
莫队。
然而，虽然它是标算，但我还不会（
所以把操作分块。每个操作处理一次。

于是现在需要支持较快地修改。
假如没有额外的修改操作，我们需要支持的就是维护一个序列，支持把变成，询问区间内所有极长的连续段的子区间个数之和。
考虑分块。
这个分块相对比较简单：只需要考虑维护所有块内的极长连续段，在左端点处记录右端点，右端点处记录左端点，并记录块内的答案。
这里为了便于区间询问，记录块内答案时不记录在块的边界上的连续段的贡献。
然后区间询问就是一个经典 PJ 操作。
这个分块不难实现修改询问，而同时也应当注意到我们的修改次数大致是，所以这里达成了一种平衡。

下一个问题：额外的修改可能把变成，怎么办呢？
注意到最多只有次本质不同的额外的修改，然后又发现这个分块容易支持撤销上一次操作。
于是可以得到这样一个想法：在一般地按照权值把变成的过程中，不考虑被修改的位置；在处理询问时暴力判断每个被修改的位置是否需要变为，回答询问后撤回。
这样就可以了。

时间复杂度，视同阶（其实是懒得算了吧）。

然而卡常力度略微有点大。
感谢松式基排，它实在是太香了！

代码：

#include <cstdio>
#include <vector>
#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 = 3e5;
const int BLK = 700;
const int CNT = N / BLK + 1;
const int LIM = 2500;
int n,m;
int block,lim;
int a[N + 5],pos[N + 5];
int vis[N + 5];
vector<int> modified;
struct note
{
    int x,v;
} b[N + 5];
struct s_change
{
    int x,v;
} chg[LIM + 5];
struct s_query
{
    int l,r,v,id,t;
} qry[LIM + 5];
int chg_tot,qry_tot;
long long ans[LIM + 5];
namespace BLOCK
{
    int a[N + 5],w[N + 5];
    long long sum[CNT + 5];
    int tot;
    struct note
    {
        int x,l,r;
        long long s;
    } temp[LIM + 5];
    inline void update(int x,int flag = 0)
    {
        register const int p = pos[x],L = (p - 1) * block + 1,R = min(p * block,n);
        register const int l = L < x && w[x - 1] ? w[x - 1] : x,r = R > x && w[x + 1] ? w[x + 1] : x;
        flag && (temp[++tot] = (note){x,l,r,sum[p]},1);
        a[x] = 1;
        L < x && (w[x - 1] = 0),x < R && (w[x + 1] = 0),
        w[l] = r,w[r] = l,
        L < l && (sum[p] -= (long long)(x - l) * (x - l + 1) >> 1),
        R > r && (sum[p] -= (long long)(r - x) * (r - x + 1) >> 1),
        L < l && R > r && (sum[p] += (long long)(r - l + 1) * (r - l + 2) >> 1);
    }
    inline void cancel()
    {
        for(;tot;--tot)
        {
            register const int x = temp[tot].x,l = temp[tot].l,r = temp[tot].r;
            register const int p = pos[x],L = (p - 1) * block + 1,R = min(p * block,n);
            w[x] = a[x] = 0,
            l < x && (w[l] = x - 1,w[x - 1] = l),
            r > x && (w[r] = x + 1,w[x + 1] = r),
            sum[p] = temp[tot].s;
        }
    }
    inline long long query(int l,int r)
    {
        long long ret = 0;
        register int cur = 0;
        for(register int i = l;i <= min(pos[l] * block,r);++i)
            a[i] && !cur && (cur = i),
            !a[i] && cur && (ret += (long long)(i - cur) * (i - cur + 1) >> 1,cur = 0);
        if(pos[l] ^ pos[r])
        {
            for(register int p = pos[l] + 1,L,R,x;p < pos[r];++p)
            {
                L = (p - 1) * block + 1,R = min(p * block,n);
                ret += sum[p];
                if(w[L] ^ R)
                    !a[L] && cur && (ret += (long long)(L - cur) * (L - cur + 1) >> 1),
                    a[L] && cur && (ret += (long long)(w[L] - cur + 1) * (w[L] - cur + 2) >> 1),
                    a[L] && !cur && (ret += (long long)(w[L] - L + 1) * (w[L] - L + 2) >> 1),
                    cur = w[R];
                else
                    !cur && (cur = L);
            }
            for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
                a[i] && !cur && (cur = i),
                !a[i] && cur && (ret += (long long)(i - cur) * (i - cur + 1) >> 1,cur = 0);
        }
        cur && (ret += (long long)(r - cur + 1) * (r - cur + 2) >> 1);
        return ret;
    }
    inline void clear()
    {
        memset(a,0,sizeof a),memset(w,0,sizeof w),memset(sum,0,sizeof sum);
    }
}
namespace SORT
{
    const int B = 9;
    const int W = 1 << B;
    int a[N + 5],b[N + 5];
    int c[W + 5];
    template<class T>
    inline void sort(T *w,int n)
    {
        T temp[N + 5];
        int *x = a,*y = b;
        for(register int i = 1;i <= n;++i)
            x[i] = i,temp[i] = w[i];
        for(register int r = 0;1 << (r * B) <= N;++r)
        {
            for(register int i = 0;i < W;++i)
                c[i] = 0;
            for(register int i = 1;i <= n;++i)
                ++c[(w[x[i]].v >> (r * B)) & (W - 1)];
            for(register int i = 1;i < W;++i)
                c[i] += c[i - 1];
            for(register int i = n;i;--i)
                y[c[(w[x[i]].v >> (r * B)) & (W - 1)]--] = x[i];
            swap(x,y);
        }
        for(register int i = 1;i <= n;++i)
            w[i] = temp[x[i]];
    }
}
void solve()
{
    register int cnt = 0;
    for(register int i = 1;i <= n;++i)
        !vis[i] && (b[++cnt] = (note){i,a[i]},1);
    SORT::sort(b,cnt),SORT::sort(qry,qry_tot);
    register int t = 0;
    for(register int i = 1,j = 1;i <= qry_tot;++i)
    {
        for(;j <= cnt && b[j].v <= qry[i].v;++j)
            BLOCK::update(b[j].x);
        for(;t < qry[i].t;)
            ++t,swap(a[chg[t].x],chg[t].v);
        for(;t > qry[i].t;)
            swap(a[chg[t].x],chg[t].v),--t;
        for(register int x : modified)
            a[x] <= qry[i].v && (BLOCK::update(x,1),1);
        ans[qry[i].id] = BLOCK::query(qry[i].l,qry[i].r);
        BLOCK::cancel();
    }
    for(;t < chg_tot;)
        ++t,swap(a[chg[t].x],chg[t].v);
    for(register int i = 1;i <= qry_tot;++i)
        printf("%lld\n",ans[i]);
}
int main()
{
    read(n),read(m),block = BLK,lim = LIM;
    for(register int i = 1;i <= n;++i)
        read(a[i]),pos[i] = (i - 1) / block + 1;
    int op,x,y,k;
    for(register int i = 1;i <= m;++i)
    {
        read(op),read(x),read(y);
        if(op == 2)
            read(k),qry[++qry_tot] = (s_query){x,y,k,qry_tot,chg_tot};
        else
            chg[++chg_tot] = (s_change){x,y},!vis[x] && (modified.push_back(x),vis[x] = 1);
        if(!(i % lim) || i == m)
            solve(),
            qry_tot = chg_tot = 0,memset(vis,0,sizeof vis),BLOCK::clear(),modified.clear();
    }
}

『My guiding star.』

洛谷 6578 「Ynoi 2019」魔法少女网站