差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:整体二分 [2020/07/30 15:29]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:整体二分 [2020/07/30 18:48] (当前版本)
jxm2001
@@ 行 8: / 行 8: @@
 ==== 动态区间第 $k$ 小 ====
+[[https://www.luogu.com.cn/problem/P2617|洛谷p2617]]
 === 题意 ===
@@ 行 115: / 行 117: @@
 	_rep(i,1,q_cnt)
 	enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+===== 算法练习 =====
+==== 习题一 ====
+[[https://www.luogu.com.cn/problem/P1527|洛谷p1527]]
+=== 题意 ===
+给定一个长度为 $n\times n$ 矩阵，$q$ 次询问。每次询问子矩阵中第 $k$ 大元素。
+=== 题解 ===
+参考算法例题中没有修改操作的一维序列区间第 $k$ 大做法，考虑二分过程中转移元素和询问。
+使用二维树状数组维护名次，总时间复杂度 $O\left(n^2\log^3 n\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=505,MAXQ=6e4+5;
+struct Num{
+	int x,y,v;
+	bool operator < (const Num &b){
+		return v<b.v;
+	}
+}a[MAXN*MAXN];
+struct Query{
+	int x1,y1,x2,y2,k,id;
+}q[MAXQ],q1[MAXQ],q2[MAXQ];
+int n,c[MAXN][MAXN],ans[MAXQ];
+#define lowbit(x) ((x)&(-x))
+void add(int x,int y,int v){
+	for(int i=x;i<=n;i+=lowbit(i))
+	for(int j=y;j<=n;j+=lowbit(j))
+	c[i][j]+=v;
+}
+int get_s(int x,int y){
+	int ans=0;
+	for(int i=x;i;i-=lowbit(i))
+	for(int j=y;j;j-=lowbit(j))
+	ans+=c[i][j];
+	return ans;
+}
+int query(int x1,int y1,int x2,int y2){
+	return get_s(x2,y2)-get_s(x1-1,y2)-get_s(x2,y1-1)+get_s(x1-1,y1-1);
+}
+void solver(int ql,int qr,int vl,int vr){
+	if(ql>qr)return;
+	int vm=vl+vr>>1;
+	if(vl==vr){
+		_rep(i,ql,qr)ans[q[i].id]=a[vm].v;
+		return;
+	}
+	_rep(i,vl,vm)add(a[i].x,a[i].y,1);
+	int cnt1=0,cnt2=0,pos=ql;
+	_rep(i,ql,qr){
+		int r=query(q[i].x1,q[i].y1,q[i].x2,q[i].y2);
+		if(q[i].k<=r)q1[++cnt1]=q[i];
+		else{
+			q2[++cnt2]=q[i];
+			q2[cnt2].k-=r;
+		}
+	}
+	_rep(i,vl,vm)add(a[i].x,a[i].y,-1);
+	_rep(i,1,cnt1)q[pos++]=q1[i];
+	_rep(i,1,cnt2)q[pos++]=q2[i];
+	solver(ql,qr-cnt2,vl,vm);solver(ql+cnt1,qr,vm+1,vr);
+}
+int main()
+{
+	n=read_int();
+	int m=read_int(),cnt=0,x1,y1,x2,y2;
+	_rep(i,1,n)_rep(j,1,n)
+	a[++cnt]=Num{i,j,read_int()};
+	sort(a+1,a+cnt+1);
+	_rep(i,1,m){
+		x1=read_int(),y1=read_int(),x2=read_int(),y2=read_int();
+		q[i]=Query{x1,y1,x2,y2,read_int(),i};
+	}
+	solver(1,m,1,cnt);
+	_rep(i,1,m)
+	enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题二 ====
+[[https://www.luogu.com.cn/problem/P3527|洛谷p3527]]
+=== 题意 ===
+给定一个长度为 $m$ 的环，每个节点有一个所属国家。$k$ 次事件，每次对 $[l,r]$ 顺时针环形区间上的每个点点权加上一个值。
+每个国家有一个期望值 $p_i$，求每个国家最早多少次操作之后属于该国家的所有点的点权和能不小于 $p_i$。
+=== 题解 ===
+首先把考虑如何把环上修改转化成线段修改，发现将每个 $[l,r](l\gt r)$ 事件拆成 $[l,m],[1,r]$ 事件即可。
+接下来直接整体二分，计算贡献时差分 $+$ 树状数组维护区间修改 $+$ 单点查询操作，每个国家暴力查询属于他的点集的点权和。
+发现每层修改时间复杂度 $O(m\log m)$，查询复杂度也是 $O(m\log m)$，共 $O(\log m)$ 层。
+于是总时间复杂度 $O(m\log^2 m)$。事实上本题存在 $O(m\log m)$ 做法，有兴趣的可以自行思考。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5,Inf=1e9;
+struct Num{
+	int l,r,v,t;
+}a[MAXN<<1];
+vector<int> ch[MAXN];
+struct Query{
+	int k,id;
+}q[MAXN],q1[MAXN],q2[MAXN];
+int m,ans[MAXN];
+LL c[MAXN];
+#define lowbit(x) ((x)&(-x))
+void add(int lef,int rig,int v){
+	int pos=lef;
+	while(pos<=m){
+		c[pos]+=v;
+		pos+=lowbit(pos);
+	}
+	pos=rig+1;
+	while(pos<=m){
+		c[pos]-=v;
+		pos+=lowbit(pos);
+	}
+}
+LL query(int idx){
+	LL ans=0;
+	_for(i,0,ch[idx].size()){
+		int pos=ch[idx][i];
+		while(pos){
+			ans+=c[pos];
+			pos-=lowbit(pos);
+		}
+		if(ans>Inf)
+		return ans;
+	}
+	return ans;
+}
+void solver(int ql,int qr,int vl,int vr){
+	if(ql>qr)return;
+	int vm=vl+vr>>1;
+	if(vl==vr){
+		_rep(i,ql,qr)ans[q[i].id]=a[vm].t;
+		return;
+	}
+	_rep(i,vl,vm)add(a[i].l,a[i].r,a[i].v);
+	int cnt1=0,cnt2=0,pos=ql;
+	_rep(i,ql,qr){
+		LL r=query(q[i].id);
+		if(q[i].k<=r)q1[++cnt1]=q[i];
+		else{
+			q2[++cnt2]=q[i];
+			q2[cnt2].k-=r;
+		}
+	}
+	_rep(i,vl,vm)add(a[i].l,a[i].r,-a[i].v);
+	_rep(i,1,cnt1)q[pos++]=q1[i];
+	_rep(i,1,cnt2)q[pos++]=q2[i];
+	solver(ql,qr-cnt2,vl,vm);solver(ql+cnt1,qr,vm+1,vr);
+}
+int main()
+{
+	int n=read_int(),cnt=0,lef,rig,v;
+	m=read_int();
+	_rep(i,1,m)
+	ch[read_int()].push_back(i);
+	_rep(i,1,n)
+	q[i]=Query{read_int(),i};
+	int k=read_int();
+	_rep(i,1,k){
+		lef=read_int(),rig=read_int(),v=read_int();
+		if(lef<=rig)
+		a[++cnt]=Num{lef,rig,v,i};
+		else{
+			a[++cnt]=Num{lef,m,v,i};
+			a[++cnt]=Num{1,rig,v,i};
+		}
+	}
+	solver(1,n,1,cnt+1);
+	_rep(i,1,n){
+		if(!ans[i])
+		puts("NIE");
+		else
+		enter(ans[i]);
+	}
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具