[NOIP2017 提高组] 列队 题解

题解"/>

[NOIP2017 提高组] 列队 题解

数据结构。

n = 1 n=1 n=1 的 case：考虑有 m + q m+q m+q 个位置，出队的人直接添加到队尾。维护位置对应的人，每次查询第 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 y=m 时只用查最后一列。

实现考虑离线树状树组或动态开点线段树，线段树 / 树状树组上二分可以做到 log ⁡ \log log，总时间复杂度 O ( n log ⁡ n ) O(n \log n) O(nlogn)。

树状树组实现显然要离线，仅用一个 BIT 预处理每次非最后一列操作在对应行的位置。

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 3e5 + 5; 
const int V = 6e5;int n, m, q, tree[N<<1], 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 i=20; i>=0; 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 i=1; i<=V; i++) tree[i] = lowbit(i);vector <vector<int>> cmd(n+1);for(int i=1; i<=q; i++){cin >> x[i] >> y[i];if(y[i] != m) cmd[x[i]].push_back(i);}for(int i=1; i<=n; 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 <vector<int>> row(n+1);vector <int> column;for(int i=1; i<=q; i++){int in, out, p = select(x[i]); add(p, -1);if(y[i] != m){out = (num[i] < m) ? ((x[i]-1)*m+num[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";	}
}