整体二分专题
A - K-th Number [POJ - 2104 ]
\(1 <= n <= 100 000, 1 <= m <= 5 000\), 给出数组\(a[1..n](\leq1e9)\)
然后有\(m\)个询问, 每次询问\(Q(l,r,k)\)求\(a[l..r]\)之间从小到大第\(k\)个的数
B - Dynamic Rankings [ZOJ-2112]
\(1 <= N <= 50,000 ~~~~ 1 <= M <= 10,000\), 给出数组\(a[1..n](\leq1e9)\)
然后有\(m\)个操作:
\(C~i~t\)将\(a[i]\)改为\(t\)
\(Q~i~j~k\)求\(a[l..r]\)之间从小到大第k个的数
C - K大数查询 [HYSBZ - 3110]
有\(N\)个位置，\(M\)个操作。操作有两种，每次操作如果是\(1~a~b~c\)的形式表示在第a个位置到第\(b\)个位置，每个位置加入一个数\(c\)
如果是\(2~a~b~c\)形式，表示询问从第\(a\)个位置到第\(b\)个位置，第\(C\)大的数是多少。【样例说明】
第一个操作 后位置 1 的数只有 1 ， 位置 2 的数也只有 1 。 第二个操作 后位置 1的数有 1 、 2 ，位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。
\(N,M<=50000,N,M<=50000\) \(a<=b<=N\)
1操作中\(abs(c)<=N\) 2操作中\(c<=Maxlongint\)
思路
A
将数组数值和询问一起放入操作序列\(a[]\)中
\(solve(x, y, l, r)\)代表操作编号在\([x,y]\)间的询问的答案在\([l,r]\)之间, 并且当前\([x,y]\)间的询问只能由\([x,y]\)之间的数值贡献
在\(solve()\)中:
- \(mid = (l + r) >> 1\), 假设询问的答案为\(mid\),那么要检查\(\leq mid\)的个数符不符合每个询问要求的个数
- 如果这个操作是数组中的数, 则
- 若\(\leq mid\), 则放入\(a_l[]\)中,这部分对之后的询问有贡献,将位置加入树状数组
- 否则放入\(a_r[]\)中
- 否则就是一个询问, 调用树状数组,求\(\leq mid\)的个数
- 如果\(\geq\)需要的个数,那么实际答案比\(mid\)小(等于), 放入\(a_l[]\)中
- 否则实际答案比\(mid\)大,减去现在贡献, 放入\(a_r[]\)中
将\(和放回a_l[]和a_r[]放回a[]\)中, \(区间区间solve(l区间,l,mid), solve(r区间, mid+1,r)\)
如果\(l==r\)则区间内的询问答案都确定了
到边界就return
#include#include #include #include #include using namespace std;typedef long long LL;const int MAXN = 1e5 + 10;const int INF = 1e9 + 10;inline int in(){ int x = 0, flag = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar(); return x * flag;}int n, m, tot;struct Fenwick{ int val[MAXN]; void upd(int x, int v) { for (int i = x; i <= 100000; i += (i & (-i))) val[i] += v; } int qry(int x) { int ret = 0; for (int i = x; i > 0; i &= (i - 1)) ret += val[i]; return ret; }} T;struct Node{ int v, l, r, p, typ, id;} a[MAXN << 1], al[MAXN << 1], ar[MAXN << 1];int an[MAXN];void solve(int x, int y, int l, int r){ if (l > r || x >= y) return ; if (l == r) { for (int i = x; i <= y; i ++) if (a[i].typ == 1) an[a[i].id] = l; return; } int mid = (l + r) >> 1; int cntl = 0, cntr = 0; for (int i = x; i <= y; i ++) { if (a[i].typ == 0) { if (a[i].v <= mid) al[++cntl] = a[i], T.upd(a[i].id, 1); else ar[++cntr] = a[i]; } else { int val = T.qry(a[i].r) - T.qry(a[i].l - 1); if (a[i].p <= val) al[++cntl] = a[i]; else a[i].p -= val, ar[++cntr] = a[i]; } } for (int i = x; i <= y; i ++) if (a[i].typ == 0 && a[i].v <= mid) T.upd(a[i].id, -1); for (int i = 1; i <= cntl; i ++) a[x + i - 1] = al[i]; for (int i = 1; i <= cntr; i ++) a[x + cntl + i - 1] = ar[i]; solve(x, x + cntl - 1, l, mid); solve(y - cntr + 1, y, mid + 1, r);}int main(){ n = in(); m = in(); for (int i = 1; i <= n; i ++) { a[++ tot].v = in(); a[tot].typ = 0; a[tot].id = i; } for (int i = 1; i <= m; i ++) { a[++ tot] = (Node) {0, in(), in(), in(), 1, i }; } solve(1, tot, -INF, INF); for (int i = 1; i <= m; i ++) printf("%d\n", an[i]); return 0;}
B
小改改(思考如何转化change)
C
小改改(思考如何处理区间而非前缀)