1、二分答案
2、基础数据结构，如树状数组，线段树。
首先，二分答案求最大值的最小值大概长成下面这个样子：
int solve(int l, int r)
{
while (l<r)
{
int mid=l+r>>1;
if (check(mid)) l=mid+1;
else r=mid;
}
return l;
}解决\(n\)次询问的时间复杂度就是\(O(n^2logn)\)
而整体二分就是用于在\(O(nlog^2n)\)的复杂度离线解决上述问题。
举一个例子，求静态区间K大。
考虑分治解决编号为\(L-R\)的操作询问的答案在\(l-r\)，每次讲答案二分（即\(mid=\frac{l+r}{2}\)）。
将\(L-R\)的修改操作按被修改数\(\leq mid\)和\(>mid\)分为\(1,2\)两部分，同时如果被修改数\(\leq mid\)，就在树状数组该位置上\(+1\)。
将\(L-R\)的询问操作按树状数组查询区间和\(\geq K\)个\(<K\)（即询问的\(K\)大）分为\(1,2\)两部分，\(<K\)的情况需要减去查询的区间和，然后分治\(1,2\)两部分即可。
一次分治的复杂度为\(O(nlogn)?\)，\(logn?\)次分治的复杂度即为\(O(nlog^2n)?\)
具体如下（只有主干部分，细节见例题代码）：
#define rep(i, l, r) for (int i=(l); i<=(r); ++i)
struct node{int l, r, k, id, type;}q[N], q1[N], q2[N];
//若type=1, 为第id个询问，询问[l,r]中k大
//若type=1，为第id个数，值为l
void solve(int l, int r, int L, int R)
{
if(l==r) rep(i, L, R) if (q[i].type) ans[q[i].id]=l;
int mid=l+r>>1, cnt1=0, cnt2=0;
rep(i, L, R)
if (q[i].type)
{
int k=query(q[i].r)-query(q[i].l-1);
if (k>=q[i].k) q1[++cnt1]=q[i];
else q2[++cnt2]=q[i], q[i].k-=k;
}
else
{
if (q[i].l<=mid) add(q[i].id, 1), q1[++cnt1]=q[i];
else q2[++cnt2]=q[i];
}
//清空树状数组
rep(i, 1, cnt1) q[L+i-1]=q1[i];
rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
solve(l, mid, L, L+cnt1-1);
solve(mid+1, r, L+cnt1, R);
}静态区间K大：K-th Number
#include<bits/stdc++.h>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=400005, inf=1e9;
struct node{int l, r, k, id, typ;}q[N], q1[N], q2[N];
int d[N], ans[N], n, m, cnt;
inline int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
void add(int x, int t){for (; x<=n; x+=x&-x) d[x]+=t;}
int query(int x){int res=1; for (; x; x-=x&-x) res+=d[x]; return res;}
void solve(int l, int r, int L, int R)
{
if (l>r || L>R) return;
if (l==r) {rep(i, L, R) if (q[i].typ) ans[q[i].id]=l; return;}
int mid=l+r>>1, cnt1=0, cnt2=0;
rep(i, L, R)
if (q[i].typ)
{
int tmp=query(q[i].r)-query(q[i].l-1);
if (tmp>=q[i].k) q1[++cnt1]=q[i];
else q[i].k-=tmp, q2[++cnt2]=q[i];
}
else
{
if (q[i].l<=mid) add(q[i].id, 1), q1[++cnt1]=q[i];
else q2[++cnt2]=q[i];
}
rep(i, 1, cnt1) if (!q1[i].typ) add(q1[i].id, -1);
rep(i, 1, cnt1) q[L+i-1]=q1[i];
rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
int main()
{
n=read(); m=read();
rep(i, 1, n) q[++cnt]=(node){read(), 0, 0, i, 0};
rep(i, 1, m) q[++cnt]=(node){read(), read(), read(), i, 1};
solve(-inf, inf, 1, cnt);
rep(i, 1, m) printf("%d\n", ans[i]);
return 0;
}
dalao：我会用主席树\(O(nlogn)\)在线解决该问题。
那整体二分是不是被吊锤了？看下面这题
即待修改的区间\(K\)大。
用整体二分与静态\(K\)大区别不大，只要注意修改时的处理即可。
细节见代码：
#include<bits/stdc++.h>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=500005, inf=1e9;
struct node{int l, r, k, id, typ;}q[N], q1[N], q2[N];
int d[N], ans[N], a[N], n, m, cnt, tot;
inline int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
void add(int x, int t){for (; x<=n; x+=x&-x) d[x]+=t;}
int query(int x){int res=0; for (; x; x-=x&-x) res+=d[x]; return res;}
void solve(int l, int r, int L, int R)
{
if (l>r || L>R) return;
if (l==r) {rep(i, L, R) if (q[i].typ) ans[q[i].id]=l; return;}
int mid=l+r>>1, cnt1=0, cnt2=0;
rep(i, L, R)
if (q[i].typ)
{
int tmp=query(q[i].r)-query(q[i].l-1);
if (tmp>=q[i].k) q1[++cnt1]=q[i];
else q[i].k-=tmp, q2[++cnt2]=q[i];
}
else
{
if (q[i].l<=mid) add(q[i].id, q[i].r), q1[++cnt1]=q[i];
else q2[++cnt2]=q[i];
}
rep(i, 1, cnt1) if (!q1[i].typ) add(q1[i].id, -q1[i].r);
rep(i, 1, cnt1) q[L+i-1]=q1[i];
rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
int main()
{
n=read(); m=read();
rep(i, 1, n) q[++cnt]=(node){a[i]=read(), 1, 0, i, 0};
rep(i, 1, m)
{
char opt[2]; scanf("%s", opt);
if (opt[0]=='Q')
q[++cnt]=(node){read(), read(), read(), ++tot, 1};
else
{
int x=read(), y=read();
q[++cnt]=(node){a[x], -1, 0, x, 0};
q[++cnt]=(node){a[x]=y, 1, 0, x, 0};
}
}
solve(-inf, inf, 1, cnt);
rep(i, 1, tot) printf("%d\n", ans[i]);
return 0;
}
dalao：我会树状数组套主席树的\(O(nlog^2n)\)在线算法。
但我不会啊QAQ
整体二分常数吊打树套树还好写QAQ
还是简单题 传送门
把第一个例题的树状数组改为二维树状数组即可。
你不会二维树状数组？我也不会
#include<bits/stdc++.h>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=500005, inf=1e9;
struct node{int x1, y1, x2, y2, k, id;}q[N], q1[N], q2[N];
int d[505][505], ans[N], n, m, cnt;
inline int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
void add1(int x, int y, int t){for (; y<=n; y+=y&-y) d[x][y]+=t;}
void add(int x, int y, int t){for (; x<=n; x+=x&-x) add1(x, y, t);}
int query2(int x, int y){int res=0; for (; y; y-=y&-y) res+=d[x][y]; return res;}
int query1(int x, int y){int res=0; for (; x; x-=x&-x) res+=query2(x, y); return res;}
int query(int x1, int y1, int x2, int y2)
{return query1(x2, y2)+query1(x1-1, y1-1)-query1(x1-1, y2)-query1(x2, y1-1);}
void solve(int l, int r, int L, int R)
{
if (l>r || L>R) return;
if (l==r) {rep(i, L, R) if (q[i].id) ans[q[i].id]=l; return;}
int mid=l+r>>1, cnt1=0, cnt2=0;
rep(i, L, R)
if (q[i].id)
{
int tmp=query(q[i].x1, q[i].y1, q[i].x2, q[i].y2);
if (tmp>=q[i].k) q1[++cnt1]=q[i];
else q[i].k-=tmp, q2[++cnt2]=q[i];
}
else
{
if (q[i].k<=mid) add(q[i].x1, q[i].y1, 1), q1[++cnt1]=q[i];
else q2[++cnt2]=q[i];
}
rep(i, 1, cnt1) if (!q1[i].id) add(q1[i].x1, q1[i].y1, -1);
rep(i, 1, cnt1) q[L+i-1]=q1[i];
rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
int main()
{
n=read(); m=read();
rep(i, 1, n) rep(j, 1, n)
q[++cnt]=(node){i, j, 0, 0, read(), 0};
rep(i, 1, m)
q[++cnt]=(node){read(), read(), read(), read(), read(), i};
solve(0, inf, 1, cnt);
rep(i, 1, m) printf("%d\n", ans[i]);
return 0;
}
原文：https://www.cnblogs.com/ACMSN/p/10680618.html