# BZOJ4717 改装

Posted by yjjr's blog on January 1, 2018

# 题目

改装(reequip.pas/c/cpp/in/out) 【题目背景】

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 【数据规模和约定】

# 分析

50分暴力，爆零的同学交由监考老师处理。只拿了10分的同学看看自己是不是忽略了什么。

k=1的时候最大值就是两边最大值乘在一起，两个RMQ解决。其实这10分没拿到的也应该交给监考老师处理。

# 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;
{
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()
{
while(q--){
if(opt==0){
if(type==0)a[pos]=val;else b[pos]=val;
}else{
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;
}