分块60分求助

P2801 教主的魔法

tlnllkbp @ 2018-09-03 20:55:45

求大佬查错

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;
const int N = 1e7+10, M = 1e5;
int n, m, sqn, l, r, c;
char op;
int v[N], blo[M], tag[M];
vector<int> vec[M];
inline void reset(int o) {
    vec[o].clear();
    REP(i,(o-1)*sqn+1,o*sqn) vec[o].push_back(v[i]);
    sort(vec[o].begin(),vec[o].end());
}

inline void upd() {
    if (blo[l]==blo[r]) {
        REP(i,l,r) v[i]+=c;
        reset(blo[l]);
        return ;
    }
    REP(i,l,min(r,sqn*blo[l])) v[i]+=c;
    REP(i,(blo[r]-1)*sqn+1,r) v[i]+=c;
    REP(i,blo[l]+1,blo[r]-1) tag[i]+=c;
    reset(blo[l]),reset(blo[r]);
}

inline void qry() {
    int ans = 0;
    if (blo[l]==blo[r]) {
        REP(i,l,r) ans+=tag[blo[l]]+v[i]>=c;
    } else {
        REP(i,l,min(r,sqn*blo[l])) ans+=tag[blo[l]]+v[i]>=c;
        REP(i,(blo[r]-1)*sqn+1,r) ans+=tag[blo[r]]+v[i]>=c;
        REP(i,blo[l]+1,blo[r]-1) {
            ans+=vec[i].end()-lower_bound(vec[i].begin(),vec[i].end(),c-tag[i]);
        }
    }
    printf("%d\n", ans);
}

signed main() {
    scanf("%d%d", &n, &m);sqn=sqrt(n);
    REP(i,1,n) { 
        scanf("%d", v+i);
        blo[i]=(i-1)/sqn+1;
        vec[blo[i]].push_back(v[i]);
    }
    REP(i,1,blo[n]) sort(vec[i].begin(),vec[i].end());
    REP(i,1,m) {
        scanf(" %c%d%d%d", &op, &l, &r, &c);
        if (op=='M') upd();
        else qry();
    }
}

by tlnllkbp @ 2018-09-03 20:57:48

......知道了, 原来是数组越界了, dalao们可以走了


|