hihocoder1711 评论框排版[并查集+set]

 #include <cstdio>
#include <iostream>
#include <set>
using namespace std;
const int N = 1e5+; struct Block {
long long begin, all_size; //root起始, root子树总大小
long long dis, size, f; //距离父节点起始距离, 自身大小, 父节点标号
bool operator <(const Block &rhs) const {
return begin < rhs.begin;
}
};
Block block[N]; int findf(int x) {//找到标号x的根节点标号, 并让x直接连向根节点
if(x == block[x].f) return x;
int rt = findf(block[x].f);
int f = block[x].f;
block[x].dis += block[f].dis;
block[x].f = block[f].f;
return rt;
}
void merge(int x, int y) { //将标号y所在的子树merge到标号x所在的子树
int fx = findf(x), fy = findf(y);
if(fx == fy) return ;
block[fy].dis = block[fx].all_size;
block[fy].f = fx;
block[fx].all_size += block[fy].all_size;
} set<Block> se; int main() {
int n, k, h, x, tot = ;
char op;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf(" %c", &op);
if(op == 'I') {
scanf("%d%d", &k, &h);
int ID = ++tot;
block[tot] = {k, h, , h, tot};
if(se.empty()) {se.insert(block[ID]); continue ;} auto it = se.upper_bound(block[ID]);
if(it == se.begin()) {
while(it != se.end() && block[ID].begin+block[ID].all_size >= it->begin) {
int f = it->f;
se.erase(it++);
merge(ID, f);
}
se.insert(block[ID]);
}
else { // it != se.begin()
auto tmp = it;
--tmp;
if(tmp->begin + tmp->all_size >= k) {
int f = tmp->f;
se.erase(tmp);
merge(f, tot);
ID = f;//////////////////////////////////////////
}
while(it != se.end() && block[ID].begin+block[ID].all_size >= it->begin) {
int f = it->f;
se.erase(it++);
merge(ID, f);
}
se.insert(block[ID]);
}
}
else {
scanf("%d", &x);
int rt = findf(x);
long long L = block[x].dis+block[rt].begin;
long long R = L+block[x].size-;
printf("%I64d %I64d\n", L, R);
}
}
return ;
} /*
5
I 1 5
I 8 10
I 5 5
Q 3
Q 2
*/
上一篇:sql的集合操作


下一篇:用python(2.7)自定义实现SQL的集合操作