淘宝网站图片维护怎么做,佛山做优化的网络公司,怎么改网站标题,2022永久免费的看电视软件数据结构。 n 1 n1 n1 的 case#xff1a;考虑有 m q mq mq 个位置#xff0c;出队的人直接添加到队尾。维护位置对应的人#xff0c;每次查询第 k k k 个人的位置。
实现考虑维护 01 序列#xff0c;表示位置上是 / 否有人#xff0c;每次查前缀和为 k k k 的位置即…数据结构。 n 1 n1 n1 的 case考虑有 m q mq mq 个位置出队的人直接添加到队尾。维护位置对应的人每次查询第 k k k 个人的位置。
实现考虑维护 01 序列表示位置上是 / 否有人每次查前缀和为 k k k 的位置即可。
一般情况每次操作只会影响某一行以及最后一列。考虑将最后一列单独处理。
对于查询 ( x , y ) (x,y) (x,y)需查询第 x x x 行第 y y y 个人的位置以及最后一列第 x x x 个人的位置维护一下对应编号 y m y m ym 时只用查最后一列。
实现考虑离线树状树组或动态开点线段树线段树 / 树状树组上二分可以做到 log \log log总时间复杂度 O ( n log n ) O(n \log n) O(nlogn)。
树状树组实现显然要离线仅用一个 BIT 预处理每次非最后一列操作在对应行的位置。
#includebits/stdc.h
#define int long long
using namespace std;const int N 3e5 5;
const int V 6e5;int n, m, q, tree[N1], x[N], y[N], num[N];int lowbit(int x) {return x(-x);}
void add(int x, int d){for(;x V; x lowbit(x)) tree[x] d;}
int select(int k)
{int pos 0, sum 0;for(int i20; i0; i--){pos (1 i);if(pos V or sum tree[pos] k) pos - (1 i);else sum tree[pos];}return pos 1;
}signed main()
{ios::sync_with_stdio(0); cin.tie(0);cin n m q;for(int i1; iV; i) tree[i] lowbit(i);vector vectorint cmd(n1);for(int i1; iq; i){cin x[i] y[i];if(y[i] ! m) cmd[x[i]].push_back(i);}for(int i1; in; i){for(auto id : cmd[i])num[id] select(y[id]), add(num[id], -1);for(auto id : cmd[i]) add(num[id], 1);}vector vectorint row(n1);vector int column;for(int i1; iq; i){int in, out, p select(x[i]); add(p, -1);if(y[i] ! m){out (num[i] m) ? ((x[i]-1)*mnum[i]) : row[x[i]][num[i]-m], in (p n) ? (p*m) : column[p-n-1];row[x[i]].push_back(in), column.push_back(out);}else{out (p n) ? (p*m) : column[p-n-1];column.push_back(out);}cout out \n; }
}
