Rye_Catcher @ 2018-06-19 21:58:20
rt,交上去只有60分,查了好久的错查不出来,然后把代码改了一下交到LOJ上一道类似的题上,居然全部RE,求大佬查错
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <vector>
#include <queue>
#define ll long long
#define ri int
using namespace std;
const int inf=0x7fffffff;
const int maxn=1000005;
const int maxx=2007;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int n,q,block;
int a[maxn],tag[maxx],pos[maxx],L[maxx],R[maxx];
vector <int>g[maxx];
inline void reset(int now){
g[now].clear();
for(ri i=L[now];i<=R[now];i++)g[now].push_back(a[i]);
sort(g[now].begin(),g[now].end());
return ;
}
inline void add(int l,int r,int c){
int p=pos[l],q=pos[r];
if(p==q){
for(ri i=l;i<=r;i++){
a[i]+=c;
}
reset(p);
}
else{
for(ri i=p+1;i<=q-1;i++)tag[i]+=c;
for(ri i=l;i<=R[p];i++){
a[i]+=c;
}
reset(p);
for(ri i=L[q];i<=r;i++){
a[i]+=c;
}
reset(q);
}
return ;
}
inline int query(int l,int r,int x){
int p=pos[l],q=pos[r],cnt=0;
if(p==q){
for(ri i=l;i<=r;i++){
if(a[i]+tag[p]>=x)cnt++;
}
}
else{
for(ri i=p+1;i<=q-1;i++){
cnt+=g[i].size()-(lower_bound(g[i].begin(),g[i].end(),x-tag[i])-g[i].begin());
}
for(ri i=l;i<=R[p];i++){
if(a[i]+tag[p]>=x)cnt++;
}
for(ri i=L[q];i<=r;i++){
if(a[i]+tag[q]>=x)cnt++;
}
}
return cnt;
}
int main(){
read(n),read(q);
block=sqrt(n);
for(ri i=1;i<=n;i++){
read(a[i]);
}
for(ri i=1;i<=block;i++){
L[i]=(i-1)*block+1;
R[i]=i*block;
}
if(R[block]<n)block++,L[block]=R[block-1]+1,R[block]=n;
for(ri i=1;i<=block;i++){
for(ri j=L[i];j<=R[i];j++){
pos[j]=i;
g[i].push_back(a[j]);
}
sort(g[i].begin(),g[i].end());
}
char op[3];
int l,r,c;
while(q--){
scanf("%s",op);
read(l),read(r),read(c);
if(op[0]=='M'){
add(l,r,c);
}
else {
printf("%d\n",query(l,r,c));
}
}
return 0;
}
by 小粉兔 @ 2018-06-19 21:59:53
orz刚学OI就学分块
by hellomath @ 2018-06-19 22:01:47
orz刚学OI就学分块
by mydiplomacy @ 2018-06-19 22:10:55
orz刚学OI就学分块
by nstk0513 @ 2018-06-19 22:13:38
@mydiplomacy 太强了!
by nstk0513 @ 2018-06-19 22:15:32
@Rye_Catcher 您的代码lower_bound那句需要特判一下x-tag[i]不在范围内的情况。如果直接搞,什么也找不到,就RE了。
by noip @ 2018-06-19 22:23:12
orz刚学OI就学分块
by ustze @ 2018-06-19 22:27:11
@noip orz 由乃oi毒瘤分块大佬lxl
by kl膜法59改 @ 2018-07-23 20:23:20
@noip orz紫名巨神