技术教程 编程教程 LOJ 数列分块入门 9 题解题报告 正文

LOJ 数列分块入门 9 题解题报告

2023-02-22,,

LOJ 数列分块入门 9 题解题报告

\(\text{By DaiRuiChen007}\)

I. 数列分块入门 1

题目大意

\(\text{Link}\)

维护一个长度为 \(n\) 的序列，支持区间加，单点查值

思路分析

简单分块，块长 \(\sqrt n\)，对于每个块维护一个懒标记

代码呈现

#include<bits/stdc++.h>

using namespace std;

const int MAXN=5e4+1,SQR=231;

int a[MAXN],bel[MAXN];

int tag[SQR],lp[SQR],rp[SQR];

inline void Modify(int l,int r,int c) {

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) a[i]+=c;

		return ;

	}

	for(int i=l;i<=rp[bel[l]];++i) a[i]+=c;

	for(int i=lp[bel[r]];i<=r;++i) a[i]+=c;

	for(int i=bel[l]+1;i<=bel[r]-1;++i) tag[i]+=c;

	return ;

}

signed main() {

	int n,k;

	scanf("%d",&n);

	k=sqrt(n);

	for(int i=1;i<=n;++i) scanf("%d",&a[i]);

	for(int i=1;i<=k;++i) lp[i]=(i-1)*k+1,rp[i]=i*k;

	rp[k]=n;

	for(int i=1;i<=k;++i) for(int j=lp[i];j<=rp[i];++j) bel[j]=i;

	while(n--) {

		int opt,l,r,c;

		scanf("%d%d%d%d",&opt,&l,&r,&c);

		if(opt==0) Modify(l,r,c);

		if(opt==1) printf("%d\n",a[r]+tag[bel[r]]);

	}

	return 0;

}

II. 数列分块入门2

题目大意

\(\text{Link}\)

维护一个长度为 \(n\) 的序列，支持区间加，区间统计小于 \(k\) 的数的个数

思路分析

区间加，传统思路，维护懒标记

区间计数，对于每个序列维护一个有序集合（排序后的 vector 或直接使用 set）都可以

然后对于每一个块在有序集上二分小于 \(k-tag\) 的个数

分块的重要注意事项：如果在修改了零散块的时候会影响区间标记的正确性，需要先下放区间标记再修改零散块

在本题中，如果修改零散块时，要把对应块维护的有序集清空然后重新加入维护

代码呈现

#include<bits/stdc++.h>

using namespace std;

const int MAXN=50001,SQR=231;

int a[MAXN],bel[MAXN];

int tag[SQR],lp[SQR],rp[SQR];

vector <int> f[SQR];

inline void Update(int id) {

	f[id].clear();

	for(int i=lp[id];i<=rp[id];++i) f[id].push_back(a[i]);

	sort(f[id].begin(),f[id].end());

	return ;

}

inline void Modify(int l,int r,int v) {

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) a[i]=a[i]+v;

		Update(bel[l]);

		return ;

	}

	for(int i=l;i<=rp[bel[l]];++i) a[i]=a[i]+v;

	Update(bel[l]);

	for(int i=lp[bel[r]];i<=r;++i) a[i]=a[i]+v;

	Update(bel[r]);

	for(int i=bel[l]+1;i<=bel[r]-1;++i) tag[i]+=v;

}

inline int Query(int l,int r,int v) {

	int ans=0;

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) if(a[i]+tag[bel[i]]<v) ++ans;

		return ans;

	}

	for(int i=l;i<=rp[bel[l]];++i) if(a[i]+tag[bel[i]]<v) ++ans;

	for(int i=lp[bel[r]];i<=r;++i) if(a[i]+tag[bel[i]]<v) ++ans;

	for(int i=bel[l]+1;i<=bel[r]-1;++i) ans+=lower_bound(f[i].begin(),f[i].end(),v-tag[i])-f[i].begin();

	return ans;

}

signed main() {

	int n,k;

	scanf("%d",&n);

	k=sqrt(n);

	for(int i=1;i<=n;++i) scanf("%d",&a[i]);

	for(int i=1;i<=k;++i) lp[i]=(i-1)*k+1,rp[i]=i*k;

	rp[k]=n;

	for(int i=1;i<=k;++i) {

		for(int j=lp[i];j<=rp[i];++j) bel[j]=i;

		Update(i);

	}

	while(n--) {

		int opt,l,r,c;

		scanf("%d%d%d%d",&opt,&l,&r,&c);

		if(opt==0) Modify(l,r,c);

		if(opt==1) printf("%d\n",Query(l,r,c*c));

	}

	return 0;

}

III. 数列分块入门 3

题目大意

\(\text{Link}\)

维护一个长度为 \(n\) 的序列，支持区间加，区间查询前驱

思路分析

和上一题几乎一样，直接有序集上二分即可

代码呈现

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1e5+1,SQR=321,INF=2147483647;

int a[MAXN],bel[MAXN];

int tag[SQR],lp[SQR],rp[SQR];

vector <int> f[SQR];

inline void Update(int id) {

	f[id].clear();

	for(int i=lp[id];i<=rp[id];++i) f[id].push_back(a[i]);

	sort(f[id].begin(),f[id].end());

	return ;

}

inline void Modify(int l,int r,int v) {

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) a[i]+=v;

		Update(bel[l]);

		return ;

	}

	for(int i=l;i<=rp[bel[l]];++i) a[i]+=v;

	Update(bel[l]);

	for(int i=lp[bel[r]];i<=r;++i) a[i]+=v;

	Update(bel[r]);

	for(int i=bel[l]+1;i<=bel[r]-1;++i) tag[i]+=v;

	return ;

}

inline int query(int l,int r,int v) {

	int ans=-INF,ok=false;

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) if(a[i]+tag[bel[i]]<v) ok=true,ans=max(ans,a[i]+tag[bel[i]]);

		if(!ok) return -1;

		else return ans;

	}

	for(int i=l;i<=rp[bel[l]];++i) if(a[i]+tag[bel[i]]<v) ok=true,ans=max(ans,a[i]+tag[bel[i]]);

	for(int i=lp[bel[r]];i<=r;++i) if(a[i]+tag[bel[i]]<v) ok=true,ans=max(ans,a[i]+tag[bel[i]]);

	for(int i=bel[l]+1;i<=bel[r]-1;++i) {

		auto it=lower_bound(f[i].begin(),f[i].end(),v-tag[i]);

		if(it!=f[i].begin()) ok=true,ans=max(ans,*(--it)+tag[i]);

	}

	if(!ok) return -1;

	else return ans;

}

signed main() {

	int n,k;

	scanf("%d",&n);

	k=sqrt(n);

	for(int i=1;i<=n;++i) scanf("%d",&a[i]);

	for(int i=1;i<=k;++i) lp[i]=(i-1)*k+1,rp[i]=i*k;

	rp[k]=n;

	for(int i=1;i<=k;++i) {

		for(int j=lp[i];j<=rp[i];++j) bel[j]=i;

		Update(i);

	}

	while(n--) {

		int opt,l,r,c;

		scanf("%d%d%d%d",&opt,&l,&r,&c);

		if(opt==0) Modify(l,r,c);

		if(opt==1) printf("%d\n",query(l,r,c));

	}

	return 0;

}

IV. 数列分块入门 4

题目大意

\(\text{Link}\)

维护一个长度为 \(n\) 的数，支持区间加，查询区间和

思路分析

查询区间和只需要在查询单点和的基础上维护每一个整块的和

类似线段树，在打懒标记的时候同时更新一下区间和

代码呈现

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int MAXN=50001,SQR=231;

int a[MAXN],bel[MAXN];

int tag[SQR],lp[SQR],rp[SQR],sum[SQR];

inline void Modify(int l,int r,int v) {

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) sum[bel[i]]+=v,a[i]+=v;

		return ;

	}

	for(int i=l;i<=rp[bel[l]];++i) sum[bel[i]]+=v,a[i]+=v;

	for(int i=lp[bel[r]];i<=r;++i) sum[bel[i]]+=v,a[i]+=v;

	for(int i=bel[l]+1;i<=bel[r]-1;++i) tag[i]+=v;

}

inline int Query(int l,int r) {

	int ans=0;

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) ans+=a[i]+tag[bel[i]];

		return ans;

	}

	for(int i=l;i<=rp[bel[l]];++i) ans+=a[i]+tag[bel[i]];

	for(int i=lp[bel[r]];i<=r;++i) ans+=a[i]+tag[bel[i]];

	for(int i=bel[l]+1;i<=bel[r]-1;++i) ans+=sum[i]+tag[i]*(rp[i]-lp[i]+1);

	return ans;

}

signed main() {

	int n,k;

	scanf("%lld",&n);

	k=sqrt(n);

	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);

	for(int i=1;i<=k;++i) lp[i]=(i-1)*k+1,rp[i]=i*k;

	rp[k]=n;

	for(int i=1;i<=k;++i) {

		for(int j=lp[i];j<=rp[i];++j) sum[i]+=a[j],bel[j]=i;

	}

	while(n--) {

		int opt,l,r,c;

		scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);

		if(opt==0) Modify(l,r,c);

		if(opt==1) printf("%lld\n",Query(l,r)%(c+1));

	}

	return 0;

}

V. 数列分块入门 5

题目大意

\(\text{Link}\)

维护一个长度为 \(n\) 的序列，支持区间开根，查询区间和

思路分析

注意到数据范围里的每个数开根次数不超过 \(6\) 次就会变成 \(0\) 或 \(1\)，然后无论开根多少次值都不会变

所以对于每一个块，维护当前块中大于 \(1\) 的数的个数， 如果一个块内没有大于 \(1\) 的数，那么修改的时候直接跳过这个块，否则暴力对于每一个位置修改（其实可以用记录下一个大于 \(1\) 的数，但是没啥用）

然后维护一个区间和，经典求区间和模板即可

代码呈现

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int MAXN=5e4+1,SQR=231;

int a[MAXN],bel[MAXN];

int lp[SQR],rp[SQR],sum[SQR],siz[SQR];

inline void Modify(int l,int r) {

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) {

			if(a[i]<=1) continue;

			sum[bel[i]]-=a[i];

			a[i]=sqrt(a[i]);

			sum[bel[i]]+=a[i];

			if(a[i]<=1) --siz[bel[i]];

		}

		return ;

	}

	for(int i=l;i<=rp[bel[l]];++i) {

		if(a[i]<=1) continue;

		sum[bel[i]]-=a[i];

		a[i]=sqrt(a[i]);

		sum[bel[i]]+=a[i];

		if(a[i]<=1) --siz[bel[i]];

	}

	for(int i=lp[bel[r]];i<=r;++i) {

		if(a[i]<=1) continue;

		sum[bel[i]]-=a[i];

		a[i]=sqrt(a[i]);

		sum[bel[i]]+=a[i];

		if(a[i]<=1) --siz[bel[i]];

	}

	for(int i=bel[l]+1;i<=bel[r]-1;++i) {

		if(!siz[i]) continue;

		for(int j=lp[i];j<=rp[i];++j) {

			if(a[j]<=1) continue;

			sum[i]-=a[j];

			a[j]=sqrt(a[j]);

			sum[i]+=a[j];

			if(a[j]<=1) --siz[i];

		}

	}

	return ;

}

inline int Query(int l,int r) {

	int res=0;

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) res+=a[i];

		return res;

	}

	for(int i=l;i<=rp[bel[l]];++i) res+=a[i];

	for(int i=lp[bel[r]];i<=r;++i) res+=a[i];

	for(int i=bel[l]+1;i<=bel[r]-1;++i) res+=sum[i];

	return res;

}

signed main() {

	int n;

	scanf("%lld",&n);

	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);

	int k=sqrt(n);

	for(int i=1;i<=k;++i) {

		lp[i]=k*(i-1)+1;

		rp[i]=i==k?n:k*i;

		for(int j=lp[i];j<=rp[i];++j) {

			bel[j]=i,sum[i]+=a[j];

			if(a[j]>1) ++siz[i];

		}

	}

	for(int i=1;i<=n;++i) {

		int opt,l,r,c;

		scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);

		if(opt==0) Modify(l,r);

		if(opt==1) printf("%lld\n",Query(l,r));

	}

	return 0;

}

VI. 数列分块入门 6

题目大意

\(\text{Link}\)

维护一个不定长序列，支持单点插入，单点查值

思路分析

对于每个块，用一个 vector 维护其中的每一个数

对于查询操作，先从第一块开始，整块整块地跳，然后找到所在的块的对应位置然后输出

对于插入操作，同理找到对应的块中对应的位置，暴力 insert 即可

为了保证分块的时间复杂度，需要对整个序列进行定期重构，也就是将原本的序列重新分块

如果某一个块的大小大于初始块长的特定倍数（建议 \(12\sim 20\) 等倍数均可，视个人喜好而定），就可以对整个序列重新分块

代码呈现

#include<bits/stdc++.h>

using namespace std;

const int SQR=451;

vector <int> seq[SQR];

int n,k;

inline int bel(int x) { return (x+k-1)/k; }

inline void Rebuild() {

	vector <int> vec;

	for(int i=1;i<=k;++i) {

		for(int v:seq[i]) vec.push_back(v);

		seq[i].clear();

	}

	n=vec.size(),k=sqrt(n);

	for(int i=1;i<=n;++i) seq[bel(i)].push_back(vec[i-1]);

	k=bel(n);

	return ;

}

inline int Query(int p) {

	int block=1;

	while(p>seq[block].size()) {

		p-=seq[block].size();

		++block;

	}

	return seq[block][p-1];

}

inline void Insert(int p,int v) {

	int block=1;

	while(p>seq[block].size()) {

		p-=seq[block].size();

		++block;

	}

	seq[block].insert(seq[block].begin()+p-1,v);

	if(seq[block].size()>(k<<4)) Rebuild();

	return ;

}

signed main() {

	scanf("%d",&n);

	int q=n;k=sqrt(n);

	for(int i=1;i<=n;++i) {

		int x;

		scanf("%d",&x);

		seq[bel(i)].push_back(x);

	}

	k=bel(n);

	while(q--) {

		int opt,l,r,c;

		scanf("%d%d%d%d",&opt,&l,&r,&c);

		if(opt==0) Insert(l,r);

		if(opt==1) printf("%d\n",Query(r));

	}

	return 0;

}

VII. 数列分块入门 7

题目大意

\(\text{Link}\)

维护一个长度为 \(n\) 的序列，支持区间加，区间乘，查询单点值

思路分析

线段树2的分块版本，同理维护乘法标记和加法标记，注意修改零散块之前要先下放标记，并且计算标记贡献的时候是先乘后加的

具体的实现细节可以先写一下线段树2然后再来写，思路会清晰得多

代码呈现

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int MAXN=1e5+1,SQR=321,MOD=10007;

int add[SQR],mul[SQR],lp[SQR],rp[SQR],sum[SQR];

int a[MAXN],bel[MAXN];

inline void PushDown(int id) {

	for(int i=lp[id];i<=rp[id];++i) a[i]=(a[i]*mul[id]%MOD+add[id])%MOD;

	mul[id]=1,add[id]=0;

	return ;

}

inline void ModifyAdd(int l,int r,int v) {

	if(bel[l]==bel[r]) {

		PushDown(bel[l]);

		for(int i=l;i<=r;++i) a[i]=(a[i]+v)%MOD;

		return ;

	}

	PushDown(bel[l]);

	for(int i=l;i<=rp[bel[l]];++i) a[i]=(a[i]+v)%MOD;

	PushDown(bel[r]);

	for(int i=lp[bel[r]];i<=r;++i) a[i]=(a[i]+v)%MOD;

	for(int i=bel[l]+1;i<=bel[r]-1;++i) add[i]=(add[i]+v)%MOD;

	return ;

}

inline void ModifyMul(int l,int r,int v) {

	if(bel[l]==bel[r]) {

		PushDown(bel[l]);

		for(int i=l;i<=r;++i) a[i]=a[i]*v%MOD;

		return ;

	}

	PushDown(bel[l]);

	for(int i=l;i<=rp[bel[l]];++i) a[i]=a[i]*v%MOD;

	PushDown(bel[r]);

	for(int i=lp[bel[r]];i<=r;++i) a[i]=a[i]*v%MOD;

	for(int i=bel[l]+1;i<=bel[r]-1;++i) mul[i]=mul[i]*v%MOD,add[i]=add[i]*v%MOD;

	return ;

}

inline int Query(int p) {

	return (a[p]*mul[bel[p]]+add[bel[p]])%MOD;

}

signed main() {

	int n,k;

	scanf("%lld",&n);

	k=sqrt(n);

	for(int i=1;i<=k;++i) {

		lp[i]=k*(i-1)+1;

		rp[i]=i==k?n:k*i;

		add[i]=0,mul[i]=1;

		for(int j=lp[i];j<=rp[i];++j) scanf("%lld",&a[j]),bel[j]=i;

	}

	for(int i=1;i<=n;++i) {

		int opt,l,r,c;

		scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);

		if(opt==0) ModifyAdd(l,r,c);

		if(opt==1) ModifyMul(l,r,c);

		if(opt==2) printf("%lld\n",Query(r));

	}

	return 0;

}

VIII. 数列分块入门 8

题目大意

\(\text{Link}\)

维护一个长度为 \(n\) 的序列，支持查询区间值等于 \(c\) 的元素个数，并且将整个区间元素推平成 \(c\)

思路分析

在简单暴力的基础上分一下块，考虑一个显而易见的优化：维护每个块内是否全部等于某个数，如果是则直接修改并跳过，否则暴力对于每一个元素修改并更行区间标记，对于零散块则下放标记并且暴力修改

这样做的单次均摊复杂度是 \(\Theta(\sqrt n)\) 的，具体的证明援引自 命题人 hzwer 大佬的题解：

这样看似最差情况每次都会耗费 \(\Theta(n)\) 的时间，但其实可以这样分析：

假设初始序列都是同一个值，那么查询是 \(\Theta(\sqrt n)\)，如果这时进行一个区间操作，它最多破坏首尾 \(2\) 个块的标记，所以只能使后面的询问至多多 \(2\) 个块的暴力时间，所以均摊每次操作复杂度还是 \(\Theta(\sqrt n)\)

换句话说，要想让一个操作耗费 \(\Theta(n)\)的时间，要先花费 \(\Theta(\sqrt n)\) 个操作对数列进行修改

初始序列不同值，经过类似分析后，就可以放心的暴力啦

——hzwer（本系列题目命题人）

Orz。。。

代码呈现

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1e5+1,SQR=321;

int a[MAXN],bel[MAXN],lp[SQR],rp[SQR],tag[SQR];

inline void PushDown(int id) {

	if(tag[id]==-1) return ;

	for(int i=lp[id];i<=rp[id];++i) a[i]=tag[id];

	tag[id]=-1;

	return ;

}

inline int Solve(int l,int r,int v) {

	int res=0;

	if(bel[l]==bel[r]) {

		PushDown(bel[l]);

		for(int i=l;i<=r;++i) {

			if(a[i]==v) ++res;

			else a[i]=v;

		}

		return res;

	}

	PushDown(bel[l]);

	for(int i=l;i<=rp[bel[l]];++i) {

		if(a[i]==v) ++res;

		else a[i]=v;

	}

	PushDown(bel[r]);

	for(int i=lp[bel[r]];i<=r;++i) {

		if(a[i]==v) ++res;

		else a[i]=v;

	}

	for(int i=bel[l]+1;i<=bel[r]-1;++i) {

		if(tag[i]==-1) {

			for(int j=lp[i];j<=rp[i];++j) {

				if(a[j]==v) ++res;

				else a[j]=v;

			}

			tag[i]=v;

		} else {

			if(tag[i]==v) res+=rp[i]-lp[i]+1;

			else tag[i]=v;

		}

	}

	return res;

}

signed main() {

	int n,k;

	scanf("%d",&n);

	k=sqrt(n);

	for(int i=1;i<=k;++i) {

		lp[i]=(i-1)*k+1;

		rp[i]=i==k?n:i*k;

		tag[i]=-1;

		for(int j=lp[i];j<=rp[i];++j) scanf("%d",&a[j]);

	}

	for(int i=1;i<=n;++i) {

		int l,r,c;

		scanf("%d%d%d",&l,&r,&c);

		printf("%d\n",Solve(l,r,c));

	}

	return 0;

}

IX. 数列分块入门 9

题目大意

\(\text{Link}\)

维护一个长度为 \(n\) 的序列，支持查询值最小的区间众数

思路分析

不管怎么样看到标题就先把块分了再说

先分块，对于一个查询区间，分成整块+零散块

考虑可能成为答案的数：零散块中的都有可能，整块中只有可能是这一段的众数。如果不是整块的众数的话，那么一定在零散块中出现过（自行感性理解）

所以只需要离散化，然后将每个数的出现位置存下来，可以做到 \(\Theta(\log n)\) 查询某个数在区间里的出现次数

同时，需要预处理出任意两个块之间的区间众数，方便查询

然后对于每次查询，只需要对于整块里的众数和零散块里的数都枚举一遍，计算出现次数，取众数最小值即可

复杂度 \(\Theta(n\sqrt n\log n)\)

代码呈现

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1e5+1,SQR=321;

int mdl[SQR][SQR],cnt[MAXN],a[MAXN],bel[MAXN],lp[SQR],rp[SQR];

vector <int> pos[MAXN],dsc;

inline int count(int x,int l,int r) {

	return upper_bound(pos[x].begin(),pos[x].end(),r)-lower_bound(pos[x].begin(),pos[x].end(),l);

}

inline int Query(int l,int r) {

	int res=0,tot=0;

	if(bel[l]==bel[r]) {

		for(int i=l;i<=r;++i) {

			int tmp=count(a[i],l,r);

			if(tmp>tot||(a[i]<res&&tmp==tot)) tot=tmp,res=a[i];

		}

		return dsc[res-1];

	}

	if(bel[r]-bel[l]>1) res=mdl[bel[l]+1][bel[r]-1],tot=count(res,l,r);

	for(int i=l;i<=rp[bel[l]];++i) {

		int tmp=count(a[i],l,r);

		if(tmp>tot||(a[i]<res&&tmp==tot)) tot=tmp,res=a[i];

	}

	for(int i=lp[bel[r]];i<=r;++i) {

		int tmp=count(a[i],l,r);

		if(tmp>tot||(a[i]<res&&tmp==tot)) tot=tmp,res=a[i];

	}

	return dsc[res-1];

}

signed main() {

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;++i) {

		scanf("%d",&a[i]);

		dsc.push_back(a[i]);

	}

	sort(dsc.begin(),dsc.end());

	dsc.erase(unique(dsc.begin(),dsc.end()),dsc.end());

	int k=sqrt(n),m=(n+k-1)/k;

	for(int i=1;i<=m;++i) {

		lp[i]=(i-1)*k+1;

		rp[i]=i==m?n:i*k;

		for(int j=lp[i];j<=rp[i];++j) {

			a[j]=(lower_bound(dsc.begin(),dsc.end(),a[j])-dsc.begin())+1;

			bel[j]=i;

			pos[a[j]].push_back(j);

		}

	}

	for(int i=1;i<=m;++i) {

		for(int i=1;i<=n;++i) cnt[i]=0;

		int res=0,tot=0;

		for(int j=lp[i];j<=n;++j) {

			++cnt[a[j]];

			if(cnt[a[j]]>tot||(cnt[a[j]]==tot&&a[j]<res)) {

				tot=cnt[a[j]];

				res=a[j];

			}

			mdl[i][bel[j]]=res;

		}

	}

	for(int i=1;i<=n;++i) {

		int l,r;

		scanf("%d%d",&l,&r);

		printf("%d\n",Query(l,r));

	}

	return 0;

}

LOJ 数列分块入门 9 题解题报告的相关教程结束。

《LOJ 数列分块入门 9 题解题报告.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!