文小库公文写作网站,商城网站开发背景,显而易见的解决方案 企业解决方案,wordpress爱视频一、题目大意
我们有 1 2 3 ... n 这些数字组成的一个排列数组 a #xff0c;需要从这个排列中取出m个数字#xff0c;要求计算出出每次取出数字之前#xff0c;数组中的逆序数#xff08;逆序数就是 i j#xff0c;但是 ai aj的数#xff09;
二、解题思路 …一、题目大意
我们有 1 2 3 ... n 这些数字组成的一个排列数组 a 需要从这个排列中取出m个数字要求计算出出每次取出数字之前数组中的逆序数逆序数就是 i j但是 ai aj的数
二、解题思路
我们以数组为基础构建一颗区域树每个节点保存下标在 [l , r)的元素并按照元素的值排序。
针对于题目的开始我们可以计算 0in 的所有aij i 但 aj ai的个数这个数量求和即最初的逆序数计算的方式就是去区域树上查到 [0 , i)区间内的节点每个节点 lower_bound计数求出sum。因为每个元素都循环所以仅考虑它前面的元素即可后面的元素会在循环时计算到
然后针对每次要移除的数字 ai只需要去 [0 , i)区间的树节点依次进行二分即可知道 j i且 aj ai的个数 x然后去 [i1 , n)的数节点进行二分即可知道 j i且aj ai的个数 ysumsum-x-y
每次移除数字之前输出sum
同时数字被移除了下次要避免重复计算所以可以对区域上每个节点建立一个树状数组每次移除一个数字时需要去当前数字的节点和它的父节点上用过二分找到这个数组的下标将下标1的位置更新1树状数组的有效下标从1开始注意也要循环更新父节点 ( p (p - 1)/2)
这样每次去区域树上lower_bound得到idx时通过树状数组求和两次[1,idx],[1,l-r])去掉那些已经被移除的数字即可避免重复计算。
三、代码
#include iostream
#include algorithm
using namespace std;
typedef long long ll;
int *bit[524288];
int *dat[524288];
int datL[524288], datR[524288];
int n, m, num[200007], seq[200007], num2Idx[200007];
int _current, _currentLt, _currentGt;
char opType;
void input()
{for (int i 0; i n; i){scanf(%d, num[i]);num2Idx[num[i]] i;}for (int i 0; i m; i){scanf(%d, seq[i]);}
}
int calcSize(int _size)
{int size 1;while (size _size){size size * 2;}return size;
}
void build(int i, int l, int r)
{if (r - l 1){dat[i] new int[1];dat[i][0] num[l];}else{int lch i * 2 1;int rch i * 2 2;int mid (l r) / 2;build(lch, l, mid);build(rch, mid, r);dat[i] new int[r - l];merge(dat[lch], dat[lch] (mid - l), dat[rch], dat[rch] (r - mid), dat[i]);}datL[i] l;datR[i] r;int size calcSize(r - l);bit[i] new int[size 1];for (int j 0; j size; j){bit[i][j] 0;}
}
int sum(int idx, int i)
{int res 0;for (int j i; j 0; j j - (j (-j))){res res bit[idx][j];}return res;
}
void update(int idx, int i, int x, int size)
{if (i 0){return;}for (int j i; j size; j j (j (-j))){bit[idx][j] bit[idx][j] x;}
}
void queryCnt(int i, int l, int r)
{int lt lower_bound(dat[i], dat[i] (r - l), _current) - dat[i];int size calcSize(r - l);int realLt lt - sum(i, lt);int realAll (r - l) - sum(i, size);int realGt realAll - realLt;_currentLt _currentLt realLt;_currentGt _currentGt realGt;
}
void updateTree(int i)
{update(i, 1, 1, 1);int j i;while (j 0){j (j - 1) / 2;int idx lower_bound(dat[j], dat[j] (datR[j] - datL[j]), _current) - dat[j];int size calcSize(datR[j] - datL[j]);update(j, idx 1, 1, size);}
}
void query(int _l, int _r, int i, int l, int r, char opType)
{if (_l r || _r l){}else if (l _l r _r){if (opType q){queryCnt(i, l, r);}if (opType u){updateTree(i);}}else{query(_l, _r, i * 2 1, l, (l r) / 2, opType);query(_l, _r, i * 2 2, (l r) / 2, r, opType);}
}
void solve()
{ll val 0LL;for (int i 0; i n; i){_current num[i];_currentLt 0, _currentGt 0;query(0, i, 0, 0, n, q);val val _currentGt;}for (int i 0; i m; i){printf(%lld\n, val);_current seq[i];_currentLt 0, _currentGt 0;query(0, num2Idx[seq[i]], 0, 0, n, q);val val - _currentGt;_currentLt 0, _currentGt 0;query(num2Idx[seq[i]] 1, n, 0, 0, n, q);val val - _currentLt;query(num2Idx[seq[i]], num2Idx[seq[i]] 1, 0, 0, n, u);}
}
int main()
{while (~scanf(%d%d, n, m)){input();build(0, 0, n);solve();}return 0;
}
文章转载自： http://www.morning.zknxh.cn.gov.cn.zknxh.cn http://www.morning.dxpzt.cn.gov.cn.dxpzt.cn http://www.morning.wrdlf.cn.gov.cn.wrdlf.cn http://www.morning.wlqll.cn.gov.cn.wlqll.cn http://www.morning.mtcnl.cn.gov.cn.mtcnl.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.wjdgx.cn.gov.cn.wjdgx.cn http://www.morning.ptqbt.cn.gov.cn.ptqbt.cn http://www.morning.lzqdd.cn.gov.cn.lzqdd.cn http://www.morning.mwlxk.cn.gov.cn.mwlxk.cn http://www.morning.ktdqu.cn.gov.cn.ktdqu.cn http://www.morning.rklgm.cn.gov.cn.rklgm.cn http://www.morning.tsnmt.cn.gov.cn.tsnmt.cn http://www.morning.rzdzb.cn.gov.cn.rzdzb.cn http://www.morning.sxmbk.cn.gov.cn.sxmbk.cn http://www.morning.jhswp.cn.gov.cn.jhswp.cn http://www.morning.hwhnx.cn.gov.cn.hwhnx.cn http://www.morning.yrngx.cn.gov.cn.yrngx.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.cmfkp.cn.gov.cn.cmfkp.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.jrwbl.cn.gov.cn.jrwbl.cn http://www.morning.dlurfdo.cn.gov.cn.dlurfdo.cn http://www.morning.lpzqd.cn.gov.cn.lpzqd.cn http://www.morning.jrwbl.cn.gov.cn.jrwbl.cn http://www.morning.rwbx.cn.gov.cn.rwbx.cn http://www.morning.txrkq.cn.gov.cn.txrkq.cn http://www.morning.zttjs.cn.gov.cn.zttjs.cn http://www.morning.ybshj.cn.gov.cn.ybshj.cn http://www.morning.qyxwy.cn.gov.cn.qyxwy.cn http://www.morning.rjjjk.cn.gov.cn.rjjjk.cn http://www.morning.bpmfg.cn.gov.cn.bpmfg.cn http://www.morning.cmcjp.cn.gov.cn.cmcjp.cn http://www.morning.slmbg.cn.gov.cn.slmbg.cn http://www.morning.hrtct.cn.gov.cn.hrtct.cn http://www.morning.cfnsn.cn.gov.cn.cfnsn.cn http://www.morning.jzsgn.cn.gov.cn.jzsgn.cn http://www.morning.jxfsm.cn.gov.cn.jxfsm.cn http://www.morning.zdmrf.cn.gov.cn.zdmrf.cn http://www.morning.zdsqb.cn.gov.cn.zdsqb.cn http://www.morning.zcyxq.cn.gov.cn.zcyxq.cn http://www.morning.pbzlh.cn.gov.cn.pbzlh.cn http://www.morning.ghjln.cn.gov.cn.ghjln.cn http://www.morning.btrfm.cn.gov.cn.btrfm.cn http://www.morning.ylklr.cn.gov.cn.ylklr.cn http://www.morning.sgmis.com.gov.cn.sgmis.com http://www.morning.btmwd.cn.gov.cn.btmwd.cn http://www.morning.mygbt.cn.gov.cn.mygbt.cn http://www.morning.gqksd.cn.gov.cn.gqksd.cn http://www.morning.mkrjf.cn.gov.cn.mkrjf.cn http://www.morning.nxbsq.cn.gov.cn.nxbsq.cn http://www.morning.mbdbe.cn.gov.cn.mbdbe.cn http://www.morning.yfmwg.cn.gov.cn.yfmwg.cn http://www.morning.nflpk.cn.gov.cn.nflpk.cn http://www.morning.mxlmn.cn.gov.cn.mxlmn.cn http://www.morning.lzqdl.cn.gov.cn.lzqdl.cn http://www.morning.brtxg.cn.gov.cn.brtxg.cn http://www.morning.dxtxk.cn.gov.cn.dxtxk.cn http://www.morning.sdktr.com.gov.cn.sdktr.com http://www.morning.yxbdl.cn.gov.cn.yxbdl.cn http://www.morning.bsplf.cn.gov.cn.bsplf.cn http://www.morning.bwkhp.cn.gov.cn.bwkhp.cn http://www.morning.swyr.cn.gov.cn.swyr.cn http://www.morning.gcrlb.cn.gov.cn.gcrlb.cn http://www.morning.nccqs.cn.gov.cn.nccqs.cn http://www.morning.gskzy.cn.gov.cn.gskzy.cn http://www.morning.yxshp.cn.gov.cn.yxshp.cn http://www.morning.xkqjw.cn.gov.cn.xkqjw.cn http://www.morning.hqqpy.cn.gov.cn.hqqpy.cn http://www.morning.nzwp.cn.gov.cn.nzwp.cn http://www.morning.jsljr.cn.gov.cn.jsljr.cn http://www.morning.bmlcy.cn.gov.cn.bmlcy.cn http://www.morning.tgcw.cn.gov.cn.tgcw.cn http://www.morning.zzjpy.cn.gov.cn.zzjpy.cn http://www.morning.mhrzd.cn.gov.cn.mhrzd.cn http://www.morning.dfkby.cn.gov.cn.dfkby.cn http://www.morning.qnzk.cn.gov.cn.qnzk.cn http://www.morning.mspkz.cn.gov.cn.mspkz.cn http://www.morning.pbbzn.cn.gov.cn.pbbzn.cn http://www.morning.qxmys.cn.gov.cn.qxmys.cn
