小元勋 @ 2019-06-01 15:01:37
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
#define maxm 3010
#define mid ((l+r)>>1)
#define lson l,mid,nod<<1
#define rson mid+1,r,nod<<1|1
#define Love long long
int n,m,a[maxn];
Love ans=0,la[maxn],mi[maxn];
inline int read_() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}
inline void pushup_(int nod) {
mi[nod]=min(mi[nod<<1],mi[nod<<1|1]);
}
void build_(int l,int r,int nod) {
if(l==r) {
mi[nod]=a[l];
return;
}
build_(lson);
build_(rson);
pushup_(nod);
}
inline void xiugai_(int l,int r,int nod,int v) {
mi[nod]+= (Love) v;
la[nod]+= (Love) v;
}
inline void pushdown_(int l,int r,int nod) {
//if(!la[nod]) return;
xiugai_(lson,la[nod]);
xiugai_(rson,la[nod]);
la[nod]=0;
}
void update_(int l,int r,int nod,int LL,int RR,int v) {
if(LL<=l&&RR>=r) {
xiugai_(l,r,nod,v);
return;
}
if(la[nod]) pushdown_(l,r,nod);
if(LL<=mid) update_(lson,LL,RR,v);
if(RR>mid) update_(rson,LL,RR,v);
pushup_(nod);
}
void query_(int l,int r,int nod,int LL,int RR,int v) {
if(LL<=l&&RR>=r&&mi[nod]>=v) {
ans+=r-l+1;
return;
}
if(l==r) return ;
if(la[nod]) pushdown_(l,r,nod);
if(LL<=mid) query_(lson,LL,RR,v);
if(RR>mid) query_(rson,LL,RR,v);
}
void readda_() {
n=read_();m=read_();
for(int i=1;i<=n;++i) {
a[i]=read_();
}
memset(la,0,sizeof(la));
memset(mi,0,sizeof(mi));
build_(1,n,1);
int x,y,z;
for(int i=1;i<=m;++i) {
char c;
cin>>c;
x=read_();y=read_();z=read_();
if(c=='M') {
update_(1,n,1,x,y,z);
}
else {
ans=0;
query_(1,n,1,x,y,z);
printf("%lld\n",ans);
}
}
}
int main() {
freopen("a.txt","r",stdin);
readda_();
return 0;
}
by wxwoo @ 2019-06-01 15:03:15
这题不应该分块艹过去吗
by 言和YanHe @ 2019-06-01 15:04:47
@wxwoo 艹过去?!
by wxwoo @ 2019-06-01 15:06:23
@HFOI菠萝 分块不就是暴力吗,暴力不就是艹过去吗
by 小元勋 @ 2019-06-01 15:06:27
@wxwoo 不会分块
by 小元勋 @ 2019-06-01 15:09:52
过了,考了个月考考傻了。 搞忘开4倍了。。。
by WCF_ @ 2019-06-01 15:23:12
这个不是分块吗?
by Juan_feng @ 2019-06-01 15:25:09
@何元勋 显然复杂度是错误的啊
by Juan_feng @ 2019-06-01 15:27:33
@何元勋 您的query函数可能遍历整颗树,而且相当好卡。
说句闲话, 要是区间加区间rank都能log做了那分块就可以退出历史舞台了
by 分块 @ 2019-06-01 15:34:21
@wxwoo 暴力是相对而言吧。
对于本题而言, 我就是正解啦, 暴力什么的, 才不是呢(〃'▽'〃)
by 小元勋 @ 2019-06-01 15:43:34
@Juan_feng 那可能是数据水吧