数据疑似过水

修改操作时将 直接将右侧不完整块清空 可拿 100pts ，但是hack#1会WA

错误代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

#define div(...)

int n,q;

int nb,sb;
int a[1000010],id[1000010];
vector<int>b[1010];int tag[1010];

void modify(int l,int r,int k){
    int bid=id[l],eid=id[r];
    if(id[l]==id[l-1]){
        int i=l;
        for(i=l;id[i]==id[l];++i){
            a[i]+=k;
        }
        b[id[l]].clear();
        for(int j=i-1;id[j]==id[l];--j){
            b[id[l]].push_back(a[j]);
        }
        sort(b[id[l]].begin(),b[id[l]].end());
        bid++;
    }
    if(id[r]==id[r+1]){
        int i=r;
        for(i=r;id[i]==id[r];--i){
            a[i]+=k;
        }
        b[id[r]].clear();
        //注意看这里 ---------------------------------------------------
        eid--;
    }
    for(int i=bid;i<=eid;++i){
        tag[i]+=k;
    }
}
int singlequery(int id,int k){
    int l=0,r=b[id].size()-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(b[id][mid]+tag[id]>=k){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return b[id].size()-l;
}
int query(int l,int r,int k){
    int bid=id[l],eid=id[r],ret=0;
    if(id[l]==id[l-1]){
        vector<int>v;
        for(int i=l;id[i]==id[l];++i){
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        for(int i=v.size()-1;i>=0&&v[i]+tag[id[l]]>=k;--i){
            ret++;
        }
        bid++;
    }
    if(id[r]==id[r+1]){
        vector<int>v;
        for(int i=r;id[i]==id[r];--i){
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        for(int i=v.size()-1;i>=0&&v[i]+tag[id[l]]>=k;--i){
            ret++;
        }
        eid--;
    }
    for(int i=bid;i<=eid;++i){
        ret+=singlequery(i,k);
    }
    return ret;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    div(input){
        cin>>n>>q;
        for(int i=1;i<=n;++i){
            cin>>a[i];
        }
    }
    div(prework){
        sb=ceil(sqrt(n));
        nb=ceil(1.0*n/sb);
        for(int i=1,nsb=0,nid=1;i<=n;++i){
            nsb++;
            id[i]=nid;
            b[nid].push_back(a[i]);
            if(nsb>=sb){
                nsb=0;
                nid++;
            }
        }
        for(int i=1;i<=nb;++i){
            sort(b[i].begin(),b[i].end());
        }
    }
    div(solve){
        while(q--){
            char opt;int l,r,k;
            cin>>opt>>l>>r>>k;
            if(opt=='M'){
                modify(l,r,k);
            }
            else{
                cout<<query(l,r,k)<<"\n";
            }
        }
    }
}

正确代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

#define div(...)

int n,q;

int nb,sb;
int a[1000010],id[1000010];
vector<int>b[1010];int tag[1010];

void modify(int l,int r,int k){
    int bid=id[l],eid=id[r];
    if(id[l]==id[l-1]){
        int i=l;
        for(i=l;id[i]==id[l];++i){
            a[i]+=k;
        }
        b[id[l]].clear();
        for(int j=i-1;id[j]==id[l];--j){
            b[id[l]].push_back(a[j]);
        }
        sort(b[id[l]].begin(),b[id[l]].end());
        bid++;
    }
    if(id[r]==id[r+1]){
        int i=r;
        for(i=r;id[i]==id[r];--i){
            a[i]+=k;
        }
        b[id[r]].clear();
        for(int j=i+1;id[j]==id[r];++j){
            b[id[r]].push_back(a[j]);
        }
        sort(b[id[r]].begin(),b[id[r]].end());
        eid--;
    }
    for(int i=bid;i<=eid;++i){
        tag[i]+=k;
    }
}
int singlequery(int id,int k){
    int l=0,r=b[id].size()-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(b[id][mid]+tag[id]>=k){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return b[id].size()-l;
}
int query(int l,int r,int k){
    int bid=id[l],eid=id[r],ret=0;
    if(id[l]==id[l-1]){
        vector<int>v;
        for(int i=l;id[i]==id[l];++i){
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        for(int i=v.size()-1;i>=0&&v[i]+tag[id[l]]>=k;--i){
            ret++;
        }
        bid++;
    }
    if(id[r]==id[r+1]){
        vector<int>v;
        for(int i=r;id[i]==id[r];--i){
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        for(int i=v.size()-1;i>=0&&v[i]+tag[id[l]]>=k;--i){
            ret++;
        }
        eid--;
    }
    for(int i=bid;i<=eid;++i){
        ret+=singlequery(i,k);
    }
    return ret;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    div(input){
        cin>>n>>q;
        for(int i=1;i<=n;++i){
            cin>>a[i];
        }
    }
    div(prework){
        sb=ceil(sqrt(n));
        nb=ceil(1.0*n/sb);
        for(int i=1,nsb=0,nid=1;i<=n;++i){
            nsb++;
            id[i]=nid;
            b[nid].push_back(a[i]);
            if(nsb>=sb){
                nsb=0;
                nid++;
            }
        }
        for(int i=1;i<=nb;++i){
            sort(b[i].begin(),b[i].end());
        }
    }
    div(solve){
        while(q--){
            char opt;int l,r,k;
            cin>>opt>>l>>r>>k;
            if(opt=='M'){
                modify(l,r,k);
            }
            else{
                cout<<query(l,r,k)<<"\n";
            }
        }
    }
}