526互联

data structures

发布时间 2023-05-02 09:23:11作者: Rainbow_qwq

存个板子，免得每次要用的时候不知道从哪题里拉（

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