洛谷 P1960 列队
2024-10-06 10:01:41
题意简述
有一个n × m 的矩阵,第i行第j列元素编号为(i - 1)× m +j
每次将一个数取出,其他元素依次向左,向上填补空缺,最后将取出的数放入矩阵最后一格
求每次取出数的编号
题解思路
由于最后一列较为特殊,只有当取出的数位于最后一列,向上填补空缺时才有影响,所有特殊考虑
对于每一行的(m - 1)个元素 和 最后一列元素都维护一个splay
进行删除第k个元素 和 在末尾插入元素 两个操作
代码
#include <cstdio>
#include <cassert>
using namespace std;
typedef long long ll;
struct Node
{
ll l, r;
Node *c[2];
int s;
Node() {l = r = 0; s = 0; c[0] = c[1] = 0; }
Node(ll x) {l = r = x; s = 1; c[0] = c[1] = 0; }
Node(ll l, ll r) {this -> l = l; this -> r = r; s = r - l + 1; c[0] = c[1] = 0; }
int get(bool b){return c[b] ? c[b] -> s : 0; }
void upt(){s = get(0) + get(1) + (r - l + 1); }
int cmp(int x){return (x > get(0) && x <= get(0) + r - l + 1) ? -1 : x > get(0); }
}*r[300010];
int n, m, q, x, y;
void rtt(Node* &o, bool b)
{
Node* t = o -> c[b ^ 1];
o -> c[b ^ 1] = t -> c[b];
t -> c[b] = o;
o -> upt();
t -> upt();
o = t;
}
void splay(Node* &o, int k)
{
if (!o) return;
int d1 = o -> cmp(k);
if (d1 == -1) return;
int xx = k - d1 * (o -> s - o -> get(1));
int d2 = o -> c[d1] -> cmp(xx);
if (d2 == -1) rtt(o, d1 ^ 1);
else
{
splay(o -> c[d1] -> c[d2], xx - d2 * (o -> c[d1] -> s - o -> c[d1] -> get(1)));
if (d1 == d2) rtt(o, d2 ^ 1);
else rtt(o -> c[d1], d2 ^ 1);
rtt(o, d1 ^ 1);
}
}
void ins(Node* &o, Node* x)
{
if (!o) {o = x; return; }
splay(o, o -> s);
o -> c[1] = x;
o -> upt();
}
Node* del(Node* &o, int k)
{
splay(o, k);
if (o -> l == o -> r)
{
Node* t = o;
if (!o -> c[0]) o = o -> c[1];
else
{
splay(o -> c[0], o -> get(0));
o -> c[0] -> c[1] = o -> c[1];
o = o -> c[0];
o -> upt();
}
t -> s = 1;
t -> c[0] = t -> c[1] = 0;
return t;
}
ll xxx = o -> l + k - o -> get(0) - 1;
Node* x = new Node(o -> l, xxx - 1);
o -> l = xxx + 1;
x -> c[0] = o -> c[0];
o -> c[0] = x;
x -> upt();
o -> upt();
return new Node(xxx);
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (register int i = 1; i <= n; ++i)
{
r[i] = new Node((ll)(i - 1) * m + 1, (ll)i * m - 1);
ins(r[0], new Node((ll)i * m));
}
for (register int i = 1; i <= q; ++i)
{
scanf("%d%d", &x, &y);
Node* idx;
if (y == m)
{
printf("%lld\n", (idx = del(r[0], x)) -> l);
ins(r[0], idx);
}
else
{
ins(r[x], del(r[0], x));
printf("%lld\n", (idx = del(r[x], y)) -> l);
ins(r[0], idx);
}
}
}
最新文章
- 再次记录 Visual Studio 2015 CTP 5 的一个坑
- 理解ip和端口
- C#保存图片设置图片质量的方法
- 如何优化tomcat配置(从内存、并发、缓存4个方面)优化
- 3D模型文件读写.Net SDK
- Hibernate复合主键映射
- VMware Player 使用错误集锦
- 【百度地图API】北京周边7日游——图标按路线轨迹行动
- 源码分析Android Handler是如何实现线程间通信的
- 响应式、手机端、自适应 百分比实现div等宽等高的方法
- GBK和UTF8有什么区别
- BZOJ_2595_[Wc2008]游览计划_斯坦纳树
- k8s部署使用Dashboard(十)--技术流ken
- 中文多分类 BERT
- python 爬取历史天气
- 聚类分析K均值算法讲解
- 一个无锁消息队列引发的血案(三)——地:q3.h 与 RingBuffer
- js 社会主义点击事件
- mysql执行SQL语句时报错:[Err] 3 - Error writing file &#39;/tmp/MYP0G1B8&#39; (Errcode: 28 - No space left on device)
- 第三方苹果开发库之ASIHTTPRequest