提交记录

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
template<typename T>
void read(T& x){
	char c=getchar();bool a=0;x=0;
	while(!isdigit(c)){
		if(c=='-') a^=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	if(a) x*=-1;
	return;
}
template<typename T,typename ...Args>
void read(T& x,Args&... args){
	read(x),read(args...);
	return; 
}

#define SQRT ((int)325)
#define LOG ((int)40)
#define N ((int)1e5)
//#define DBG

int n,m,tot;
/*
n,m:如题
tot:节点长度不同的序列数 
*/
int p[N+10];
struct Sequence{
	int cnt,tot;
	/*
	cnt:序列中节点数 
	tot:序列中块数 
	*/
	struct Node{
		int l,r,v;
		bool operator<(const Node &b)const{
			return v<b.v;
		}
	}ss[N+10];
	struct Block{
		int l,r,ll,rr,lazy;
	}pp[SQRT];
	int value(int x,int y){
		return ss[x].v+(ss[x].r-ss[x].l+1)*pp[y].lazy;
	}
	void add_block(int i,int l,int r,int k){
		if(l<=pp[i].ll&&pp[i].rr<=r) pp[i].lazy+=k;
		else{
			for(int j=pp[i].l;j<=pp[i].r;j++){
				if(r<ss[j].l||ss[j].r<l) continue;
				ss[j].v+=k*(min(ss[j].r,r)-max(ss[j].l,l)+1);
			}
			sort(ss+pp[i].l,ss+pp[i].r+1);
		}
		return;
	}
	int query_block(int i,int l,int r,int k){
		if(l<=pp[i].ll&&pp[i].rr<=r){
			int L=pp[i].l,R=pp[i].r,mid;
			while(L<R){
				mid=(L+R+1)>>1;
				if(value(mid,i)>k){
					R=mid-1;
				}else{
					L=mid;
				}
			}
			if(value(L,i)>k) return 0;
			return L-pp[i].l+1;
		}else{
			int re=0;
			for(int j=pp[i].l;j<=pp[i].r;j++){
				if(l<=ss[j].l&&ss[j].r<=r&&value(j,i)<=k){
					re++;
				}
			}
			return re;
		}
	}
	void init(){
		int len=sqrt(cnt),tmp=1;
		while(tmp+len-1<=cnt){
			pp[++tot]={tmp,tmp+len-1,ss[tmp].l,ss[tmp+len-1].r,0};
			tmp+=len;
		}
		if(tmp<=cnt){
			pp[++tot]={tmp,cnt,ss[tmp].l,ss[cnt].r,0};
		}
		return;
	}
	void add(int l,int r,int k){
		int L=1,R=tot,mid;
		while(L<R){
			mid=(L+R+1)>>1;
			if(pp[mid].ll>l){
				R=mid-1;
			}else{
				L=mid;
			}
		}
		for(int i=L;i<=tot&&pp[i].ll<=r;i++){
			add_block(i,l,r,k);
		}
		return;
	}
	int query(int l,int r,int k){
		int L=1,R=tot,mid;
		while(L<R){
			mid=(L+R+1)>>1;
			if(pp[mid].ll>l){
				R=mid-1;
			}else{
				L=mid;
			}
		}
		int re=0;
		for(int i=L;i<=tot&&pp[i].ll<=r;i++){
			re+=query_block(i,l,r,k);
		}
		return re;
	}
}s[LOG];

#define ls (i<<1)
#define rs (i<<1|1)
void build(int i,int L,int R){
	int len=R-L+1;
	if(!p[len]) p[len]=++tot;
	s[p[len]].ss[++s[p[len]].cnt]=(Sequence::Node){L,R,0};
	if(L==R) return;
	int mid=(L+R)>>1;
	build(ls,L,mid);
	build(rs,mid+1,R);
	return;
}
#undef ls
#undef rs

void op1(int l,int r,int k){
	for(int i=1;i<=tot;i++){
		s[i].add(l,r,k);
	}
	return;
}

void op2(int l,int r,int k){
	int ans=0;
	for(int i=1;i<=tot;i++){
		ans+=s[i].query(l,r,k);
	}
	printf("%d\n",ans);
	return;
}

void init(){
	for(int i=1;i<=tot;i++){
		s[i].init();
	}
	return;
}

#ifdef DBG
void show(){
	printf("tot=%d\n",tot);
	for(int i=1;i<=tot;i++){
		printf("s[%d]:tot=%d,cnt=%d\n",i,s[i].tot,s[i].cnt);
		for(int j=1;j<=s[i].tot;j++){
			printf("-pp[%d]={[%d,%d],[%d,%d],lazy=%d}:\n",j,s[i].pp[j].l,s[i].pp[j].r,s[i].pp[j].ll,s[i].pp[j].rr,s[i].pp[j].lazy);
			for(int k=s[i].pp[j].l;k<=s[i].pp[j].r;k++){
				printf("--ss[%d]={[%d,%d],%d}\n",k,s[i].ss[k].l, s[i].ss[k].r, s[i].ss[k].v);
			}
		}
		printf("\n");
	}
	return;
}
#endif

int main(){
	read(n,m);
	build(1,1,n);
	init();
	#ifdef DBG
	show();
	#endif
	for(int i=1,op,l,r,k;i<=m;i++){
		read(op,l,r,k);
		if(op==1){
			op1(l,r,k);
		}else{
			op2(l,r,k);
		}
		#ifdef DBG
		show();
		#endif
	}
	return 0;
}