社区讨论

全部都是“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 条回复,欢迎继续交流。

正在加载回复...