\(\color{#0066ff}{题目描述}\)
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。
\(\color{#0066ff}{输入格式}\)
第一行输入一个数字 n。
第二行输入 n 个数字，第 i 个数字为 \(a_i\) ，以空格隔开。
接下来输入 n 行询问，每行输入四个数字 \(\mathrm{opt}、l、r、c\)，以空格隔开。
若 \(\mathrm{opt} = 0\)，表示将位于 \([l,r]\) 的之间的数字都加 c。
若 \(\mathrm{opt} = 1\)，表示询问\([l,r]\) 中，小于 \(c^2\) 的数字的个数。
\(\color{#0066ff}{输出格式}\)
对于每次询问，输出一行一个数字表示答案。
\(\color{#0066ff}{输入样例}\)
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2\(\color{#0066ff}{输出样例}\)
3
0
2\(\color{#0066ff}{题解}\)
每个块还是维护标记，单点维护权值
额外开一个数组，这个数组基于原序列，但是满足所有块内元素有序
在区间加的时候，整块打标记，数组不用管，因为一个有序的序列同时加一个数，相对大小不变，依然有序
对于散块，暴力加，这是就可能改变大小关系，于是重新\(O(\sqrt{n})\)的复制一遍那个散块，排序
询问时，如果是整块，直接lowerbound，累计答案
如果是散块，一定要暴力统计
为什么呢？ 举个例子（对拍出来的）
10
2 6 1 8 9 6 9 2 9 3
1 6 10 3为了方便，只写了那个有问题的操作
根据前面所说，那个数组应该是\(1,2,6,6,8,9,2,9,9,3\)
那么我们询问的区间是[6,10]，但是正常应该在区间内的是\(6,9,2,9,3\)
而数组中的却是\(9,2,9,9,3\)
所以答案出现了错误，原因是sort后，改变了原序列元素的位置，这时我们可能会统计到一些不该统计的东东
所以散块一定不能用数组，暴力就可以了
#include<cstdio>
#include<queue>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define _ 0
#define LL long long
#define Space putchar(' ')
#define Enter putchar('\n')
#define fuu(x,y,z) for(int x=(y),x##end=z;x<=x##end;x++)
#define fu(x,y,z) for(int x=(y),x##end=z;x<x##end;x++)
#define fdd(x,y,z) for(int x=(y),x##end=z;x>=x##end;x--)
#define fd(x,y,z) for(int x=(y),x##end=z;x>x##end;x--)
#define mem(x,y) memset(x,y,sizeof(x))
#ifndef olinr
inline char getc()
{static char buf[100001],*p1=buf,*p2=buf;return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100001,stdin),p1==p2)? EOF:*p1++;
}
#else
#define getc() getchar()
#endif
template<typename T>inline void in(T &x)
{int f=1; char ch; x=0;while(!isdigit(ch=getc()))(ch=='-')&&(f=-f);while(isdigit(ch)) x=x*10+(ch^48),ch=getc();x*=f;
}
const int inf=0x7fffffff;
int n;
struct K
{int l,r,tag;K() {l=inf,r=-inf;}
}e[50505];
struct seq
{int val,bel;
}a[50500];
int s[50505];
int num;
inline int lob(int L,int R,int c)
{ return std::lower_bound(s+L,s+R+1,c)-s-L;
}
inline void init()
{num=std::sqrt(n);fuu(i,1,n){in(a[i].val),a[i].bel=(i-1)/num+1,s[i]=a[i].val;e[a[i].bel].l=std::min(e[a[i].bel].l,i);e[a[i].bel].r=std::max(e[a[i].bel].r,i); }for(int i=1;i<=n;i+=num) std::sort(s+e[a[i].bel].l,s+e[a[i].bel].r+1);
}
inline void add(int l,int r,int c)
{fuu(i,a[l].bel+1,a[r].bel-1) e[i].tag+=c;fuu(i,l,std::min(r,e[a[l].bel].r)) a[i].val+=c;fuu(i,e[a[l].bel].l,e[a[l].bel].r) s[i]=a[i].val;std::sort(s+e[a[l].bel].l,s+e[a[l].bel].r+1);if(a[l].bel!=a[r].bel){fuu(i,std::max(l,e[a[r].bel].l),r) a[i].val+=c;fuu(i,e[a[r].bel].l,e[a[r].bel].r) s[i]=a[i].val;std::sort(s+e[a[r].bel].l,s+e[a[r].bel].r+1);}
}
inline int query(int l,int r,int c)
{int ans=0;fuu(i,a[l].bel+1,a[r].bel-1) ans+=lob(e[i].l,e[i].r,c-e[i].tag);fuu(i,l,std::min(e[a[l].bel].r,r)) if(a[i].val<c-e[a[l].bel].tag) ans++;if(a[l].bel!=a[r].bel) fuu(i,std::max(e[a[r].bel].l,l),r) if(a[i].val<c-e[a[r].bel].tag) ans++;return ans;
}
int main()
{in(n);init();int p,l,r,c;while(n--){in(p),in(l),in(r),in(c);if(p==0) add(l,r,c);else printf("%d\n",query(l,r,c*c));}return ~~(0^_^0);
}