BZOJ4717 改装

Posted by yjjr's blog on January 1, 2018

标签:二分,树状数组,平衡树

题目

题目传送门

	改装(reequip.pas/c/cpp/in/out) 【题目背景】
小Q最近喜欢上了一款游戏,名为《舰队connection》,在游戏中,小Q指挥强大的舰队南征北战,从而成为了一名dalao。
在游戏中,不仅船只能力很重要,搭配合适的装备更是如虎添翼。小Q潜心研究配装三十年,终于——把装备凑齐了。 【题意描述】
小Q有n艘船,m件装备。为了简单起见,我们假定每艘船都只能携带一件装备,且可以携带任何一件装备。每艘船和每件装备都有自己的能力值。船携带装备时,能力值为两者相乘。
另外,小q还有可能对船或装备进行改修(强化)。改修成功会让能力提升,失败则会让能力降低。
由于最佳配置已经用了无数次了毫无挑战性,因此,小Q并不打算直接使用最佳配置,而是使用相对弱一些的第k佳配置。
具体来说,每次选择船只时,由于关卡限制,小Q需要在编号为L到R的船只中选择一艘,并在编号为a和b之间的装备选择一架,组成出击用的船只。于是,小Q总共有(R-L+1)*(b-a+1)种选择,小Q希望知道,所有这些选择中,第k大的能力值是多少。
例如:
船只:5 3 7
装备:4 2 1 8 16
对于L=1,R=3,a=1,b=5,k=10的询问,将所有可能的能力值排序,分别为7*16=102,5*16=80,7*8=56,3*16=48,5*8=40,7*4=28,3*8=24,5*4=20,7*2=14,3*4=12,5*2=10,7*1=7,3*2=6,5*1=5,3*1=3,其中第10大的是12。
对于L=2,R=3,a=2,b=4,k=5的询问,将所有可能的能力值排序,分别为7*8=56,3*8=24,7*2=16,7*1=7,3*2=6,3*1=3,其中第5大的是6。
假定小Q改修了第二艘船使其能力值成功增加至4,并改修了第5件装备但由于失败使得它的能力值减小为9。
现在,对于L=1,R=2,A=4,B=5,K=3的询问,所有可能的能力值分别为5*9=45,5*8=40,4*9=36,4*8=32,其中第3大的是36。
现在,你要编写一个程序回答这些问题。

提示:由于游戏的特殊性,装备比船多得不知道到哪里去了,另外,作为一个人类,小Q才不会在一秒钟之内问几百万个问题让你回答,他只会问几百个,而且给你好几秒钟的时间回答。 【输入格式】
第一行两个数n,m,空格分隔,表示小Q的船的数量和装备的数量。
第二行n个数,空格分隔,表示小Q的船的能力值(按编号)。
第三行m个数,空格分隔,表示小Q的装备的能力值(按编号)。
第四行一个数q,表示小q的操作数量。
接下来q行,每行描述一个操作,操作要么为一个改修事件,要么为一个询问。
对于改修事件,该行4个数0,type,pos,val,type为0或1,0表示把pos号船改修成val的能力值,1表示把pos号装备改修成val的能力值。
对于询问操作,该行6个数1,L,R,a,b,k,空格分隔,表示一个询问。 【输出格式】
对于每个询问操作,输出一行,包含一个数,表示询问的答案。 【样例输入】
3 5
5 3 7
4 2 1 8 16
5
1 1 3 1 5 10
1 2 3 2 4 5
0 0 2 4
0 1 5 9
1 1 2 4 5 3 【样例输出】
12
6
36 【数据规模和约定】
对于100%的数据,n<=250,m<=100000,q<=100000,其中询问操作不会超过200。
对于100%的数据,1<=L<=R<=n,1<=a<=b<=m,1<=k<=(R-L+1)*(b-a+1),任何时候船能力值为不超过2000的正整数,装备能力值为不超过1000000的正整数。
本题共20个测试点。
对于1,2号数据:n,m<=10,q<=20。
对于3,4号数据:k=1。
对于5,6,7,8号数据:n=1。
对于9,10,11,12号数据:n<=5。
对于1,3,5,7,9,11,13,15,17,19号数据:没有修改操作。
标程使用了读入优化。
提醒:本题空间限制较严格,请在提交前确认空间未溢出。 【时间和空间限制】
时间限制以标程在评测环境下的最大数值2倍向上取整为准。
空间限制以标程在评测环境下的最大数值2倍向上取整至2的整次幂为准。
如标程在所有测试点的最大耗时为2.4s,最大空间消耗为160MB,则时间限制应为5s,空间限制应为512MB。
如有需要,该数值应在考试前测出并向选手公示。

分析

再次吐槽出题人,编故事能力过于强大

简要题意:给定两个数组a,b,定义数组c[i,j]=a[i]*b[j],支持修改a或b中的一个元素或者查询c中的子矩阵内第k大值

注意到修改操作最多只有200次,所以很容易水过了,然而我只拿了40分暴力(暴力拿满是50分)(感觉全世界都AC了T1和T2)

实际上可以两次二分解决,问题划归为询问值x在当前两个区间内第几大

先二分询问值x,然后枚举船只,二分累和对应船只的搭配武器中比x大的数量,然后判断累和和k的大小

标程竟然达到了4K%%%

下面复制一段出题人的题解

50分暴力,爆零的同学交由监考老师处理。只拿了10分的同学看看自己是不是忽略了什么。
暴力AC的同学可以向大家传授一下卡常数经验。(附注:第k大是可以O(len)求的,不用排序)
k=1的时候最大值就是两边最大值乘在一起,两个RMQ解决。其实这10分没拿到的也应该交给监考老师处理。
原本n=1和n=5是给各种一维第k大的,结果标程不给力时限太长就扔给暴力了= =。
标算:因为n和查询都比较小,所以想办法把n乘到查询上。第k大用二分做,二分出来的值除以n那一维的值,然后再到m这维查询,就变成了形如“l到r区间内比x小的有少个”。用树状数组套平衡树解决。总复杂度O(mlogm+qnlogClog2m)。
一开始没料到三次的log这么慢,不过应该还是比暴力快的。
这里特意卡了一下内层用线段树的内存,因为二分的时候不同行位置不一样,导致线段树无法体现出按走势二分的优势,所以这里用平衡树是复杂度不变但是节约内存的做法。另外据说外层换成线段树也会炸内存……

code

二分水法

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1e5+6;
int a[maxn],b[maxn],c[maxn],n,m,q,len,l,r,L,R,k,type,pos,val,low,high;
inline int judge(int x,int rk){
	int l=1,r=len+1;
	while(l<r){
		int mid=(l+r)>>1;
		if(x*c[mid]<rk)l=mid+1;else r=mid;
	}
	return len-l+1;
}
	
int main()
{
	n=read(),m=read();
	rep(i,1,n)a[i]=read();
	rep(i,1,m)b[i]=read();
	q=read();
	while(q--){
		int opt=read();
		if(opt==0){
			type=read(),pos=read(),val=read();
			if(type==0)a[pos]=val;else b[pos]=val;
		}else{
			L=read(),R=read(),l=read(),r=read(),k=read();
			len=r-l+1;low=high=0;
			rep(i,l,r)c[i-l+1]=b[i];
			sort(c+1,c+1+len);
			rep(i,L,R)high=max(high,a[i]*c[len]+1);
			while(low<high){//二分总的能力值 
				int num=0;
				int mid=((ll)low+high)>>1;
				rep(i,L,R)num+=judge(a[i],mid);//对于每个能力值,枚举船,然后二分能带多少个装备 
				if(num<k)high=mid;else low=mid+1;
			}
			printf("%d\n",high-1);
		}
	}
	return 0;
}

std

#include <cstdio>
#include <algorithm>
const	int	maxn = 110000;
const	int	maxs = 1100000;
const	int	top = 2000000000;
const	int	maxm = 260;
typedef	long long	ll;
typedef	unsigned int	ui;
int	vm[maxm], vn[maxn];
int	n, m, q, lm, rm, ln, rn, k, pos, val;
ui	lf, ri, mid, sum;
inline	int	getint()
{
	char	ch = getchar(); int x = 0;
	while (ch < '0' || ch > '9') ch = getchar();
	while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x;
}
struct	Gen
{
	ll	x;
	int	k, p;
	Gen()	{}
	Gen(int x) : x(x) {k = 31; p = 0x78000001;}
	int	g()	{return x = (k * x) % p;}
}	G('O'*'I');
struct	bittreap
{
	struct	node
	{
		int	size, x, w;
		node	*s[2];
		node()	{}
		node(int x) : size(1), x(x) {s[0] = s[1] = 0; w = G.g();}
		void	update() {size = 1 + (s[0] ? s[0]->size : 0) + (s[1] ? s[1]->size : 0);}
	};
	static	bool	cmp(node *p, node *q) {return p->x < q->x;}
	node	*root[maxn], *list[maxn], *stack[maxn];
	node	*p, *q, *r;
	int	n, num, back;
	struct	Mem
	{
		node	pond[maxs];
		int	back;
		Mem()	{back = 0;}
		node*	mynew() {return &pond[back++];}
		node*	mynew(const node &p) {return &(pond[back++] = p);}
	}	M;
	void	split(node *p, int x, node* &p1, node* &p2)
	{
		if (!p) {p1 = p2 = 0; return;}
		if (p->x <= x) {split(p->s[1], x, p1, p2); p->s[1] = p1; (p1 = p)->update();}
		else {split(p->s[0], x, p1, p2); p->s[0] = p2; (p2 = p)->update();}
	}
	void	splits(node *p, node* &p1, node* &p2)
	{
		if (p->s[0]) {splits(p->s[0], p1, p2); p->s[0] = p2; (p2 = p)->update(); return;}
		p1 = p; p2 = p->s[1]; p->s[1] = 0; p->update();
	}
	node*	merge(node *p1, node *p2)
	{
		if (!p1) return p2; if (!p2) return p1;
		if (p1->w < p2->w) {p1->s[1] = merge(p1->s[1], p2); p1->update(); return p1;}
		else {p2->s[0] = merge(p1, p2->s[0]); p2->update(); return p2;}
	}
	int	query(node *p, int v)
	{
		if (!p) return 0;
		if (p->x <= v) return (p->s[0] ? p->s[0]->size : 0) + 1 + query(p->s[1], v);
		else return query(p->s[0], v);
	}
	void	preset(int nn, int *a)
	{
		n = nn;
		for (int i=1; i<=n; i++) root[i] = 0;
		for (int i=n; i; i--) for (int u=i; u<=n; u+=(u&(-u)))
		{
			node *p = M.mynew(node(a[i]));
			p->s[1] = root[u]; root[u] = p;
		}
		for (int i=1; i<=n; i++)
		{
			for (num = 0; root[i]; root[i] = root[i]->s[1]) list[++num] = root[i];
			std::sort(list + 1, list + num + 1, cmp);
			for (int j=1; j<=num; j++)
			{
				for (list[j]->s[0] = 0; back && stack[back]->w >= list[j]->w; list[j]->s[0] = stack[back--]) stack[back]->update();
				list[j]->s[1] = 0; if (back) stack[back]->s[1] = list[j]; stack[++back] = list[j];
			}
			while (back) stack[back--]->update();
			if (num) root[i] = stack[1];
		}
	}
	void	change(int pos, int val1, int val2)
	{
		for (int u=pos; u<=n; u+=(u&(-u)))
		{
			split(root[u], val1-1, p, q);
			splits(q, q, r);
			*q = node(val2);
			split(merge(p, r), val2, p, r);
			root[u] = merge(p, merge(q, r));
		}
	}
	int	query(int l, int r, int v)
	{
		int ans = 0;
		for (int u=r; u; u-=(u&(-u))) ans += query(root[u], v);
		for (int u=l-1; u; u-=(u&(-u))) ans -= query(root[u], v);
		return ans;
	}
}	tool1;
int	main()
{
	freopen("reequip.in", "r", stdin);
	freopen("reequip.out", "w", stdout);
	m = getint(); n = getint();
	for (int i=1; i<=m; i++) vm[i] = getint();
	for (int i=1; i<=n; i++) vn[i] = getint();
	tool1.preset(n, vn);
	q = getint();
	for (int i=1; i<=q; i++)
	{
		if (getint())
		{
			lm = getint(); rm = getint(); ln = getint(); rn = getint(); k = (rm - lm + 1) * (rn - ln + 1) - getint() + 1;
			lf = 1; ri = top;
			while (lf < ri)
			{
				mid = (lf + ri) >> 1; sum = 0;
				for (int j=lm; j<=rm; j++) sum += tool1.query(ln, rn, mid / vm[j]);
				if (sum < k) lf = mid + 1; else ri = mid;
			}
			printf("%d\n", lf);
		}
		else
		{
			if (getint())
			{
				pos = getint(); val = getint();
				tool1.change(pos, vn[pos], val); vn[pos] = val;
			}
			else
			{
				pos = getint(); val = getint();
				vm[pos] = val;
			}
		}
	}
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr