Sharpsmile @ 2023-09-12 19:31:51
问题出现在RB函数中,在计算完bel后紧接着输出他会以 迅雷不及掩耳之势 变成零。然而我并没有碰他qaq
大佬帮帮/kk
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <random>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <sstream>
#include <bitset>
using namespace std;
#define endl "\n"
#define int long long
#define double long double
#define p1(x) (x).first
#define p2(x) (x).second
#define pii pair<int,int>
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
struct BF{
const int SIZ=450;
const int LEN=445;
const int N=2e5;
int a[200030];
int s[200030];
int S[200030];
int sum[550];
int tg[550];
int bel[200030];
int L[550],R[550];
inline void RB(int *A){
memset(L,0x3f,sizeof(L));
for(int i=1;i<=N;i++){
a[i]=A[i],tg[i]=0,
bel[i]=(i+SIZ-1)/SIZ,
L[bel[i]]=min(L[bel[i]],i),
R[bel[i]]=max(R[bel[i]],i);
if(i==2e5)
cout<<bel[i]<<" ";
}
cout<<endl;
for(int i=1;i<=10;i++)
cout<<bel[i]<<" ";
cout<<endl;
for(int i=1;i<=LEN;i++){
s[L[i]]=a[L[i]];
for(int j=L[i]+1;j<=R[i];j++)
s[j]=s[j-1]+a[j];
sum[i]=s[R[i]];
S[i]=S[i-1]+sum[i];
}
}
inline void pd(int x){
for(int i=L[x];i<=R[x];i++)
a[i]+=tg[x];
s[L[x]]=a[L[x]];
for(int i=L[x]+1;i<=R[x];i++)
s[i]=s[i-1]+a[i];
sum[x]=s[R[x]];
tg[x]=0;
}
inline void upd(){
for(int i=1;i<=LEN;i++)
S[i]=S[i-1]+sum[i];
}
inline void add(int x,int v){
sum[x]+=(R[x]-L[x]+1)*v;
tg[x]+=v;
}
inline void add(int l,int r,int v){
if(bel[l]==bel[r]){
for(int i=l;i<=r;i++)
a[i]+=v;
pd(bel[l]);
}
else{
for(int i=l;i<=R[bel[l]];i++)
a[i]+=v;
pd(bel[l]);
for(int i=L[bel[r]];i<=r;i++)
a[i]+=v;
pd(bel[r]);
for(int i=bel[l]+1;i<=bel[r]-1;i++)
add(i,v);
}
upd();
}
inline int g(int l,int r){
int LP=0;
if(l!=L[bel[l]])
LP=s[l-1];
return s[r]-LP+tg[bel[l]]*(r-l+1);
}
inline int G(int L,int R){
return S[R]-S[L];
}
inline int gt(int l,int r){
if(bel[l]==bel[r])return g(l,r);
else return g(l,R[bel[l]])
+G(bel[l]+1,bel[r]-1)
+g(L[bel[r]],r);
}
}T;
int n,q;
int a[200300];
inline void slv(){
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
T.RB(a);
while(q--){
int op,l,r;
cin>>op>>l>>r;
if(op==1){
int k;
cin>>k;
T.add(l,r,k);
}
else cout<<T.gt(l,r)<<endl;
}
}
inline void MT(){long long _;cin>>_;while(_--)slv();}
const char* SS="/Users/noip2019/Downloads/P8907_2.in";
signed main(){ios::sync_with_stdio(0);
// freopen("/Users/noip2019/Desktop/ZZZZZZZZZZZZCW/0911\ NFLS\ T1/1.in","r",stdin);
// MT();
slv();
return 0;
}
/*
C(1000,500)=
270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320
*/
by Hanghang @ 2023-09-12 19:52:12
tg 数组暴了
@Ranger_HoFr
by Sharpsmile @ 2023-09-12 20:23:19
@Hanghang Thx /kel
by Sharpsmile @ 2023-09-12 20:26:11
还是只有30pts /kk
by Sharpsmile @ 2023-09-12 20:37:59
没事了前缀和减得 L