rt,双倍经验AC了,这道题WA了。。。请大佬们帮忙审一下代码吧,写的分块
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXSQRTN 320
typedef long long ll;
int n,m,sqrtn;
ll a[MAXN];
int belong[MAXN],l[MAXSQRTN],r[MAXSQRTN],block_cnt;
bitset<MAXN> vis;
ll block[MAXSQRTN];
void init(){
vis=0;
memset(belong,0,sizeof(belong));
memset(block,0,sizeof(block));
memset(l,0,sizeof(l));
//memset(a,0,sizeof(a));
memset(r,0,sizeof(r));
block_cnt=0;
}
void build(){
block_cnt=sqrtn;
for(int i=1;i<=sqrtn;i++){
l[i]=r[i-1]+1;
r[i]=l[i]+sqrtn-1;
for(int j=l[i];j<=r[i];j++){
block[i]+=a[j];
belong[j]=i;
}
}
if(r[block_cnt]!=n){
block_cnt+=1;
l[block_cnt]=r[block_cnt-1]+1;
r[block_cnt]=n;
for(int i=l[block_cnt];i<=r[block_cnt];i++){
block[block_cnt]+=a[i];
belong[i]=block_cnt;
}
}
}
ll query(int L,int R){
ll ret=0;
if(belong[L]==belong[R]){
for(int i=L;i<=R;i++){
ret+=a[i];
}
return ret;
}
if(L!=l[belong[L]]){
for(int i=L;i<=r[belong[L]];i++){
ret+=a[i];
}
L=l[belong[L]+1];
}
if(R!=r[belong[R]]){
for(int i=R;i>=l[belong[R]];i--){
ret+=a[i];
}
R=r[belong[R]-1];
}
for(int i=belong[L];i<=belong[R];i++){
ret+=block[i];
}
return ret;
}
void modify(int L,int R){
if(belong[L]==belong[R]){
if(!vis[belong[L]]){
for(int i=L;i<=R;i++){
ll tmp=a[i];
a[i]=sqrt(a[i]);
block[belong[L]]-=tmp-a[i];
}
}
}else{
if(L!=l[belong[L]]){
if(!vis[belong[L]]){
for(int i=L;i<=r[belong[L]];i++){
ll tmp=a[i];
a[i]=sqrt(a[i]);
block[belong[L]]-=tmp-a[i];
}
}
L=l[belong[L]+1];
}
if(R!=r[belong[R]]){
if(!vis[belong[L]]){
for(int i=R;i>=l[belong[R]];i--){
ll tmp=a[i];
a[i]=sqrt(a[i]);
block[belong[R]]-=tmp-a[i];
}
}
R=r[belong[R]-1];
}
for(int i=belong[L];i<=belong[R];i++){
if(!vis[i]){
vis[i]=true;
for(int j=l[i];j<=r[i];j++){
ll tmp=a[j];
a[j]=sqrt(a[j]);
if(a[j]>1){
vis[i]=false;
}
block[i]-=tmp-a[j];
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
int fuck=0;
while(cin.good()){
cin>>n;
sqrtn=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(!cin.good()){
exit(0);
}
init();
build();
cin>>m;
cout<<"Case #"<<++fuck<<":"<<endl;
for(int i=1;i<=m;i++){
int op,l,r;
cin>>op>>l>>r;
if(l>r)swap(l,r);
if(op==0){
modify(l,r);
}else if(op==1){
cout<<query(l,r)<<endl;
}
}
}
return 0;
}