526互联

第二周学习总结

发布时间 2024-01-11 17:11:10作者: gevenfeng

第二周学习总结

分块

思想：把长度为 \(N\) 的序列分为若干个长度为 \(S\) 的快。对于每次询问/修改，整块打包处理，零散部分暴力处理。

一般情况况下，当 \(S=\sqrt{n}\) 时，有较好复杂度 \(m \sqrt{n}\)。

模板代码：

[线段树]区间极大值2

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<cstring>
const int N=1e5+5;
int n,m,id[N],len,a[N],s[N];
void change(int x,int v){
	a[x]+=v;
	s[id[x]]=-2e8;
	for(int i=(id[x]-1)*len+1;i<=id[x]*len&&i<=n;i++) s[id[x]]=std::max(s[id[x]],a[i]);
}
int query(int l,int r){
    int sid=id[l],eid=id[r],ans=-2e8;
    if(sid==eid){
        for(int i=l;i<=r;i++) ans=std::max(ans,a[i]);
        return ans;
    }
    for(int i=l;i<=sid*len;i++) ans=std::max(ans,a[i]);
    for(int i=sid+1;i<eid;i++) ans=std::max(ans,s[i]);
    for(int i=(eid-1)*len+1;i<=r;i++) ans=std::max(ans,a[i]);
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    len=(int)sqrt(n);
    for(int i=1;i<=n;i++) s[i]=-2e8;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[i]=(i-1)/len+1,s[id[i]]=std::max(s[id[i]],a[i]);
    int x,y,z;
    while(m--){
    	scanf("%d%d%d",&x,&y,&z);
    	if(x==1) change(y,z);
    	else printf("%d\n",query(y,z));
	}
    return 0;
}

例题

[根号]动态区间第K小数

将原序列分为长度为 \(\sqrt{n}\) 的块，块内元素从小到大排序。

修改操作：将 \(a_i\) 修改为 \(t\)，然后将第 \(i\) 个元素所在的块进行重组排序。时间复杂度为 \(O(\sqrt{n} \log_2 \sqrt{n})\)。

查询操作：对答案进行二分。每次二分一个 \(mid\) 值，都到询问区间内寻找比 \(mid\) 小的元素个数。整块在块内直接 \(lower \_ bound\) ，零散部分暴力比较。如果小于 \(mid\) 的元素个数恰好为 \(k-1\)，则 \(mid\) 即为答案。时间复杂度为 \(O(\sqrt{n} \log_2 \sqrt{n})\)。

综上，时间复杂度为 \(O(m \sqrt{n} \log_2 \sqrt{n})\)，可以通过测试。

代码：

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cstring>
const int N=5e4+5;
int n,m,id[N],len,a[N];
std::vector<int> v[N];
void change(int x,int y){
//	printf("%d %d\n",x,y);
//	for(auto i:v[id[x]]) printf("%d ",i);
//	putchar('\n');
	v[id[x]].erase(std::lower_bound(v[id[x]].begin(),v[id[x]].end(),a[x]));
//	for(auto i:v[id[x]]) printf("%d ",i);
//	putchar('\n');
	a[x]=y;
	v[id[x]].emplace(std::lower_bound(v[id[x]].begin(),v[id[x]].end(),y),y);
//	for(auto i:v[id[x]]) printf("%d ",i);
//	putchar('\n');
}
int count(int l,int r,int val){
	int sid=id[l],eid=id[r],ans=0;
	if(sid==eid){
		for(int i=l;i<=r;i++) ans+=(a[i]<val);
		return ans;
	}
	for(int i=l;i<=sid*len;i++) ans+=(a[i]<val);
	for(int i=sid+1;i<eid;i++) ans+=std::lower_bound(v[i].begin(),v[i].end(),val)-v[i].begin();
	for(int i=(eid-1)*len+1;i<=r;i++) ans+=(a[i]<val);
	return ans;
}
int query(int l,int r,int k){
    int L=0,R=50005;
    while(L+1<R){
    	int mid=L+(R-L>>1);
    	if(count(l,r,mid)>=k) R=mid;
    	else L=mid;
	}
    return L;
}
int main(){
//	freopen("oo.in","r",stdin);
    scanf("%d%d",&n,&m);
    len=(int)sqrt(n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[i]=(i-1)/len+1,v[id[i]].emplace_back(a[i]);
    for(int i=1;i<=n;i++) if(v[i].size()>0) std::sort(v[i].begin(),v[i].end());
    int x,y,z;
    char ch[2];
    while(m--){
    	scanf("%s",ch);
    	if(*ch=='C') scanf("%d%d",&x,&y),change(x,y);
    	else scanf("%d%d%d",&x,&y,&z),printf("%d\n",query(x,y,z));
	}
    return 0;
}

这道题更高效的解法是可持久化线段树，时间复杂度为 \(O(m \log_2 n)\)。

[根号]子集求和

考虑将集合分为两种。

这里，我们称元素个数少于或等于 \(\sqrt{n}\) 的集合为小集合，元素个数多于 \(\sqrt{n}\) 的集合为大集合。

由于 \(m\) 个集合的元素个数总和不超过 \(10^5\)，所以大集合的个数不会超过 \(\sqrt{n}\) 的级别。

设 \(cnt_{i,j}\) 表示第 \(i\) 个集合和第 \(j\) 个集合之间相关联的元素个数（即 \(size(i \thinspace \cap \thinspace j)\)），\(sum_i\) 表示第 \(i\) 个大集合内的元素之和，\(lazy_i\) 表示第 \(i\) 个大集合的下传标记。预处理的时间复杂度为 \(n \sqrt{n}\) 的级别。

将第 \(i\) 个小集合的元素加上 \(v\)：将集合 \(i\) 中的元素直接暴力加上 \(v\)，再把于 \(i\) 相关联的大集合 \(j\) 的 \(sum_j\) 加上 \(v \times cnt_{i,j}\)。时间复杂度为 \(O(\sqrt{n})\)。

将第 \(i\) 个大集合的元素加上 \(v\)：直接将 \(lazy_i\) 的值加上 \(v\)。时间复杂度为 \(O(1)\)。

询问第 \(i\) 个小集合内的元素之和：暴力加上集合内的元素，再将所得结果加上与 \(i\) 相关联的大集合 \(j\) 的 \(lazy_j \times cnt_{i,j}\)。时间复杂度为 \(O(\sqrt {n})\)。

询问第 \(i\) 个大集合内的元素之和：将 \(sum_i\) 加上 \(i\) 相关联的大集合 \(j\) 的 \(lazy_j \times cnt_{i,j}\)。时间复杂度为 \(O(\sqrt {n})\)。

综上，时间复杂度为 \(q \sqrt{n}\)，可以通过测试。

代码：

#include<stdio.h>
#include<vector>
#include<math.h>
typedef long long ll;
const int N=1e5+5,M=2e3;
std::vector<ll> v[N],num[N],guan[N];
ll n,m,q,len,a[N],cnt[N][M],sum[N],lazy[N];
int main(){
	scanf("%lld%lld%lld",&n,&m,&q);
	len=(ll)sqrt(n);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(ll i=1,size;i<=m;i++){
		scanf("%lld",&size);
		if(size<=len) for(ll j=1,x;j<=size;j++) scanf("%lld",&x),v[i].emplace_back(x),sum[i]+=a[x];
		else for(ll j=1,x;j<=size;j++) scanf("%lld",&x),v[i].emplace_back(x),num[x].emplace_back(i),sum[i]+=a[x];
	}
	for(ll i=1;i<=m;i++){
		for(auto j:v[i]){
			for(auto k:num[j]){
				cnt[i][k]++;
				if(cnt[i][k]==1) guan[i].emplace_back(k);
			}
		}
	}
	char ch[2];
	ll x,y;
	while(q--){
		scanf("%s",ch);
		if(*ch=='+'){
			scanf("%lld%lld",&x,&y);
			if(v[x].size()<=len){
				for(auto i:v[x]) a[i]+=y;
				for(auto i:guan[x]) sum[i]+=y*cnt[x][i];
			}
			else lazy[x]+=y;
		}
		else{
			scanf("%lld",&x);
			ll ans=0;
			if(v[x].size()<=len){
				for(auto i:v[x]) ans+=a[i];
				for(auto i:guan[x]) ans+=lazy[i]*cnt[x][i];
			}
			else{
				ans+=sum[x];
				for(auto i:guan[x]) ans+=lazy[i]*cnt[x][i];
			}
			printf("%lld\n",ans);	
		}
	}
	return 0;
}

[根号][APIO2015]雅加达的摩天楼

考虑普通建图与分层图结合使用。

对于跳跃能力 \(p\) 大于 \(\sqrt{n}\) 的 \(\operatorname{doge}\)，他能跳到的摩天楼数量 \(\frac{n}{p}\) 一定小于等于 \(\sqrt{n}\)，所以直接暴力建边即可。

对于跳跃能力 \(p\) 小于等于 \(\sqrt{n}\) 的 \(\operatorname{doge}\)，如果暴力建边，则边数就为 \(O(n^2)\) 的量级，无法接受。所以，我们考虑分层图建边。

对于每栋楼 \(i\)，我们都新建 \(\sqrt{n}\) 个相较于 \(i\) 的虚点，\(i_k\) 表示以 \(i\) 为起点，且跳跃长度为 \(k\)。每个虚点都要连接其对应的 \(i\)，边权为 \(0\)。

对于 \(i_k\)，我们再将其向 \(i_k-k\) 和 \(i_k+k\) 连边，边权为 \(1\)，表示从第 \(i\) 个点出发跳 \(1\) 步可以跳到 \(i_k-k\) 和 \(i_k+k\) 的对应实点。

对于在第 \(i\) 栋楼上，跳跃能力为 \(p\) 的 \(\operatorname{doge}\)，我们将 \(i\) 向 \(i_p\) 连边，表示从 \(i\) 点出发，\(1\) 步可以跳到 \(i_p\) 所连虚点对应的实点。

最后跑一遍最短路即可。

时间复杂度分析：

对于每只 跳跃能力 \(p\) 大于 \(\sqrt{n}\) 的 \(\operatorname{doge}\)，他最多会向外连接 \(\sqrt{n}\) 条边，所以总边数不超过 \(n\sqrt{n}\)。

对于分层图每层点之间连的边，共有 \((n-1)+(n-2)+\cdots+(n-\sqrt{n})=\frac{\sqrt{n}(2n-\sqrt{n}-1)}{2}\) 条边，量级为 \(n \sqrt{n}\) 条。

对于每个虚点，每个虚点都会向其对应实点连边，而虚点有 \(n \sqrt{n}\) 个，所以会连 \(n \sqrt{n}\) 条边。

对于每个实点，每个存在 \(\operatorname{doge}\) 的实点都会向其对应的一个虚点连一条边，所以会连 \(n\) 条边。

综上，边数的量级为 \(n \sqrt{n}\) 级别。使用 \(\operatorname{Dijkstra}\) 算法，时间复杂度为 \(n \sqrt{n} \log_2 n \sqrt{n}\)，勉强通过测试。

代码：

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<cstring>
const int N=3e4+5,M=174,Q=1.8375e7+5,L=6e6+5;
//(n+1)+n+(n-1)+...+(n-sqrt(n)+2)
struct jie{int to,val,nxt;}a[Q];
int n,m,building[N],len,pp,head[L],cnt,dis[L];
bool vis[Q];
void add(int x,int y,int z){
	cnt++;
	a[cnt].to=y;
	a[cnt].val=z;
	a[cnt].nxt=head[x];
	head[x]=cnt;
}
inline int num(int i,int j){return i*n+j;}
struct node{
	int id,val;
	bool operator < (const node &x) const{return val>x.val;}
};
void Dijkstra(int s){
	for(int i=1;i<=len*n+n;i++) dis[i]=0x3f3f3f3f;
	std::priority_queue<node> q;
	dis[s]=0,q.push({s,dis[s]});
	while(!q.empty()){
		node u=q.top();q.pop();
		if(vis[u.id]) continue;
		vis[u.id]=true;
		for(int i=head[u.id];i;i=a[i].nxt) if(u.val+a[i].val<dis[a[i].to]) dis[a[i].to]=u.val+a[i].val,q.push({a[i].to,dis[a[i].to]});
	}
}
int main(){
	scanf("%d%d",&n,&m);
	len=std::max((int)sqrt(n/3),1);
	/*int */pp=n;
	for(int i=1;i<=len;i++) for(int j=1;j<=n;j++) add(num(i,j),j,0);
	for(int i=1;i<=len;i++) for(int j=1;j<=n;j++) if(i+j<=n) add(num(i,j),num(i,i+j),1),add(num(i,i+j),num(i,j),1);
	for(int i=1,p;i<=m;i++){
		scanf("%d%d",&building[i],&p);
		building[i]++;
		if(p<=len) add(building[i],num(p,building[i]),0)/*,printf("%d %d\n",building[i],num[p][building[i]])*/;
		else{
			for(int j=1;building[i]+p*j<=n;j++) add(building[i],building[i]+p*j,j);
			for(int j=1;building[i]-p*j>=1;j++) add(building[i],building[i]-p*j,j);
		}
	}
	Dijkstra(building[1]);
	if(dis[building[2]]==0x3f3f3f3f) puts("-1");
	else printf("%d",dis[building[2]]);
	return 0;
}

莫队

对于某些区间问题，可以考虑使用莫队求解。

考虑暴力离线求解区间询问。

对于暴力法，我们应该以左端点为第一关键字，右端点为第二关键字。但是，由于询问之间的波动可能很大，所以，暴力法的时间复杂度为 \(O(mn)\)，无法通过测试。

但是，我们可以考虑以下优化。

把数组分成长度为 \(\sqrt{n}\) 的若干块，然后把查询的区间按左端点所在块的序号排序，如果左端点的块相同，再按右端点排序。其他步骤与暴力法完全相同。

可证得，不带修莫队的时间复杂度为 \(O(m \sqrt{n} + n \sqrt{n})\)。

模板代码：

[HH的项链](M - HH的项链 | CQNK (nks.edu.cn))

#include<stdio.h>
#include<algorithm>
#include<math.h>
const int N=1e6+5;
int n,m,a[N],id[N],cnt[N],ans[N],ANS,len;
struct node{
	int l,r,k;
	bool operator < (const node &x) const{return id[l]==id[x.l]? (id[l]&1? r>x.r:r<x.r):id[l]<id[x.l];}
}q[N];
void add(int x){ANS+=++cnt[a[x]]==1;}
void del(int x){ANS-=!--cnt[a[x]];}
int main(){
	scanf("%d",&n);
	len=(int)sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[i]=(i-1)/len+1;
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].k=i;
	std::sort(q+1,q+m+1);
	int L=1,R=0;
	for(int i=1;i<=m;i++){
		while(L<q[i].l) del(L++);
		while(R>q[i].r) del(R--);
		while(L>q[i].l) add(--L);
		while(R<q[i].r) add(++R);
		ans[q[i].k]=ANS;
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

带修莫队

与不带修莫队类似，只是多了一维时间维。

注意，由分析可得带修莫队的时间复杂度为 \(O(mS + mS + \frac{m n^2}{S^2})\)，其中 \(S\) 表示块长。

当 \(S=n^{\frac{2}{3}}\) 时，有较好时间复杂度为 \(O(m n^{\frac{2}{3}})\)。

若 \(S=\sqrt{n}\)，则时间复杂度为 \(O(mn)\)，退化为暴力法。

模板代码：

[[莫队]数颜色](N - 【莫队】数颜色 | CQNK (nks.edu.cn))

#include<stdio.h>
#include<algorithm>
#include<math.h>
const int N=1e6+5;
int n,m,a[N],id[N],cnt[N],ans[N],ANS,len,L,R;
struct node{
	int l,r,time,k;
	bool operator < (const node &x) const{return id[l]==id[x.l]? (id[r]==id[x.r]? time<x.time:id[r]<id[x.r]):id[l]<id[x.l];}
}q[N];
struct chan{int wei,old,xin;}change[N];
void add(int x){ANS+=((++cnt[a[x]])==1);}
void del(int x){ANS-=(!(--cnt[a[x]]));}
void update(int x,int y){
	if(L<=x&&x<=R) del(x);
	a[x]=y;
	if(L<=x&&x<=R) add(x);
}
int p1,p2;
int main(){
	scanf("%d%d",&n,&m);
	int len=(int)pow(n,2.0/3.0);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[i]=(i-1)/len+1;
	char ch[2];
	int x,y;
	while(m--){
		scanf("%s%d%d",ch,&x,&y);
		if(*ch=='Q') p1++,q[p1]=/**/{x,y,p2,p1};
		else change[++p2]=/**/{x,a[x],y},a[x]=y;
	}
	std::sort(q+1,q+p1+1);
	int T=p2;
	L=1,R=0;
	for(int i=1;i<=p1;i++){
//		printf("%d %d %d\n",q[i].l,q[i].r,q[i].time);
		while(L<q[i].l) del(L++);
		while(R>q[i].r) del(R--);
		while(L>q[i].l) add(--L);
		while(R<q[i].r) add(++R);
		while(T<q[i].time) T++,update(change[T].wei,change[T].xin);
		while(T>q[i].time) update(change[T].wei,change[T].old),T--;
		ans[q[i].k]=ANS;
	}
	for(int i=1;i<=p1;i++) printf("%d\n",ans[i]);
	return 0;
}

矩阵

一个 \(m\) 行 \(n\) 列的矩阵（记作 \(m \times n\)）的矩阵用二维数组 \(ma[][]\) 存储，其中 \(ma[i][j]\) 表示第 \(i\) 行第 \(j\) 列的元素的值。

矩阵加减法

把两个矩阵对应位置的元素相加减即可。要求两个矩阵的行、列数相同。

矩阵乘法

\(1.\) 一个数 \(k\) 程矩阵 \(A\)，把 \(k\) 乘以矩阵的每个元素，记作 \(kA\)。

\(2.\) 两个矩阵 \(A\) 和 \(B\) 相乘，要求 \(A\) 的列数等于 \(b\) 的行数。设 \(A\) 的尺寸为 \(m \times n\)，\(B\) 的尺寸为 \(n \times k\)，那么乘积 \(C=AB\) 的尺寸为 \(m \times k\)。矩阵乘法 \(C=AB\) 的计算公式为：\(c[i][j]=\sum \limits _{k=1}^{n}A[i][k] \times B[k][j]\)。计算时间复杂度为 \(O(mnk)\)。

矩阵模板

struct matrix{
	ll n,m;
	ll ma[N][N];
	matrix(ll p=0,ll q=0){
		n=p,m=q;
		for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) ma[i][j]=0;
	}
	matrix operator + (const matrix &x) const{
		matrix c=matrix(n,m);
		for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) c.ma[i][j]=(ma[i][j]+x.ma[i][j])%mod;
		return c;
	}
	matrix operator * (const matrix &x) const{
		matrix c=matrix(n,x.m);
		for(ll i=1;i<=n;i++)
			for(ll k=1;k<=m;k++)
				if(ma[i][k])
				    for(ll j=1;j<=x.m;j++)
						c.ma[i][j]=(c.ma[i][j]+ma[i][k]*x.ma[k][j]%mod)%mod;
		return c;
	}
}A,f;//mod为模数