新人OIer刚学分块求助

P2801 教主的魔法

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紫名巨神


|