其实做过由乃打扑克的话思路并不难。但写代码的时候把写由乃打扑克的 bug 全部复现了属实难蚌
注意到线段树不同区间长度是 \(O(\log n)\) 的，因此我们对于每种长度建一个序列，对于 1 操作，同一长度的区间，中间一段被全部包含，加上的值都是 \(len\times a\)，旁边两个小区间需要特判。
那么就是区间加区间求 \(\le x\) 的数的个数，套用由乃打扑克那题的做法，散块修改后暴力归并，整块打 tag，查询二分剪枝（询问值不在块的值域范围内跳过）即可。
块长我直接取根号序列长度，直接过了。
Code
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#include <cmath>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=1e9+7;
inline int plust(int x, int y){x+=y;if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline int minut(int x, int y){x-=y;if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline int read(){
char ch=getchar();int x=0, f=1;
while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0) putchar('-'), x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
int ret=1;
for(; b; b>>=1, a=1ll*a*a%cp)
if(b&1) ret=1ll*ret*a%cp;
return ret;
}
const int N=1e5+5;
int n, m, vis[N], tot, LEN[50];
int b[N], c[N], bt, ct;
struct BLOCK{
int trid, len, block;
vector <ll> val, tag;
vi ranl, ranr, id, bid, L, R;
Pii find(int l, int r){
int x=lower_bound(ranl.begin(), ranl.end(), l)-ranl.begin();
int y=upper_bound(ranr.begin(), ranr.end(), r)-ranr.begin()-1;
return mp(x, y);
}
void build(int pid){
trid=pid;
len=(ranl.size()+ranr.size())>>1;block=sqrt(len);
id.resize(len), bid.resize(len), val.resize(len);
for(int i=0, j, c=0; i<len; i+=block){
for(j=0; j<block&&i+j<len; ++j)
bid[i+j]=c, id[i+j]=i+j;
tag.pb(0);++c;
L.pb(i), R.pb(min(i+block-1, len-1));
}
}
void rebuild(int idx, int l, int r, ll v){
for(int i=l; i<=r; ++i) val[i]+=v;bt=ct=0;
for(int i=L[idx]; i<=R[idx]; ++i)
if(l<=id[i]&&id[i]<=r) b[++bt]=id[i];
else c[++ct]=id[i];
int bs=1, cs=1;
for(int i=L[idx]; i<=R[idx]; ++i)
if(bs<=bt&&cs<=ct)
id[i]=((val[b[bs]]<val[c[cs]])?b[bs++]:c[cs++]);
else if(bs<=bt) id[i]=b[bs++];
else if(cs<=ct) id[i]=c[cs++];
return ;
}
void Modify(int l, int r, ll v){
if(bid[l]==bid[r]) return rebuild(bid[l+r>>1], l, r, v);
rebuild(bid[l], l, R[bid[l]], v);
rebuild(bid[r], L[bid[r]], r, v);
for(int i=bid[l]+1; i<=bid[r]-1; ++i) tag[i]+=v;
}
void check(int id, int l, int r, ll v){
if(id<0||id>=len) return ;if(ranl[id]<=l&&r<=ranr[id]) return rebuild(bid[id], id, id, v*(r-l+1));
if(ranr[id]>=l&&ranl[id]<l) return rebuild(bid[id], id, id, v*(ranr[id]-l+1));
if(ranl[id]<=r&&ranr[id]>r) return rebuild(bid[id], id, id, v*(r-ranl[id]+1));
}
int Fcnt(int idx, int l, int r, ll v){
int res=0;
for(int i=l; i<=r; ++i) res+=((val[i]+tag[idx])<=v);
return res;
}
int Ef(int idx, ll v){
if(val[id[L[idx]]]>v) return 0;
if(val[id[R[idx]]]<=v) return R[idx]-L[idx]+1;
int l=L[idx], r=R[idx], ans=L[idx]-1;
while(l<=r){
int mid=l+r>>1;
if(val[id[mid]]<=v) ans=mid, l=mid+1;
else r=mid-1;
}
return ans-L[idx]+1;
}
int Query(int l, int r, ll v){
if(bid[l]==bid[r]) return Fcnt(bid[l+r>>1], l, r, v);
int res=Fcnt(bid[l], l, R[bid[l]], v)+Fcnt(bid[r], L[bid[r]], r, v);
for(int i=bid[l]+1; i<=bid[r]-1; ++i) res+=Ef(i, v-tag[i]);
return res;
}
}tr[50];
#define mid (l+r>>1)
void build(int l, int r){
if(!vis[r-l+1]) vis[r-l+1]=tot++, LEN[tot-1]=r-l+1;
tr[vis[r-l+1]].ranl.pb(l);
tr[vis[r-l+1]].ranr.pb(r);
if(l==r) return ;
build(l, mid), build(mid+1, r);
}
#undef mid
signed main(){
n=read(), m=read();
build(1, n);
for(int i=0; i<tot; ++i) tr[i].build(i);
for(int i=1; i<=m; ++i){
int op=read(), l=read(), r=read(), a=read();
if(op&1){
for(int j=0; j<tot; ++j){
Pii t=tr[j].find(l, r);
if(t.st<=t.nd) tr[j].Modify(t.st, t.nd, 1ll*a*LEN[j]);
tr[j].check(t.st-1, l, r, a);
if(t.st-1!=t.nd+1) tr[j].check(t.nd+1, l, r, a);
}
}
else{
int ans=0;
for(int j=0; j<tot; ++j){
Pii t=tr[j].find(l, r);
if(t.st<=t.nd) ans+=tr[j].Query(t.st, t.nd, a);
}
printf("%d\n", ans);
}
}
return 0;
}