存个板子,免得每次要用的时候不知道从哪题里拉(
bit
struct bit{
vector<int>tr;
int n;
void init(int N){n=N,tr=vector<int>(N+1,0);}
void add(int x,int y){for(;x<=n;x+=x&-x)tr[x]+=y;}
int ask(int x){
int s=0;
for(;x;x^=x&-x)s+=tr[x];
return s;
}
void down(){For(i,1,n)tr[i]+=tr[i^(i&-i)];}
}tr;
\(O(1)-O(\sqrt N)\) 分块
struct DS{
ll s1[maxn],s2[1005];
int bel[maxn],L[1005],R[1005],B;
void init(int n){
B=sqrt(n);
For(i,1,n)bel[i]=(i-1)/B+1,s1[i]=0;
For(i,1,bel[n])L[i]=(i-1)*B+1,R[i]=min(n,i*B),s2[i]=0;
}
void add(int x,int y){s1[x]+=y,s2[bel[x]]+=y;}
ll ask(int x){
ll res=0;
For(i,L[bel[x]],x)res+=s1[i];
Rep(i,bel[x]-1,1)res+=s2[i];
return res;
}
}ds;
\(O(\sqrt N)-O(1)\) 分块
struct DS2{
ll s1[maxn],s2[1005];
int bel[maxn],L[1005],R[1005],B;
void init(int n){
B=sqrt(n);
For(i,1,n)bel[i]=(i-1)/B+1,s1[i]=0;
For(i,1,bel[n])L[i]=(i-1)*B+1,R[i]=min(n,i*B),s2[i]=0;
}
void add(int x,int y){
For(i,x,R[bel[x]])s2[i]+=y;
For(i,bel[x]+1,bel[n])s1[i]+=y;
}
ll ask(int x){return s1[x]+s2[bel[x]];}
}ds;
Grid
const int B1=22,B2=B1*B1,sN=500,ssN=24;
struct grid{
int s22[sN][sN],s23[sN][ssN],s32[ssN][sN],s33[ssN][ssN];
void add(int x2,int y2,int a){
int x3=x2/B1,y3=y2/B1;
s22[x2][y2]+=a;
s23[x2][y3]+=a;
s32[x3][y2]+=a;
s33[x3][y3]+=a;
}
int sum(int x2,int y2){
int s=0;
int x3=x2/B1,y3=y2/B1;
#define Fi3 For(i,0,x3-1)
#define Fi2 For(i,x3*B1,x2-1)
#define Fj3 For(j,0,y3-1)
#define Fj2 For(j,y3*B1,y2-1)
Fi3 Fj3 s+=s33[i][j];
Fi2 Fj2 s+=s22[i][j];
Fi2 Fj3 s+=s23[i][j];
Fi3 Fj2 s+=s32[i][j];
return s;
}
};
莫队/二离莫队
https://uoj.ac/submission/561663
1375H merge
https://www.luogu.com.cn/record/89768497
- structures datastructures 1872e data fan data_structure_midterm_review 202312142321 customised structure data data_structure_midterm_review structure midterm structure tree data javascript structures data algorithm-two structure algorithm data 题解structures 1872e data structures data algorithm-one structure algorithm data