标签：二分，树状数组，平衡树
题目
改装(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;
}
