第二分块1

· · 题解

感觉再咕下去要出事情

【突刺贯穿の第二分块】

信仰/弱化版 CF链接
题目链接
lxl题解

Ynoi2018 Day1T1，虽然毒瘤但是和其他比相对简单，而且代码也不那么难

我们先考虑弱化版怎么做
看到1e5的数据，可以猜到他是\text n \sqrt \text n的做法。
可能存在\text {Polylog}的做法，但是估计比较难搞。
因为\text {Polylog}的做法还要处理区间无非是线段树/值域线段树，但是他们好像都很难对区间的值域进行操作。
可以试试树套树，反正我整不出来，你可以试一试……

那么我们考虑分块。
可以看出一个块内的操作只和这个块内部的值域和每个值有多少个数有关
那么我们用并查集来维护 

int fa[N],val[N];//val[i]表示以i为根的联通块的值
struct DSU
{
    int sz[N],id[N];
    inline int getfa(int x)
    {
        if (fa[x]==x) return x;
        return fa[x]=getfa(fa[x]);
    }
    inline void merge(int p,int x,int y)
    {
        if (id[y]) fa[id[x]+(p-1)*SZ]=id[y]+(p-1)*SZ;
        else
        {
            id[y]=id[x];
            val[id[y]+(p-1)*SZ]=y;
        }
        sz[y]+=sz[x];
        id[x]=sz[x]=0;
    }
}D[SZ+5];

然后我们对于边界上的块直接把它拆掉再重构

inline void Break(int P)
{
    //将第P个块拆散
    for (int i=(P-1)*SZ+1;i<=min(P*SZ,n);i++)
    {
        a[i]=val[D[P].getfa(i)];//查找j所在的联通块及其真实值
        D[P].sz[a[i]]=D[P].id[a[i]]=0;//清0
        a[i]-=tag[P];//还要减去区间移动的标记
    }
    for (int i=(P-1)*SZ+1;i<=min(P*SZ,n);i++) fa[i]=0;
    tag[P]=0;
}
inline void Build(int P)
{
    //重构第P个块
    Max[P]=0;
    for (int i=(P-1)*SZ+1;i<=P*SZ;i++)
    {
        Max[P]=max(Max[P],a[i]);//赋值区间最大值
        if (D[P].id[a[i]]==0)//如果这个块中a[i]的值没有出现过
        {//那就自己建一个联通块
            fa[i]=i;
            D[P].id[a[i]]=i-(P-1)*SZ;
            val[i]=a[i];
        } 
        else//不然把这个点并到联通块中
        fa[i]=D[P].id[a[i]]+(P-1)*SZ;
        D[P].sz[a[i]]++;
    }
}

为什么要存储区间最大值呢？区间移动的标记又是什么呢？对于整块的操作需要用到。
对于整块，有一个非常naive的想法，就是直接暴力枚举每一个值域，然后进行重新合并，这样的复杂度是\sqrt \text n的，显然不行

我们进行一些修补，如果x>Max就直接return掉
显然Max的大小会逐渐变小，那么最坏情况下每次都是1，那均摊还是\sqrt\text n，没用

显然，我们要在O(k)的时间内让Max的最大值减少k
大眼观察一下，估计要对x与Max的大小关系进行分类讨论

那么就用最naive的方式分类吧
如果2x>Max，那我们枚举所有[x+1,Max]，然后暴力修改，这样每次修改不超过x次，然后Max减少了x
如果2x\le Max，那么我们枚举所有[1,x]，然后把他们暴力移到[x+1,2x]上，然后打上tag，这样值域之间的相对位置是不变的，再运用tag就能求出真实值。这样每次修改x次，然后Max减少了x。
那么修改就很显然了 

inline void update(int P,int l,int r,int x)
{
    Break(P);//拆散
    for (int i=l;i<=r;i++) if (a[i]>x) a[i]-=x;//修改
    Build(P);//重构
}
inline void UPDATE(int P,int x)
{
    //修改整块
    if (Max[P]-tag[P]>=x*2)
    {
        for (int i=tag[P]+1;i<=tag[P]+x;i++) if (D[P].id[i]) D[P].merge(P,i,i+x);
        tag[P]+=x;
    }
    else
    {
        for (int i=Max[P];i>tag[P]+x;i--) if (D[P].id[i]) D[P].merge(P,i,i-x);
        Max[P]=min(tag[P]+x,Max[P]);
    }
}

那么查询也是显然的 

inline int query(int P,int l,int r,int x) //查询不完整的块
{
    int ans=0;
    for (int i=l;i<=r;i++)
        if (val[D[P].getfa(i)]-tag[P]==x) ans++;
    return ans;
}
inline int QUERY(int P,int x)//查询完整的块
{
    if (x+tag[P]>1e5+1) return 0;
    return D[P].sz[x+tag[P]];
}

完整代码： 

#include<bits/stdc++.h>
#define rd(x) x=read()
#define I inline
#define int long long
using namespace std;
I int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
const int N=1e5+405,SZ=320;

int fa[N],val[N];//val[i]表示以i为根的联通块的值
struct DSU
{
    int sz[N],id[N];
    I int getfa(int x)
    {
        if (fa[x]==x) return x;
        return fa[x]=getfa(fa[x]);
    }
    I void merge(int p,int x,int y)
    {
        if (id[y]) fa[id[x]+(p-1)*SZ]=id[y]+(p-1)*SZ;
        else
        {
            id[y]=id[x];
            val[id[y]+(p-1)*SZ]=y;
        }
        sz[y]+=sz[x];
        id[x]=sz[x]=0;
    }
}D[SZ+5];
int n,m;
int a[N];//原数组
int pos[N];//所在块
int Max[N];//最大值
int tag[N];//右移标记

I void Break(int P)
{
    //将第P个块拆散
    for (int j=(P-1)*SZ+1;j<=min(P*SZ,n);j++)
    {
        a[j]=val[D[P].getfa(j)];//查找j所在的联通块及其真实值
        D[P].sz[a[j]]=D[P].id[a[j]]=0;//清0
        a[j]-=tag[P];//还要减去区间移动的标记
    }
    for (int j=(P-1)*SZ+1;j<=min(P*SZ,n);j++) fa[j]=0;
    tag[P]=0;
}
I void Build(int P)
{
    //重构第P个块
    Max[P]=0;
    for (int i=(P-1)*SZ+1;i<=P*SZ;i++)
    {
        Max[P]=max(Max[P],a[i]);//赋值区间最大值
        if (D[P].id[a[i]]==0)//如果这个块中a[i]的值没有出现过
        {//那就自己建一个联通块
            fa[i]=i;
            D[P].id[a[i]]=i-(P-1)*SZ;
            val[i]=a[i];
        } 
        else//不然把这个点并到联通块中
        fa[i]=D[P].id[a[i]]+(P-1)*SZ;
        D[P].sz[a[i]]++;
    }
}
I void update(int P,int l,int r,int x)
{
    Break(P);//拆散
    for (int i=l;i<=r;i++) if (a[i]>x) a[i]-=x;//修改
    Build(P);//重构
}
I void UPDATE(int P,int x)
{
    //修改整块
    if (Max[P]-tag[P]>=x*2)
    {
        for (int i=tag[P]+1;i<=tag[P]+x;i++) if (D[P].id[i]) D[P].merge(P,i,i+x);
        tag[P]+=x;
    }
    else
    {
        for (int i=Max[P];i>tag[P]+x;i--) if (D[P].id[i]) D[P].merge(P,i,i-x);
        Max[P]=min(tag[P]+x,Max[P]);
    }
}
I int query(int P,int l,int r,int x) //查询不完整的块
{
    int ans=0;
    for (int i=l;i<=r;i++)
        if (val[D[P].getfa(i)]-tag[P]==x) ans++;
    return ans;
}
I int QUERY(int P,int x)//查询完整的块
{
    if (x+tag[P]>1e5+1) return 0;
    return D[P].sz[x+tag[P]];
}

signed main()
{
    rd(n);rd(m);
    for (int i=1;i<=n;i++) rd(a[i]);
    for (int i=1;i<=n;i++) pos[i]=(i-1)/SZ+1;
    for (int i=1;i<=pos[n];i++) Build(i);
    while (m--)
    {
        int opt,l,r,x;
        rd(opt);rd(l);rd(r);rd(x);
        if (opt==1)
        {
            int Pl=pos[l],Pr=pos[r];
            if (Pl==Pr) update(Pl,l,r,x);
            else 
            {
                update(Pl,l,Pl*SZ,x);
                update(Pr,(Pr-1)*SZ+1,r,x);
                for (int i=Pl+1;i<=Pr-1;i++) UPDATE(i,x);
            }
        } else
        {
            int Pl=pos[l],Pr=pos[r];
            if (Pl==Pr) printf("%lld\n",query(Pl,l,r,x));
            else
            {
                int ans=query(Pl,l,Pl*SZ,x);
                ans+=query(Pr,(Pr-1)*SZ+1,r,x);
                for (int i=Pl+1;i<=Pr-1;i++) ans+=QUERY(i,x);
                printf("%lld\n",ans);
            }
        }
    } 
}

那么这样就可以通过CF896E啦 后续部分（P4117题解）