比赛链接：Here
ABC水题，
D - Cutting Woods
题意：开始一根木棒长度为 \(n\) 并以 \(1\) 为单位在木棒上标记\((1\sim n)\) ，输出 \(q\) 次操作
- 操作 \(1\) 断开 \(x\) 所在的木棒：\([1,n]\) 在 \(x\) 断开变成了 \([1,x],[x + 1,n]\)
- 操作 \(2\) 查询 \(x\) 所在区间的长度
数据范围：\(n\le 10^{9},q\le 1e5,1\le x\le 1e9\)
题解：
一开始没有想到这个性质所以卡住了，
在分割之后左边以及右边这个区间的答案是固定的，也就是说答案只跟分割点有关，比如区间 \([l,r]\) 分割 \(x\)? 变成了 \([l,x],[x+1,r]\)
可以发现可以发现
\(l\) 到 \(x\) 这个区间的询问答案都是 \(x?l+1\)
\(x+1\) 到 \(r\) 这个区间的询问答案都是 \(r?l+1\)
所以可以考虑二分找到所在区间相邻 \(2\) 个的分割点下标
先考虑边界问题
边界无非是：\(0\sim n + 1,0\sim n,1\sim n,1\sim n +1\) 这 \(4\)? 种的其中一种
这个时候先假设区间是 \([1,2],[3,4],[5]\)?
分割点是 0/1 2 4 5/5+1
对于查询2
找到第一个大于等于2的数是2
第一个小于2的数应该是 0/1
答案是2
所以应该是 2 - 0 = 2
左边界应该是0在考虑查询5
答案是1
找到第一个大于等于5的数是5/6
第一个小于5的数应该是4
所以应该是 5 - 4 = 1
右边界是n在考虑二分操作的时候 分割点数组保持有序
所以可以用set动态维护
时间复杂度：\(\mathcal{O}(Nlog N)\)
set<int>s;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
s.insert(0);
s.insert(n);
while (m--) {
int c, x;
cin >> c >> x;
if (c == 1) s.insert(x);
else
cout << *s.lower_bound(x) - *--s.upper_bound(x) << "\n";
// 因为没 -- 调了半天
}
}
E - Sorting Queries
题意：给出一个空的序列和 \(q\) 次操作
- 操作 \(1\)：? 在序列末尾添加一个数 \(x\)
- 操作 \(2\) ：输出序列第一个数
- 操作 \(3\)：给当前序列排序
数据范围：\(q\le 1e5,1\le x\le 1e9\)?
题解：
假设不考虑操作 \(3\)，那么我们可直接模拟，
但在操作 \(3\)的影响下，需要维护排序对队列的影响，
假设队列中两个元素，\(head，fail\) 对应队头和队尾
暴力时间复杂度是 \(\mathcal{O}(n^2 logn)\) 肯定是不可取的
在排序的时候我们可以考虑边插入边排序，用 \(set\)? 维护
然后把对头指向 \(set\) 后面的第一个下标
这样时间复杂度便降到了 \(\mathcal{O}(n logn)\)
const int N = 1e6 + 10;
ll a[N];
multiset<ll>s;
bool st[N];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int head = 0, fail = 0;
int t; cin >> t;
int k = 1; // k = 1 表示队列第一个数的下标是1
while (t--) {
int op; cin >> op;
if (op == 1) {
int x; cin >> x;
a[++fail] = x;
} else if (op == 2) {
// 如果排序过
if (s.size()) {
cout << *s.begin() << "\n" ;
s.erase(s.begin());
} else {
cout << a[k] << "\n";
st[k] = 1;
k += 1;
}
} else {
for (int i = k ; i <= fail ; i ++) {
if (!st[i]) s.insert(a[i]) ;
}
// 插入之后 对头指向队尾的下一个下标
k = fail + 1 ;
}
}
}