```cpp
if(a[i]+add[i]>=k)
```
add是对块的,这样是不行的.
下面几个add同理.
@[Rexy](/space/show?uid=93207) ~~话说您这就学分块?~~
by SofanHe @ 2018-03-28 07:21:12
@[多功能的荀彧](/space/show?uid=43931) 谢谢dalao,
~~话说我这种错误不只一次了~~
~~话说学分块,没毛病~~
by _Violet_ @ 2018-03-28 23:44:54
@[多功能的荀彧](/space/show?uid=43931) 然而还是TLE(90分)
```cpp
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define Re register
const int N = 1e6+7;
int n,Q;int a[N],b[N];
int blo[N],l[N],r[N];
inline void read(int &_){
_=0;char c=getchar();while(c>'9' || c<'0')c=getchar();
while(c>='0'&&c<='9'){_=(_<<3)+(_<<1)+(c^48);c=getchar();}
}
inline void build(){
Re int sz=sqrt(n);
Re int tot= n/sz ;
if(n%sz) tot++;
for(Re int i=1;i<=tot;++i)
l[i]=(i-1)*sz+1,r[i]=i*sz;
r[tot] = n;
for(Re int i=1;i<=n;++i)
blo[i]=(i-1)/sz+1,b[i]=a[i];
for(Re int i=1;i<=tot;++i)
sort(b+l[i],b+r[i]+1);
}
inline void init(int L){
for(Re int i=l[blo[L]];i<=r[blo[L]];++i)
b[i]=a[i];
sort(b+l[blo[L]],b+r[blo[L]]+1);
}
int add[N];
inline void update(int L,int R,int k){
if(blo[L]==blo[R]){
for(Re int i=L;i<=R;++i)
a[i]+=k;
init(L);return;
}
for(Re int i=L;i<=r[blo[L]];++i)
a[i]+=k;
for(Re int i=l[blo[R]];i<=R;++i)
a[i]+=k;
init(L);init(R);
for(Re int i=blo[L]+1;i<blo[R];++i)
add[i]+=k;
}
inline int search(int now,int k){
Re int L=l[now],R=r[now];
while(L<R){
Re int mid=L+R>>1;
if(b[mid]<k)L=mid+1;
else R=mid;
}
return r[now]-R+1;
}
inline int ask(int L,int R,int k){
Re int cnt=0;
if(blo[L]==blo[R]){
for(Re int i=L;i<=R;++i)
if(a[i]+add[blo[i]]>=k)
++cnt;
return cnt;
}
for(Re int i=L;i<=r[blo[L]];++i)
if(a[i]+add[blo[i]]>=k)
++cnt;
for(Re int i=l[blo[R]];i<=R;++i)
if(a[i]+add[blo[i]]>=k)
++cnt;
for(Re int i=blo[L]+1;i<blo[R];++i)
cnt+=search(i,k-add[i]);
return cnt;
}
int main(){
read(n);
read(Q);
for(Re int i=1;i<=n;++i)
read(a[i]);
Re int x,y,k;
for(Re int i=0;i<Q;++i){
char c[5];scanf("%s",c);
read(x);read(y);read(k);
if(c[0]=='M') update(x,y,k);
else printf("%d",ask(x,y,k)),putchar(10);
}
return 0;
}
```
by _Violet_ @ 2018-03-28 23:49:30
@[多功能的荀彧](/space/show?uid=43931) dalao,我发现我TLE的原因是读入
然而改后第一个点Wa掉了,然后改了一下二分就过了
~~您介意给我讲下标程的二分原理吗~~
by _Violet_ @ 2018-03-29 00:03:30
@[Rexy](/space/show?uid=93207)
二分就是找一个位置让它右面的全都是$≥w$的就好了.
因为$w$可能没有,所以建议是找$<w$的最大位置.
因此我们就能得到这样的二分式子啊
by SofanHe @ 2018-03-29 06:29:56