购物网站开发文档mvc,自己做博客网站,wordpress手机软件,陵川网站建设文章目录引整体二分几道模板题Dynamic Rankings[ZJOI2013]K大数查询[国家集训队]矩阵乘法[THUPC2017] 天天爱射击[CTSC2018]混合果汁引 例1. 给定 nnn 个数 aia_iai#xff0c;一次询问#xff0c;询问区间 [l,r][l,r][l,r] 中的第 kkk 小数。 我们通常想到二分答案#x…
文章目录引整体二分几道模板题Dynamic Rankings[ZJOI2013]K大数查询[国家集训队]矩阵乘法[THUPC2017] 天天爱射击[CTSC2018]混合果汁引 例1. 给定 nnn 个数 aia_iai一次询问询问区间 [l,r][l,r][l,r] 中的第 kkk 小数。 我们通常想到二分答案然后计数在 [l,r][l,r][l,r] 区间内 ≤x\le x≤x 的数的个数再与 kkk 比较。
时间复杂度 O(nlogn)O(n\log n)O(nlogn)。尽管这并不是最优秀的做法 例2. 给定 nnn 个数 aia_iai多次询问询问区间 [1,n][1,n][1,n] 中的第 kkk 小数。 由于区间是整个数列所以我们直接排序一下然后找第 kkk 个数即可时间复杂度 O(nlogn)O(n\log n)O(nlogn)。 例3. 给定 nnn 个数 aia_iai多次询问询问区间 [l,r][l,r][l,r] 中的第 kkk 小数。 这是一道主席树即可持久化线段树的模板题。建立权值线段树然后 rrr 版本 −l-l−l 版本线段树上二分。
实际上我们仍然可以用二分做。
但如果对于每一个询问都二分一次那么时间复杂度 O(qnlogn)O(qn\log n)O(qnlogn) 就爆炸了。
是否可以只用一次二分呢——答案是显然的。
我们理想的一次二分应该是二分一个答案 xxx然后利用一个数据结构快速判断答案和每一个询问的大小关系再将询问分成 ≤x,x\le x,x≤x,x 的两部分分别二分下去。
不难发现这种假想的时间复杂度大概是带两个 logloglog 的。 例4. 给定 nnn 个数 aia_iai多次询问和修改某个位置的值询问区间 [l,r][l,r][l,r] 中的第 kkk 小数。 线段树分治不清楚。但这仍可以二分做。
整体二分
“引”中最后假想出来的思路就是 整体二分 。
能用整体二分解决的题目需要满足以下性质
答案具有可二分性。修改对判断答案的贡献相互独立即修改之间互不影响。修改如果有贡献则是确定的贡献不会随二分的答案产生变化。贡献满足交换律结合律具有广义的可加性。离线。
总体算法思路
记 [l,r][l,r][l,r] 为二分答案的值域[ql,qr][ql,qr][ql,qr] 为定义域即只考虑编号在 [ql,qr][ql,qr][ql,qr] 中的修改和询问操作这其中的询问的答案在 [l,r][l,r][l,r] 内。首先把所有操作按 时间顺序 存入数组。通常输入顺序即为操作的时间顺序。然后开始分治。在每一层的分治中利用数据结构常见为树状数组/线段树统计当前查询的答案和 mid\text{mid}mid 的关系。根据查询的答案和 mid\text{mid}mid 之间的关系分成 L,RL,RL,R 两份分别递归。类比线段树分治每一个分治的子问题都是互不相关的但却共用同一个数据结构。所以这里还要涉及到回退问题。当 lrlrlr 时[ql,qr][ql,qr][ql,qr] 中的所有询问答案即为 lll。 下面以主席树的模板题作为例题具体阐释算法实现以及时间复杂度的计算。 将输入 aia_iai 的操作定义为类型 111即 q[i].op1q[i].op1q[i].op1。并记录下 q[i]q[i]q[i] 修改的位置 iii修改的值 aia_iai。 将查询 [l,r],k[l,r],k[l,r],k 的操作定义为类型 222。并记录下询问的区间kkk 。 对于一个形如 (l,r,ql,qr)(l,r,ql,qr)(l,r,ql,qr) 的子问题二分答案为 midlr1midlr1midlr1。 然后处理 [ql,qr][ql,qr][ql,qr] 范围内的类型 111 操作。 修改的值 ≤mid\le mid≤mid 的。 全都扔到数据结构上。这里使用的是树状数组 则树状数组上放的是 ≤mid\le mid≤mid 的且在 [ql,qr][ql,qr][ql,qr] 操作区间内的修改操作。 再放入 LLL 数组中。 修改的值 midmidmid 的。 这种修改对于 midmidmid 答案没有贡献直接放进 RRR 数组中。 对于 [ql,qr][ql,qr][ql,qr] 范围中的类型 222 操作。直接询问树状数组中 [q[i].l,q[i].r][q[i].l,q[i].r][q[i].l,q[i].r] 区间内的个数 cntcntcnt。 如果 cnt≤q[i].kcnt\le q[i].kcnt≤q[i].k。 也就是说 [q[i].l,q[i].r][q[i].l,q[i].r][q[i].l,q[i].r] 中 ≤mid\le mid≤mid 的数 ≤k\le k≤k 个。答案要么是 midmidmid 要么 midmidmid。 根据二分原则我们把这个询问放到 LLL 数组中。 如果 cntq[i].kcntq[i].kcntq[i].k。 类比线段树二分我们将 q[i].kq[i].kq[i].k 减去 cntcntcnt。然后放到 RRR 数组中。 因为到时候处理 (mid1,r,ql′,qr′)(mid1,r,ql,qr)(mid1,r,ql′,qr′) 的子问题时原本 [q[i].l,q[i].r][q[i].l,q[i].r][q[i].l,q[i].r] 中 ≤mid\le mid≤mid 的数时一定会提供 111 的个数我们没有必要每次都加入。 将数据结构回退至当前层未操作前的模样。 此时的 LLL 数组放的询问是真正 ans≤midans\le midans≤mid 的询问放的修改是重新计算时还可能被挂到树状数组上去的修改。 RRR 数组同理。我们已经去掉了 LLL 数组中所有修改对 RRR 中询问产生的贡献。 现在两个数组之间的信息是完全不会有交的了。 所以分治处理 (l,mid,L),(mid1,r,R)(l,mid,L),(mid1,r,R)(l,mid,L),(mid1,r,R)。
#include bits/stdc.h
using namespace std;
#define maxn 400005
#define inf 0x7f7f7f7f
int n, m;
int ans[maxn];
struct node { int op, l, r, k, id; }q[maxn], Left[maxn], Right[maxn];namespace BIT {int t[maxn];void add( int i, int x ) { for( ;i n;i i -i ) t[i] x; }int ask( int i ) { int cnt 0; for( ;i;i - i -i ) cnt t[i]; return cnt; }
}void solve( int l, int r, int ql, int qr ) {if( ql qr ) return;if( l r ) { for( int i ql;i qr;i ) if( q[i].op 2 ) ans[q[i].id] l;return;}int mid l r 1, cntL 0, cntR 0;for( int i ql;i qr;i )if( q[i].op 1 ) {if( q[i].k mid ) Right[ cntR] q[i];else BIT :: add( q[i].id, 1 ), Left[ cntL] q[i];}else {int cnt BIT :: ask( q[i].r ) - BIT :: ask( q[i].l - 1 );if( q[i].k cnt ) Left[ cntL] q[i];else q[i].k - cnt, Right[ cntR] q[i];}for( int i 1;i cntL;i ) if( Left[i].op 1 ) BIT :: add( Left[i].id, -1 );for( int i 1;i cntL;i ) q[i ql - 1] Left[i];for( int i 1;i cntR;i ) q[i ql cntL - 1] Right[i];solve( l, mid, ql, ql cntL - 1 );solve( mid 1, r, ql cntL, qr );
}int main() {scanf( %d %d, n, m );for( int i 1, x;i n;i ) {scanf( %d, x );q[i] (node){ 1, -inf, inf, x, i };}for( int i 1, l, r, k;i m;i ) {scanf( %d %d %d, l, r, k );q[i n] (node){ 2, l, r, k, i };}solve( -inf, inf, 1, n m );for( int i 1;i m;i ) printf( %d\n, ans[i] );return 0;
}最后来分析一下这个时间复杂度
首先是二分的答案值O(logV)O(\log V)O(logV) 的。对于同一层的分治总共的区间定义域是 O(n)O(n)O(n)。类比线段树 1,2,41,2,41,2,4 的划分但同一层的总和仍是 nnn。每个数在同一层的若干个分治中最多只会被挂在数据结构上一次然后撤销。时间复杂度应为 O(nlognlogV)O(n\log n\log V)O(nlognlogV)。
几道模板题
Dynamic Rankings
Dynamic Rankings
本题才是真的修改操作即“引”中的例4 。
其实也没有什么特别的可以类比线段树分治一个数存在时间是一段连续的区间。
具体见代码即可明白。
#include bits/stdc.h
using namespace std;
#define maxn 400005
struct node { int op, x, y, k, id; }q[maxn], L[maxn], R[maxn];
int n, m;
int ans[maxn], a[maxn];namespace BIT {int t[maxn];void add( int i, int x ) { for( ;i n;i i -i ) t[i] x; }int ask( int i ) { int cnt 0; for( ;i;i - i -i ) cnt t[i]; return cnt; }
}void solve( int l, int r, int ql, int qr ) {if( ql qr ) return;if( l r ) { for( int i ql;i qr;i ) if( q[i].op 2 ) ans[q[i].id] l; return; }int mid l r 1;int cntl 0, cntr 0;for( int i ql;i qr;i )if( q[i].op 2 ) {int cnt BIT :: ask( q[i].y ) - BIT :: ask( q[i].x - 1 );if( q[i].k cnt ) L[ cntl] q[i];else q[i].k - cnt, R[ cntr] q[i];}else {if( q[i].x mid ) BIT :: add( q[i].k, q[i].y ), L[ cntl] q[i];else R[ cntr] q[i];}for( int i ql;i qr;i )if( q[i].op 1 and q[i].x mid )BIT :: add( q[i].k, -q[i].y );for( int i 1;i cntl;i ) q[i ql - 1] L[i];for( int i 1;i cntr;i ) q[i ql cntl - 1] R[i];solve( l, mid, ql, ql cntl - 1 );solve( mid 1, r, ql cntl, qr );
}int main() {int cnt 0, Max 0;scanf( %d %d, n, m );for( int i 1;i n;i ) {scanf( %d, a[i] );q[ cnt] (node){ 1, a[i], 1, i, cnt };Max max( Max, a[i] );}char op[10]; int x, y, k;for( int i 1;i m;i ) {scanf( %s, op );if( op[0] Q ) {scanf( %d %d %d, x, y, k );q[ cnt] (node) { 2, x, y, k, cnt };}else {scanf( %d %d, x, y );q[ cnt] (node){ 1, a[x], -1, x, cnt };a[x] y;q[ cnt] (node){ 1, a[x], 1, x, cnt };Max max( Max, y );}}solve( 0, Max, 1, cnt );sort( q 1, q cnt 1, []( node x, node y ) { return x.id y.id; } );for( int i 1;i cnt;i )if( q[i].op 2 ) printf( %d\n, ans[q[i].id] );return 0;
}[ZJOI2013]K大数查询
[ZJOI2013]K大数查询
注意这里是 kkk 大数不是 kkk 小数。
那么二分答案时候把 midmidmid 的挂上去即可。
或者你整体取相反数后做 kkk 小数最后输出答案再取反回来也行。
#include bits/stdc.h
using namespace std;
#define maxn 50005
#define int long long
struct node { int op, x, y, k, id; }q[maxn], L[maxn], R[maxn];
int n, m;
int ans[maxn];namespace SGT {struct node { int cnt, tag; }t[maxn 2];#define lson now 1#define rson now 1 | 1#define mid (l r 1)void pushdown( int now, int l, int r ) {if( ! t[now].tag ) return;t[lson].tag t[now].tag;t[lson].cnt t[now].tag * (mid - l 1);t[rson].tag t[now].tag;t[rson].cnt t[now].tag * (r - mid);t[now].tag 0;}void modify( int now, int l, int r, int L, int R, int x ) {if( R l or r L ) return;if( L l and r R ) { t[now].tag x; t[now].cnt x * (r - l 1); return; }pushdown( now, l, r );modify( lson, l, mid, L, R, x );modify( rson, mid 1, r, L, R, x );t[now].cnt t[lson].cnt t[rson].cnt;}int query( int now, int l, int r, int L, int R ) {if( R l or r L ) return 0;if( L l and r R ) return t[now].cnt;pushdown( now, l, r );return query( lson, l, mid, L, R ) query( rson, mid 1, r, L, R );}#undef lson#undef rson#undef mid
}void solve( int l, int r, int ql, int qr ) {if( ql qr ) return;if( l r ) { for( int i ql;i qr;i ) ans[q[i].id] l; return; }int mid l r 1;int cntl 0, cntr 0;for( int i ql;i qr;i )if( q[i].op 1 ) {if( q[i].k mid ) SGT :: modify( 1, 1, n, q[i].x, q[i].y, 1 ), R[ cntr] q[i];else L[ cntl] q[i];}else {int cnt SGT :: query( 1, 1, n, q[i].x, q[i].y );if( q[i].k cnt ) R[ cntr] q[i];else q[i].k - cnt, L[ cntl] q[i];}for( int i 1;i cntr;i )if( R[i].op 1 )SGT :: modify( 1, 1, n, R[i].x, R[i].y, -1 );for( int i 1;i cntl;i ) q[ql i - 1] L[i];for( int i 1;i cntr;i ) q[ql i cntl - 1] R[i];solve( mid 1, r, ql cntl, qr );solve( l, mid, ql, ql cntl - 1 );
}signed main() {scanf( %lld %lld, n, m );for( int i 1, op, x, y, k;i m;i ) {scanf( %lld %lld %lld %lld, op, x, y, k );q[i] (node){ op, x, y, k, i };}solve( -n, n, 1, m );sort( q 1, q m 1, []( node x, node y ) { return x.id y.id; } );for( int i 1;i m;i ) if( q[i].op 2 ) printf( %lld\n, ans[q[i].id] );return 0;
}[国家集训队]矩阵乘法
[国家集训队]矩阵乘法
数据结构用二维树状数组即可。
#include bits/stdc.h
using namespace std;
#define maxn 505
#define maxm 400005
struct node { int op, l1, r1, l2, r2, k, id; }q[maxm], L[maxm], R[maxm];
int n, m;
int ans[maxm];namespace BIT {int t[maxn][maxn];void add( int x, int y, int v ) {for( int i x;i n;i i -i )for( int j y;j n;j j -j )t[i][j] v;}int ask( int x, int y ) {int cnt 0;for( int i x;i;i - i -i )for( int j y;j;j - j -j )cnt t[i][j];return cnt;}
}void solve( int l, int r, int ql, int qr ) {if( qr ql ) return;if( l r ) { for( int i ql;i qr;i ) ans[q[i].id] l; return; }int mid l r 1;int cntl 0, cntr 0;for( int i ql;i qr;i )if( q[i].op 1 ) {if( q[i].k mid ) BIT :: add( q[i].l1, q[i].r1, 1 ), L[ cntl] q[i];else R[ cntr] q[i];}else {int cnt BIT :: ask( q[i].l2, q[i].r2 ) - BIT :: ask( q[i].l1 - 1, q[i].r2 ) - BIT :: ask( q[i].l2, q[i].r1 - 1 ) BIT :: ask( q[i].l1 - 1, q[i].r1 - 1 );if( q[i].k cnt ) L[ cntl] q[i];else q[i].k - cnt, R[ cntr] q[i];}for( int i 1;i cntl;i ) if( L[i].op 1 ) BIT :: add( L[i].l1, L[i].r1, -1 );for( int i 1;i cntl;i ) q[ql i - 1] L[i];for( int i 1;i cntr;i ) q[ql cntl i - 1] R[i];solve( l, mid, ql, ql cntl - 1 );solve( mid 1, r, ql cntl, qr );
}int main() {scanf( %d %d, n, m );int cnt 0;for( int i 1;i n;i )for( int j 1, x;j n;j ) {scanf( %d, x );q[ cnt] (node){ 1, i, j, i, j, x, cnt };}for( int i 1, l1, r1, l2, r2, k;i m;i ) {scanf( %d %d %d %d %d, l1, r1, l2, r2, k );q[ cnt] (node){ 2, l1, r1, l2, r2, k, cnt };}solve( 0, 1e9, 1, cnt );sort( q 1, q cnt 1, []( node x, node y ) { return x.id y.id; } );for( int i 1;i cnt;i ) if( q[i].op 2 ) printf( %d\n, ans[q[i].id] );return 0;
}[THUPC2017] 天天爱射击
[THUPC2017] 天天爱射击
直接从子弹入手并不好做这里稍微绕个弯当我们知道所有木板最后一次被哪颗子弹射中就能统计出每个子弹射穿的木板数。
所以应当以木板为因变量。考虑每次二分最后被射击的子弹 midmidmid然后 check\text{check}check 前 midmidmid 个子弹能否射穿该木板。
发现这个可以整体二分做。
这里的 [l,r][l,r][l,r] 不再是权值而是二分的子弹编号。
我们这里依然把子弹和木板放在同一个操作数组里面子弹为类型 111木板为类型 222。
注意两种操作的时间顺序安排我们应该是先把所有子弹打了过后再检查该木板被射中的次数是否达到承载值。
单点修改区间查询树状数组可做。
如果次数到达承载值证明可能在更早时刻就已经被射穿放入左边否则放入右边递归分治。
#include bits/stdc.h
using namespace std;
#define maxn 400005
struct node { int op, x, y, k, id; }q[maxn], L[maxn], R[maxn];
int n, m;
int ans[maxn];namespace BIT {int t[maxn];void add( int i, int x ) { for( ;i maxn;i i -i ) t[i] x; }int ask( int i ) { int cnt 0; for( ;i;i - i -i ) cnt t[i]; return cnt; }
}void solve( int l, int r, int ql, int qr ) {if( ql qr ) return;if( l r ) { for( int i ql;i qr;i ) if( q[i].op 2 ) ans[l] ; return; }int mid l r 1;int cntl 0, cntr 0;for( int i ql;i qr;i )if( q[i].op 1 ) {if( q[i].k mid ) BIT :: add( q[i].x, 1 ), L[ cntl] q[i];else R[ cntr] q[i];}else {int cnt BIT :: ask( q[i].y ) - BIT :: ask( q[i].x - 1 );if( q[i].k cnt ) L[ cntl] q[i];else q[i].k - cnt, R[ cntr] q[i];}for( int i 1;i cntl;i ) if( L[i].op 1 ) BIT :: add( L[i].x, -1 );for( int i 1;i cntl;i ) q[ql i - 1] L[i];for( int i 1;i cntr;i ) q[ql cntl i - 1] R[i];solve( l, mid, ql, ql cntl - 1 );solve( mid 1, r, ql cntl, qr );
}int main() {scanf( %d %d, n, m );for( int i 1, x, y, k;i n;i ) {scanf( %d %d %d, x, y, k );q[i m] (node){ 2, x, y, k, i m };}for( int i 1, x;i m;i ) {scanf( %d, x );q[i] (node){ 1, x, 0, i, i };}solve( 1, m 1, 1, n m );for( int i 1;i m;i ) printf( %d\n, ans[i] );return 0;
}[CTSC2018]混合果汁
[CTSC2018]混合果汁
显然我们可以整体二分最低的美味度 midmidmid。
然后把所有美味度 ≥mid\ge mid≥mid 的果汁都放入数据结构中。
但果汁有钱数和购买上限。
在二分后有个显然的贪心越便宜的越先买。
我们可以用权值线段树以单价为下标然后记录总个数和总支付钱数。
查询时先看左区间再看右区间。查询买最便宜的 lll 个的钱数是否在小朋友承受范围内。
但这里我们发现好像这里的贡献提前去掉和前面几个模板题目不太一样。因为当 midmidmid 移动时可能会加入更便宜的果汁所以我们不能在现在就把某些小朋友的钱数减去一部分。
那怎么办——我们直接不减就只是把小朋友不断分组即可。
每次撤销就类似莫队用一个指针移动。仔细想想可见下面代码每一种果汁最多上线段树两次。
总时间复杂度是可以保证的。
本题我将果汁和小朋友两种操作分开存的可能更直白一点。
这里的顺序不再是时间顺序而是果汁美味度大小的顺序。
#include bits/stdc.h
using namespace std;
#define int long long
#define maxn 100005
struct juice { int d, p, l; }g[maxn];
struct child { int g, l, id; }q[maxn], L[maxn], R[maxn];
int n, m, now;
int ans[maxn];namespace SGT {struct node { int cnt, sum; }t[maxn 2];#define lson now 1#define rson now 1 | 1#define mid (l r 1)void modify( int p, int x, int now 1, int l 1, int r 1e5 ) {if( l r ) { t[now].cnt x; t[now].sum x * p; return; }if( p mid ) modify( p, x, lson, l, mid );else modify( p, x, rson, mid 1, r );t[now].cnt t[lson].cnt t[rson].cnt;t[now].sum t[lson].sum t[rson].sum;}int query( int x, int now 1, int l 1, int r 1e5 ) {if( ! x ) return 0;if( l r ) return l * x;if( x t[lson].cnt ) return query( x, lson, l, mid );else return t[lson].sum query( x - t[lson].cnt, rson, mid 1, r );}#undef lson#undef rson#undef mid
}void solve( int l, int r, int ql, int qr ) {if( ql qr ) return;if( l r ) { for( int i ql;i qr;i ) ans[q[i].id] g[l].d; return; }int mid l r 1;while( now mid ) now, SGT :: modify( g[now].p, g[now].l );while( mid now ) SGT :: modify( g[now].p, -g[now].l ), now --;int cntl 0, cntr 0;for( int i ql;i qr;i ) {if( SGT :: t[1].cnt q[i].l ) R[ cntr] q[i];else if( SGT :: query( q[i].l ) q[i].g ) L[ cntl] q[i];else R[ cntr] q[i];}for( int i 1;i cntl;i ) q[ql i - 1] L[i];for( int i 1;i cntr;i ) q[ql cntl i - 1] R[i];solve( l, mid, ql, ql cntl - 1 );solve( mid 1, r, ql cntl, qr );
}signed main() {scanf( %lld %lld, n, m );for( int i 1;i n;i ) scanf( %lld %lld %lld, g[i].d, g[i].p, g[i].l );for( int i 1;i m;i ) scanf( %lld %lld, q[i].g, q[i].l ), q[i].id i;sort( g 1, g n 1, []( juice x, juice y ) { return x.d y.d; } );g[ n] { -1, 0, (int)1e18 };solve( 1, n, 1, m );for( int i 1;i m;i ) printf( %lld\n, ans[i] );return 0;
}
