NEERC2018 K. King Kog’s Reception
题目链接
http://codeforces.com/contest/1089/problem/K
题目大意
国王给前来拜访的骑士设计了一个队列。如果他们到的时候队列里面有其他人，那么他就会排在后面，否则会直接去拜访。有 q 次询问，操作一为在 t 时刻加入一个拜访时间为 d 的骑士。操作二为删除一个骑士。操作三为询问如果公主 t 时刻来，那么她需要等多长时间才能拜访到国王。
题目分析
这道题很明显是一道数据结构题。
首先考虑，需要知道什么信息，使得 [l, mid] 和 (mid, r] 的区间可以合并并能获取到有用的信息。对题目有直接帮助的显然是区间的结束时间。那么考虑到合并区间的问题，显然还需要记录每个区间的开始时间，还有中间空白的区域。那么如果前面区间等待的时间已经影响到后面的区间，首先会占用后面区间中的空白区域，都占用完了之后，才会推迟最终结束时间。如此一来，可以使用线段树或者平衡树维护即可。
训练赛时队友使用的是线段树，以下代码为赛后重写的平衡树版本。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;
const int maxn = 3e5 + 5;
int n, m, q;
int opt[maxn];
struct ex {
long long st;
long long ed;
long long blank;
int init(long long t, long long d){
st = t;
ed = t + d;
blank = 0;
return 0;
}
};
ex exmerge(ex x, ex y){
ex ret;
if(x.st == 0){
return y;
}
if(y.st == 0){
return x;
}
if(x.ed < y.st){
ret.st = x.st;
ret.ed = y.ed;
ret.blank = x.blank + y.blank + y.st - x.ed;
}else{
ret.st = x.st;
ret.ed = y.ed + max(x.ed - y.st - y.blank, 0ll);
ret.blank = x.blank + y.blank - min(x.ed - y.st, y.blank);
}
return ret;
}
struct node {
long long t;
long long d;
ex x;
int fix;
int c[2];
int init(long long tt, long long dd){
t = tt;
d = dd;
fix = rand();
c[0] = c[1] = 0;
x.init(tt, dd);
return 0;
}
};
node tree[maxn * 2];
int tc = 0;
int root = 0;
int read(){
int x;
scanf("%d", &x);
return x;
}
int merge(int pos){
tree[pos].x.init(tree[pos].t, tree[pos].d);
if(tree[pos].c[0]){
tree[pos].x = exmerge(tree[tree[pos].c[0]].x, tree[pos].x);
}
if(tree[pos].c[1]){
tree[pos].x = exmerge(tree[pos].x, tree[tree[pos].c[1]].x);
}
return 0;
}
int rotate(int &pos, int d){
int c = tree[pos].c[d];
tree[pos].c[d] = tree[c].c[!d];
tree[c].c[!d] = pos;
merge(pos);
merge(c);
pos = c;
return 0;
}
int insert(int &pos, long long t, long long d){
if(!pos){
pos = ++tc;
tree[pos].init(t, d);
}else{
int dr = tree[pos].t < t;
insert(tree[pos].c[dr], t, d);
if(tree[pos].fix < tree[tree[pos].c[dr]].fix){
rotate(pos, dr);
}
merge(pos);
}
return 0;
}
int remove(int &pos, long long t){
if(tree[pos].t != t){
int d = tree[pos].t < t;
remove(tree[pos].c[d], t);
merge(pos);
}else{
if(!tree[pos].c[0]){
pos = tree[pos].c[1];
}else if(!tree[pos].c[1]){
pos = tree[pos].c[0];
}else{
int d = tree[tree[pos].c[0]].fix < tree[tree[pos].c[1]].fix;
rotate(pos, d);
remove(tree[pos].c[!d], t);
merge(pos);
}
}
return 0;
}
ex query(int &pos, long long t){
ex ret;
if(!pos){
ret.init(0, 0);
}else{
ret.init(tree[pos].t, tree[pos].d);
if(tree[pos].t > t){
ret = query(tree[pos].c[0], t);
}else if(tree[pos].t == t){
ret = exmerge(tree[tree[pos].c[0]].x, ret);
}else{
ret = exmerge(exmerge(tree[tree[pos].c[0]].x, ret), query(tree[pos].c[1], t));
}
}
return ret;
}
long long getans(long long t){
ex ret = query(root, t);
return max(ret.ed - t, 0ll);
}
int main(){
int i, j;
char op;
int x, y;
srand(time(0));
q = read();
for(i=1;i<=q;i++){
scanf(" %c", &op);
if(op == '+'){
x = read();
y = read();
opt[i] = x;
insert(root, x, y);
}else if(op == '-'){
x = read();
remove(root, opt[x]);
}else{
x = read();
printf("%lld\n", getans(x));
}
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;
const int maxn = 3e5 + 5;
int n, m, q;
int opt[maxn];
struct ex {
long long st;
long long ed;
long long blank;
int init(long long t, long long d){
st = t;
ed = t + d;
blank = 0;
return 0;
}
};
ex exmerge(ex x, ex y){
ex ret;
if(x.st == 0){
return y;
}
if(y.st == 0){
return x;
}
if(x.ed < y.st){
ret.st = x.st;
ret.ed = y.ed;
ret.blank = x.blank + y.blank + y.st - x.ed;
}else{
ret.st = x.st;
ret.ed = y.ed + max(x.ed - y.st - y.blank, 0ll);
ret.blank = x.blank + y.blank - min(x.ed - y.st, y.blank);
}
return ret;
}
struct node {
long long t;
long long d;
ex x;
int fix;
int c[2];
int init(long long tt, long long dd){
t = tt;
d = dd;
fix = rand();
c[0] = c[1] = 0;
x.init(tt, dd);
return 0;
}
};
node tree[maxn * 2];
int tc = 0;
int root = 0;
int read(){
int x;
scanf("%d", &x);
return x;
}
int merge(int pos){
tree[pos].x.init(tree[pos].t, tree[pos].d);
if(tree[pos].c[0]){
tree[pos].x = exmerge(tree[tree[pos].c[0]].x, tree[pos].x);
}
if(tree[pos].c[1]){
tree[pos].x = exmerge(tree[pos].x, tree[tree[pos].c[1]].x);
}
return 0;
}
int rotate(int &pos, int d){
int c = tree[pos].c[d];
tree[pos].c[d] = tree[c].c[!d];
tree[c].c[!d] = pos;
merge(pos);
merge(c);
pos = c;
return 0;
}
int insert(int &pos, long long t, long long d){
if(!pos){
pos = ++tc;
tree[pos].init(t, d);
}else{
int dr = tree[pos].t < t;
insert(tree[pos].c[dr], t, d);
if(tree[pos].fix < tree[tree[pos].c[dr]].fix){
rotate(pos, dr);
}
merge(pos);
}
return 0;
}
int remove(int &pos, long long t){
if(tree[pos].t != t){
int d = tree[pos].t < t;
remove(tree[pos].c[d], t);
merge(pos);
}else{
if(!tree[pos].c[0]){
pos = tree[pos].c[1];
}else if(!tree[pos].c[1]){
pos = tree[pos].c[0];
}else{
int d = tree[tree[pos].c[0]].fix < tree[tree[pos].c[1]].fix;
rotate(pos, d);
remove(tree[pos].c[!d], t);
merge(pos);
}
}
return 0;
}
ex query(int &pos, long long t){
ex ret;
if(!pos){
ret.init(0, 0);
}else{
ret.init(tree[pos].t, tree[pos].d);
if(tree[pos].t > t){
ret = query(tree[pos].c[0], t);
}else if(tree[pos].t == t){
ret = exmerge(tree[tree[pos].c[0]].x, ret);
}else{
ret = exmerge(exmerge(tree[tree[pos].c[0]].x, ret), query(tree[pos].c[1], t));
}
}
return ret;
}
long long getans(long long t){
ex ret = query(root, t);
return max(ret.ed - t, 0ll);
}
int main(){
int i, j;
char op;
int x, y;
srand(time(0));
q = read();
for(i=1;i<=q;i++){
scanf(" %c", &op);
if(op == '+'){
x = read();
y = read();
opt[i] = x;
insert(root, x, y);
}else if(op == '-'){
x = read();
remove(root, opt[x]);
}else{
x = read();
printf("%lld\n", getans(x));
}
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;
const int maxn = 3e5 + 5;
int n, m, q;
int opt[maxn];
struct ex {
long long st;
long long ed;
long long blank;
int init(long long t, long long d){
st = t;
ed = t + d;
blank = 0;
return 0;
}
};
ex exmerge(ex x, ex y){
ex ret;
if(x.st == 0){
return y;
}
if(y.st == 0){
return x;
}
if(x.ed < y.st){
ret.st = x.st;
ret.ed = y.ed;
ret.blank = x.blank + y.blank + y.st - x.ed;
}else{
ret.st = x.st;
ret.ed = y.ed + max(x.ed - y.st - y.blank, 0ll);
ret.blank = x.blank + y.blank - min(x.ed - y.st, y.blank);
}
return ret;
}
struct node {
long long t;
long long d;
ex x;
int fix;
int c[2];
int init(long long tt, long long dd){
t = tt;
d = dd;
fix = rand();
c[0] = c[1] = 0;
x.init(tt, dd);
return 0;
}
};
node tree[maxn * 2];
int tc = 0;
int root = 0;
int read(){
int x;
scanf("%d", &x);
return x;
}
int merge(int pos){
tree[pos].x.init(tree[pos].t, tree[pos].d);
if(tree[pos].c[0]){
tree[pos].x = exmerge(tree[tree[pos].c[0]].x, tree[pos].x);
}
if(tree[pos].c[1]){
tree[pos].x = exmerge(tree[pos].x, tree[tree[pos].c[1]].x);
}
return 0;
}
int rotate(int &pos, int d){
int c = tree[pos].c[d];
tree[pos].c[d] = tree[c].c[!d];
tree[c].c[!d] = pos;
merge(pos);
merge(c);
pos = c;
return 0;
}
int insert(int &pos, long long t, long long d){
if(!pos){
pos = ++tc;
tree[pos].init(t, d);
}else{
int dr = tree[pos].t < t;
insert(tree[pos].c[dr], t, d);
if(tree[pos].fix < tree[tree[pos].c[dr]].fix){
rotate(pos, dr);
}
merge(pos);
}
return 0;
}
int remove(int &pos, long long t){
if(tree[pos].t != t){
int d = tree[pos].t < t;
remove(tree[pos].c[d], t);
merge(pos);
}else{
if(!tree[pos].c[0]){
pos = tree[pos].c[1];
}else if(!tree[pos].c[1]){
pos = tree[pos].c[0];
}else{
int d = tree[tree[pos].c[0]].fix < tree[tree[pos].c[1]].fix;
rotate(pos, d);
remove(tree[pos].c[!d], t);
merge(pos);
}
}
return 0;
}
ex query(int &pos, long long t){
ex ret;
if(!pos){
ret.init(0, 0);
}else{
ret.init(tree[pos].t, tree[pos].d);
if(tree[pos].t > t){
ret = query(tree[pos].c[0], t);
}else if(tree[pos].t == t){
ret = exmerge(tree[tree[pos].c[0]].x, ret);
}else{
ret = exmerge(exmerge(tree[tree[pos].c[0]].x, ret), query(tree[pos].c[1], t));
}
}
return ret;
}
long long getans(long long t){
ex ret = query(root, t);
return max(ret.ed - t, 0ll);
}
int main(){
int i, j;
char op;
int x, y;
srand(time(0));
q = read();
for(i=1;i<=q;i++){
scanf(" %c", &op);
if(op == '+'){
x = read();
y = read();
opt[i] = x;
insert(root, x, y);
}else if(op == '-'){
x = read();
remove(root, opt[x]);
}else{
x = read();
printf("%lld\n", getans(x));
}
}
return 0;
}