自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 22:06:43，当前版本为作者最后更新于2019-01-04 17:37:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

表示ynoi的分块题不加剪枝是绝对过不去的……

我连4680的剪枝都剪过还会怂这题？

---

前置芝士:线段树

其实只要会按照题意模拟建线段树就行了……

我平常惯用的是左开右闭的线段树，不过这题给出的线段树是闭区间的线段树

本题题解

好的我们一看这题发现我们不再维护序列而是在维护线段树了……

那么我们仔细观察一下线段树有什么优美性质可以让我们利用呢？

我们仔细观察了一下，发现并没有……

看起来我们的思考陷入了僵局，所以让我们来思考这个问题的一个简化版本，如果我们维护的不是线段树而是一个序列，我们的操作会变成什么呢？

1.区间加

2.询问区间里有多少个数字比x小

这好像是个分块的经典问题啊……我们将序列分成$O(\sqrt{n})$块，然后每个块维护一个块中数字排好序的数组以及一个加法标记，我们修改的时候暴力的重构零散的块，对于整块我们直接打标记

然后我们询问的时候边角暴力然后对于一个整块直接二分就行了

这样做的复杂度就是$O(NlogN\sqrt{N})$的

接下来我们发现这个东西并不能搬到线段树上，我们发现区间+x的时候线段树上每个节点的值会变化$len×x$其中$len$为这个线段树节点长度，即使我们对于线段树上节点的size分类讨论，想要套用刚才的分块算法，我们会发现仅仅是一个简单的区间加法就能够破坏我们的有序性质

不过既然提到的每个节点的len值我们就会发现一个非常有趣的性质

当我们区间的长度是2的整次幂的时候我们会发现len的取值只有log种……这个当然十分显然

那么让我们把目光放到一般的线段树上，我们发现一个肥肠有趣的性质，通过打表可以得到，在线段树的长度小于$10^5$的时候，这个线段树最多有33种(应该是这个数，可能稍有浮动)本质不同的节点长度

所以看起来我们可以把节点长度相等的节点拉出来看成一个序列

这样我们似乎可以for每种不同的区间长度然后去跑刚才在序列上的暴力……

具体点来讲当我们执行区间$(l,r)$加x的时候，我们枚举每一种不同的节点长度$len$，此时我们把所有长度为len的节点按照左端点排好序(其实右端点也可以，毕竟长度一样的节点一定互不包含，线段树上的区间又不存在相交关系)这些节点就形成了一个序列

此时我们发现只有比较靠近$l$和$r$的节点增加的值不是$len×x$因为l和r可能没有完全包含这个节点，

其他被$(l,r)$完全包含的节点的权值一定增加了$len×x$，所以$(l,r)$区间$+x$就变成了两个单点修改操作和一个区间加操作，这些操作当然是可以套用我们在序列上的分块算法的

而我们查询的时候当然也可以枚举节点的长度，依然是零散的块暴力然后在整块上二分答案查找就可以了

看起来我们的算法复杂度是$O(Nlog^2{n}\sqrt{N})$但是我们发现线段树的每一层最多有两种不同的节点长度

所以我们发现我们一次操作的复杂度其实是

$$\sum_{i}\sqrt{\frac{n}{2^{i}}}(log(n)-i)$$

的，这个东西稍微近似一下会发现它的复杂度其实是

$O(\sqrt{N}logn)$

只是常数稍微大了几圈而已，因此我们的总复杂度就是$O(N\sqrt{N}logn)$

说的很漂亮实际一写您发现这个分块细节不是一般的多并且内存分配也十分令人头大……

等您终于调完140行+的代码之后您发现您tle了……

如果朴素实现上述的算法显然不符合ynoi的风格

我们发现每次给零散块的加的时候都是这个块中的一些元素+了va，那么这些元素之间的相对有序性不变，因此我们可以使用归并而不是sort来重构整个块，这样重构的复杂度就变成了$O(n)$

对于单点修改我们暴力的把这个点插入到原来的有序数列里就行了，或者你也可以不断swap直到找到一个合适的位置复杂度依然$O(n)$

那么我们就可以蛇皮的调一下块长把我们的复杂度降至$O(N\sqrt{Nlogn})$

我的垃圾归并常数过大了所以我的块长是丢人的$1.3\sqrt{N}$各位神仙可以根据自己的常数大小自行三分出最优块长

然后我们发现这样交上去还是tle，大概分数是在55到85之间

我们发现还需要压榨一些询问方面的复杂度，很遗憾的是询问的复杂度并不能被继续压榨了……

所以我们还是老老实实的剪枝好了……

其实我们只需要一个非常简单的剪枝就可以过了这题，判断一下询问的x是否大于最大值或者小于最小值，如果两个条件满足其一就返回0或者是块长，否则我们就大力二分

事实证明这个剪枝相当好使，然后我们就可以通过这题了~

其实这题思路非常简单就是实现的细节十分难受

上代码~

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;const int N=1e5+10;typedef long long ll;int n;int m;
namespace INPUT_SPACE{
    const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
    char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
    inline int inn()
    {
        int x,ch,sgn=1;while(((ch=gc())<'0'||ch>'9')&&ch!='-');
        if(ch=='-') sgn=-1,x=0;else x=ch^'0';
        while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');
        return x*sgn;
    }
}using INPUT_SPACE::inn;
template <typename T>//这里直接用指针+数组分配内存 
inline void gm(T* & p,int siz,T* & op){op=p;p=p+siz+1;}
ll* S_t;int* A_t;ll S_bas[15*N];int A_bas[20*N];int q[N];ll* SA;
inline bool cmp(int x,int y){return SA[x]<SA[y];}
struct blk
{
    ll* a;int* sr;int* sr1;int siz;ll add;int pl;int pr;
    inline ll& operator [](const int& x){return a[x];}
    inline void ih()//初始化内存 
    {
        gm(S_t,siz,a);gm(A_t,siz,sr);gm(A_t,siz,sr1);
    	for(int i=1;i<=siz;i++)sr[i]=i;
    }
    inline void rebuild(int l,int r,int pos)//归并 
    {
        for(int i=1;i<=siz;i++)a[i]+=add;add=0;
        int hd1=0;int hd=0;int op=0;
        for(int i=1;i<=siz;i++)
            if(sr[i]!=pos)((l<=sr[i]&&sr[i]<=r)?sr[++hd1]:q[++hd])=sr[i];
        int i=1;int j=1;
        while(i<=hd1&&j<=hd)sr1[++op]=((a[sr[i]]<a[q[j]])?sr[i++]:q[j++]);
        while(i<=hd1)sr1[++op]=sr[i++];while(j<=hd)sr1[++op]=q[j++];
        int ins=1;
        if(ins<=siz-1&&a[sr1[1]]<a[pos])
        {
            int l=1;int r=siz-1;
            while(l!=r){int mid=(l+r+1)>>1;if(a[sr1[mid]]<a[pos])l=mid;else r=mid-1;}
            ins=l+1;
        }for(int i=1;i<ins;i++)sr[i]=sr1[i];sr[ins]=pos;
        for(int i=ins;i<=siz-1;i++)sr[i+1]=sr1[i];
    }
    inline void brurebuild()
    {for(int i=1;i<=siz;i++)a[i]+=add;add=0;SA=a;sort(sr+1,sr+siz+1,cmp);}
    inline int qry(ll x)//询问 
    {
        int l=0;int r=siz;x-=add;
        if(x<a[sr[1]])return 0;if(x>=a[sr[siz]])return siz;
        while(l!=r){int mid=(l+r+1)>>1;if(a[sr[mid]]<=x)l=mid;else r=mid-1;}
        return l;
    }
    inline int brucalc(int l,int r,ll x)
    {int ret=0;x-=add;for(int i=l;i<=r;i++)ret+=(a[i]<=x);return ret;}
    inline void lb_add(ll del){add+=del;} 
}B_bas[N];blk* B_t;
struct blk_arr
{
    int tot;int* bi;int* bj;blk* bl;int* al;int* ar;int gl[N];int gr[N];int B;
    inline void ih()//分配内存 
    {
        gm(A_t,tot,bi);gm(A_t,tot,bj);gm(A_t,tot,al);gm(A_t,tot,ar);B=sqrt(tot)*1.3;
        for(int i=1;i<=tot;i++)bi[i]=(i-1)/B+1;for(int i=1;i<=tot;i++)bj[i]=(i-1)%B+1;
        gm(B_t,bi[tot],bl);for(int i=1;i<bi[tot];i++)bl[i].siz=B;
        bl[bi[tot]].siz=((tot%B)?tot%B:B);
        for(int i=1;i<=bi[tot];i++)bl[i].ih();tot=0;
    }
    inline void pb(const int& l,const int& r){al[++tot]=l;ar[tot]=r;}
    inline void calcg()//这里预处理的实际询问的点和序列上的点的映射 
    {
        for(int i=1;i<=n+1;i++)gl[i]=0x3f3f3f3f;for(int i=1;i<=tot;i++)gl[ar[i]]=i;
        for(int i=1;i<=tot;i++)gr[al[i]]=i;for(int i=n;i>=1;i--)gl[i]=min(gl[i],gl[i+1]);
        for(int i=1;i<=n;i++)gr[i]=max(gr[i],gr[i-1]);
    }
    inline bool aju(int& l,int& r)
    {r=min(r,ar[tot]);l=max(l,al[1]);return (l<=r);}
    inline void stadd(int l,int r,ll x,ll va)//分各种情况讨论，相当恶心大家还是自己颓吧 
    {
        if(aju(l,r)==false)return;int tl=gl[l];int tr=gr[r];if(tl>tr)return;
        l=max(l,al[tl]);r=min(r,ar[tr]);
        if(tl==tr){bl[bi[tl]][bj[tl]]+=(r-l+1)*x;bl[bi[tl]].rebuild(0,0,bj[tl]);return;}
        int p1=bi[tl];int p2=bi[tr];
        bl[p1][bj[tl]]+=(ar[tl]-l+1)*x;bl[p2][bj[tr]]+=(r-al[tr]+1)*x;
        if(p1==p2){for(int i=tl+1;i<tr;i++)bl[p1][bj[i]]+=va;bl[p1].brurebuild();return;}
        for(int i=tl+1;bi[i]==p1;i++)bl[p1][bj[i]]+=va;
        for(int i=tr-1;bi[i]==p2;i--)bl[p2][bj[i]]+=va;
        bl[p1].rebuild(bj[tl]+1,bl[p1].siz,bj[tl]);
        bl[p2].rebuild(1,bj[tr]-1,bj[tr]);
        for(int i=p1+1;i<p2;i++)bl[i].lb_add(va);
    }
    inline int qry(int l,int r,ll x)//询问也是分情况讨论 
    {
        if(aju(l,r)==false)return 0;int tl=gl[l];int tr=gr[r];
        if(l>al[tl])tl++;if(r<ar[tr])tr--;if(tl>tr)return 0;
        int p1=bi[tl];int p2=bi[tr];
        if(p1==p2){return bl[p1].brucalc(bj[tl],bj[tr],x);}int ret=0;
        ret=bl[p1].brucalc(bj[tl],bl[p1].siz,x)+bl[p2].brucalc(1,bj[tr],x);
        for(int i=p1+1;i<p2;i++)ret+=bl[i].qry(x);return ret;
    }
}ds[35];int lim[35];int cnt;
inline void dfs1(int l,int r)//预先分配size 
{
    if(l>r)return;int va=r-l+1;int mid=(l+r)>>1;
    for(int i=1;i<=cnt;i++)if(lim[i]==va){ds[i].tot++;goto ed;}
    lim[++cnt]=va;ds[cnt].tot++;
    ed:;if(r!=l){dfs1(l,mid);dfs1(mid+1,r);}
}
inline void dfs2(int l,int r)//处理区间 
{
    if(l>r)return;int va=r-l+1;int mid=(l+r)>>1;
    for(int i=1;i<=cnt;i++)if(lim[i]==va){ds[i].pb(l,r);break;}
    if(r!=l){dfs2(l,mid);dfs2(mid+1,r);}
}
int main()
{
//	freopen("tst.txt","r",stdin);freopen("run.txt","w",stdout);
    S_t=S_bas;A_t=A_bas;B_t=B_bas;n=inn();m=inn();
    dfs1(1,n);for(int i=1;i<=cnt;i++)ds[i].ih();dfs2(1,n);
    for(int i=1;i<=cnt;i++)ds[i].calcg();
    for(int rd=1,tp,l,r,x;rd<=m;rd++)
    {
        tp=inn();l=inn();r=inn();x=inn();
        if(tp==1){for(int i=1;i<=cnt;i++)ds[i].stadd(l,r,x,(ll)lim[i]*x);}
        else 
        {
            int ret=0;for(int i=1;i<=cnt;i++)ret+=ds[i].qry(l,r,x);
            printf("%d\n",ret);
        }
    }return 0;//拜拜程序~ 
}