THZH @ 2023-08-16 17:00:44
如果你下列数据始终输出14
input:
100 5
40 7 47 44 52 81 87 60 82 49 40 30 44 90 62 68 81 44 46 17 44 71 89 79 44 95 57 4 6 36 26 61 62 64 14 93 46 35 20 98 55 6 71 9 85 31 1 70 93 100 82 33 57 14 83 56 40 67 27 53 43 39 44 4 59 32 49 72 91 60 67 84 16 64 9 21 59 30 100 34 47 62 10 9 56 88 19 20 16 92 22 11 68 56 62 16 77 94 20 10
M 66 67 1
M 82 97 13
M 14 90 20
M 47 76 7
A 58 86 80
output:
13那么你大概率在未完全覆盖的块中暴力更新时，对着排序数组直接更新了，看看下面这段代码，捋一捋。
a数组->排序数组
b数组->原始数组#define ox of[x]
#define oy of[y]
#define f(x,y) for(register I i=x;i<=y;i++)
f(x,r[ox])b[i]+=v;
f(l[oy],y)b[i]+=v;
f(l[ox],r[ox])a[i]=b[i];
f(l[oy],r[oy])a[i]=b[i];你应当先在b数组中更新对应元素，然后把b数组的块复制到排序数组a对应的块中，然后在a数组的块中再次进行排序。
也就是说，除了更新未完全覆盖的具体元素外，始终以块为操作单位。
这属于本人的粗心导致的错误，我认为不会有人错在这的
cccccorz
by THZH @ 2023-08-16 17:03:55
还有数据过水，笨人的垃圾代码，在这种情况下任然有90pts,出题人的每一个数据都有责任。
在错误更新答案的情况下，我的实际得分本应该为0pts
by THZH @ 2023-08-16 18:48:55
@小粉兔 加强数据
by 小粉兔 @ 2023-08-17 02:39:36
@THZH 反正没过就不要加强了吧
by ssl_lwz @ 2023-08-24 10:01:02
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n,m,a[N],b[N],bel[N],add[N];
int st[N],ed[N],t;
void copy(int x){
for(int i=st[x];i<=ed[x];i++)
b[i]=a[i];
sort(b+st[x]+1,b+ed[x]+1);
}
void build(){
for(int i=1;i<=t;i++){
st[i]=n/t*(i-1)+1;
ed[i]=n/t*i;
}
ed[t]=n;
for(int i=1;i<=t;i++)
for(int j=st[i];j<=ed[i];j++)
bel[j]=i;
}
void update(int x,int y,int c){
//(x,y)+c
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++)
a[i]+=c;
copy(bel[x]);
return;
}
for(int i=x;i<=ed[bel[x]];i++){
a[i]+=c;
copy(bel[x]);
}
for(int i=st[bel[y]];i<=y;i++){
a[i]+=c;copy(bel[y]);
}
for(int i=ed[bel[x]]+1;i<st[bel[y]];i++)
add[i]+=c;
}
int find(int x,int c){ //在块x中
//找>=c的个数
int z=st[x],y=ed[x];
while(z<=y){
int mid=(z+y)>>1;
if(b[mid]+add[x]<mid) z=mid+1;
else y=mid-1;
}
return ed[x]-z+1;
}
int ser(int x,int y,int w){
int ans=0;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) ans+=(a[i]+add[i]>=w);
return ans;
}
for(int i=x;i<=ed[bel[x]];i++)
ans+=(a[i]+add[i]>=w);
for(int i=st[bel[y]];i<=y;i++)
ans+=(a[i]+add[i]>=w);
for(int i=bel[x]+1;i<bel[y];i++)
ans+=find(i,w);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
t=sqrt(n);
for(int i=1;i<=n;i++) cin>>a[i];
// build();
for(int i=1,x,y,w;i<=m;i++){
char c;
cin>>c>>x>>y>>w;
if(c=='M'){
update(x,y,w);
}
else{
cout<<ser(x,y,w)<<endl;
}
}
return 0;
}@小粉兔 甚至不调用build函数都有90分
by ssl_lwz @ 2023-08-24 10:02:20
我的边界全是0
by OrinLoong @ 2024-07-05 14:14:56
@THZH 抽象，我的程序WA subtask1，结果这组数据输出12
by OrinLoong @ 2024-07-05 14:19:01
@OrinLoong 已AC，xy同块更新时同步到排序数组那里循环范围写成x到y了