社区讨论
全部都是“Too short on line 1“求调
P3850[TJOI2007] 书架参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @misx1rbq
- 此快照首次捕获于
- 2025/12/05 21:44 2 个月前
- 此快照最后确认于
- 2025/12/07 16:20 2 个月前
样例是过了的,以下是我用FHQTreap的代码。
很奇怪的是,无论是用其他算法,还是直接暴力,都是这个结果。用string替换string_view后会RE.
CPP#include <iostream>
#include <random>
#include <string_view>
// #include <string>
#include <utility>
// #define string_view string
using namespace std;
class SegTreap{
private:
using DataType = string_view;
static mt19937 engine;
static uniform_int_distribution<int> dist;
struct Node{
DataType data;
int size,pri;
Node *son[2];
Node(const DataType &x):data(x),size(1),pri(dist(engine)),son{}{}
~Node() = default;
void update(){
int lsi = son[0]?son[0]->size:0;
int rsi = son[1]?son[1]->size:0;
size = lsi + rsi + 1;
}
};
using DoubleNode = pair<Node*,Node*>;
Node *root;
string_view *string_ptr;
void _clear(Node *&_){
if(_->son[0]) _clear(_->son[0]);
if(_->son[1]) _clear(_->son[1]);
delete _;
}
DoubleNode split(Node *cur,int rk){
if(cur == nullptr) return {nullptr,nullptr};
int lsi = cur->son[0]?cur->son[0]->size:0;
if(rk <= lsi){
DoubleNode tmp = split(cur->son[0],rk);
cur->son[0] = tmp.second;
cur->update();
return {tmp.first,cur};
}else{
rk -= lsi + 1;
DoubleNode tmp = split(cur->son[1],rk);
cur->son[1] = tmp.first;
cur->update();
return {cur,tmp.second};
}
}
Node *merge(Node *u,Node *v){
if(u == nullptr || v == nullptr) return u?u:v;
if(u->pri < v->pri){
u->son[1] = merge(u->son[1],v);
u->update();
return u;
}else{
v->son[0] = merge(u,v->son[0]);
v->update();
return v;
}
}
void _mid(Node *cur){
if(cur->son[0]) _mid(cur->son[0]);
*string_ptr = cur->data;
++string_ptr;
if(cur->son[1]) _mid(cur->son[1]);
}
public:
SegTreap():root(nullptr),string_ptr(nullptr){}
~SegTreap(){
if(root == nullptr) return;
_clear(root);
root = nullptr;
}
void insert(const DataType &x,int rk){
Node *res = new Node(x);
DoubleNode tmp = split(root,rk);
tmp.first = merge(tmp.first,res);
root = merge(tmp.first,tmp.second);
}
void bindStr(string_view *s){
string_ptr = s;
}
void assign(){
if(root == nullptr || string_ptr == nullptr) return;
_mid(root);
}
};
mt19937 SegTreap::engine(1);
uniform_int_distribution<int> SegTreap::dist(1,10000000);
void read(char s[]){
int js = 0;
char ch = getchar();
//z is lower
while (ch < 'A' || ch > 'z') ch = getchar();
while (ch >= 'A' && ch <= 'z'){
s[js++] = ch;
ch = getchar();
}
s[js] = '\0';
}
char buffer[110000][12];
int cnt = 0;
string_view shelf[110000];
SegTreap t;
void solve(){
int n,m,q;
t.bindStr(shelf);
scanf("%d",&n);
for (int i = 1;i <= n;++i){
read(buffer[cnt]);
string_view s = buffer[cnt++];
t.insert(s,i);
}
scanf("%d",&m);
while (m--){
int u;
read(buffer[cnt]);
string_view s = buffer[cnt++];
scanf("%d",&u);
t.insert(s,u);
}
t.assign();
scanf("%d",&q);
while (q--){
int u;
scanf("%d",&u);
cout << shelf[u] << '\n';
}
cout << endl;
}
int main(){
solve();
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...