「求问：三种输入区别及前两种错误」

求问：三种输入区别及前两种错误

板块P4008 [NOI2003] 文本编辑器
楼主LuoFeng_Nanami
当前回复2
已保存回复2
发布时间2023/12/19 22:32
上次更新2023/12/20 14:09:19

被骇客银狼阻止的越权访问保存失败

求问：三种输入区别及前两种错误

LuoFeng_Nanami楼主2023/12/19 22:32

$80$ pts cin ver. :

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
#define int ll

using namespace std;

const int inf = 0x3f3f3f3f,mod = 1e9 + 7; 
const int maxn = 2e6 + 7;

namespace FHQTreap{
	int pos, root, tot, siz[maxn], rnd[maxn], ls[maxn], rs[maxn];
	char val[maxn];
	
	inline void PushUp(int p){
		siz[p] = siz[ls[p]] + 1 + siz[rs[p]];
	}
	
	inline int New(char v){
		int x = ++tot;
		val[x] = v, siz[x] = 1, rnd[x] = rand();
		return x;
	}
	
	inline void Split(int p, int v, int &x, int &y){
		if(!p){
			x = y = 0;
			return;
		}
		if(v <= siz[ls[p]]) y = p, Split(ls[p], v, x, ls[y]);
		else x = p, Split(rs[p], v - siz[ls[p]] - 1, rs[x], y);
		PushUp(p);
	}
	
	inline int Merge(int x, int y) {
		if(!x || !y) return x | y;
		if(rnd[x] > rnd[y]) {
			rs[x] = Merge(rs[x], y),
			PushUp(x);
			return x;
		} else {
			ls[y] = Merge(x, ls[y]),
			PushUp(y);
			return y;
		}
	}
	
	inline void Print(int p){
		if(!p) return;
		Print(ls[p]), cout << val[p], Print(rs[p]);
	}
}

using namespace FHQTreap;

string op;
int _;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> _;
	while(_--){
		cin >> op;
		if(op == "Move") cin >> pos;
		else if(op == "Insert"){
			int x, z, n;
			cin >> n;
			Split(root, pos, x, z);
			F(i, 1, n){
				char ch;
				cin >> ch;
				while(ch < 32 || ch > 126) cin >> ch;
				x = Merge(x, New(ch));
			}
			root = Merge(x, z);
		} else if(op == "Delete") {
			int x, y, z, n;
			cin >> n;
			Split(root, pos + n, x, z), Split(x, pos, x, y);
			root = Merge(x, z);
		} else if(op == "Get") {
			int x, y, z, n;
			cin >> n;
			Split(root, pos + n, x, z), Split(x, pos, x, y);
			Print(y);
			cout << '\n';
			root = Merge(Merge(x, y), z);
		} else if(op == "Prev") pos--;
		else pos++;
	}
	
	return 0;
}

$0$ pts FASTEST IO ver. :

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
#define int ll

using namespace std;

const int inf = 0x3f3f3f3f,mod = 1e9 + 7; 
const int maxn = 2e6 + 7;

namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline ll read(){
		reg char ch=gh();
		reg ll x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void writ(ll x)
	{
		if(x < 0){
			putchar('-');
			x = -x;
		}
		if(x > 9) 
			writ(x / 10);
		putchar(x % 10 + '0');
	}
	inline void write(ll x,char c)
	{
		writ(x);
		putchar(c);
	}
}
using namespace IO;

namespace FHQTreap{
	int pos, root, tot, siz[maxn], rnd[maxn], ls[maxn], rs[maxn];
	char val[maxn];
	
	inline void PushUp(int p){
		siz[p] = siz[ls[p]] + 1 + siz[rs[p]];
	}
	
	inline int New(char v){
		int x = ++tot;
		val[x] = v, siz[x] = 1, rnd[x] = rand();
		return x;
	}
	
	inline void Split(int p, int v, int &x, int &y){
		if(!p){
			x = y = 0;
			return;
		}
		if(v <= siz[ls[p]]) y = p, Split(ls[p], v, x, ls[y]);
		else x = p, Split(rs[p], v - siz[ls[p]] - 1, rs[x], y);
		PushUp(p);
	}
	
	inline int Merge(int x, int y) {
		if(!x || !y) return x | y;
		if(rnd[x] > rnd[y]) {
			rs[x] = Merge(rs[x], y),
			PushUp(x);
			return x;
		} else {
			ls[y] = Merge(x, ls[y]),
			PushUp(y);
			return y;
		}
	}
	
	inline void Print(int p){
		if(!p) return;
		Print(ls[p]), putchar(val[p]), Print(rs[p]);
	}
}

using namespace FHQTreap;

string op;
int _;

signed main(){
	
	_ = read();
	while(_--){
		cin >> op;
		if(op == "Move") pos = read();
		else if(op == "Insert"){
			int x, z, n;
			n = read();
			Split(root, pos, x, z);
			F(i, 1, n){
				char ch = getchar();
				while(ch < 32 || ch > 126) ch = getchar();
				x = Merge(x, New(ch));
			}
			root = Merge(x, z);
		} else if(op == "Delete") {
			int x, y, z, n;
			n = read();
			Split(root, pos + n, x, z), Split(x, pos, x, y);
			root = Merge(x, z);
		} else if(op == "Get") {
			int x, y, z, n;
			n = read();
			Split(root, pos + n, x, z), Split(x, pos, x, y);
			Print(y);
			putchar('\n');
			root = Merge(Merge(x, y), z);
		} else if(op == "Prev") pos--;
		else pos++;
	}
	
	return 0;
}

$100$ pts ACCEPTED ver. : (thanks Alex_Wei)

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
#define int ll

using namespace std;

const int inf = 0x3f3f3f3f,mod = 1e9 + 7; 
const int maxn = 2e6 + 7;

#define gc getchar()

inline int read(){
	int x=0,sgn=0; char s=gc;
	while(!isdigit(s))sgn|=s=='-',s=gc;
	while(isdigit(s))x=x*10+s-'0',s=gc;
	return sgn?-x:x;
}

namespace FHQTreap{
	int pos, root, tot, siz[maxn], rnd[maxn], ls[maxn], rs[maxn];
	char val[maxn];
	
	inline void PushUp(int p){
		siz[p] = siz[ls[p]] + 1 + siz[rs[p]];
	}
	
	inline int New(char v){
		int x = ++tot;
		val[x] = v, siz[x] = 1, rnd[x] = rand();
		return x;
	}
	
	inline void Split(int p, int v, int &x, int &y){
		if(!p){
			x = y = 0;
			return;
		}
		if(v <= siz[ls[p]]) y = p, Split(ls[p], v, x, ls[y]);
		else x = p, Split(rs[p], v - siz[ls[p]] - 1, rs[x], y);
		PushUp(p);
	}
	
	inline int Merge(int x, int y) {
		if(!x || !y) return x | y;
		if(rnd[x] > rnd[y]) {
			rs[x] = Merge(rs[x], y),
			PushUp(x);
			return x;
		} else {
			ls[y] = Merge(x, ls[y]),
			PushUp(y);
			return y;
		}
	}
	
	inline void Print(int p){
		if(!p) return;
		Print(ls[p]), putchar(val[p]), Print(rs[p]);
	}
}

using namespace FHQTreap;

string op;
int _;

signed main(){
	
	_ = read();
	while(_--){
		cin >> op;
		if(op == "Move") pos = read();
		else if(op == "Insert"){
			int x, z, n;
			n = read();
			Split(root, pos, x, z);
			F(i, 1, n){
				char ch = getchar();
				while(ch < 32 || ch > 126) ch = getchar();
				x = Merge(x, New(ch));
			}
			root = Merge(x, z);
		} else if(op == "Delete") {
			int x, y, z, n;
			n = read();
			Split(root, pos + n, x, z), Split(x, pos, x, y);
			root = Merge(x, z);
		} else if(op == "Get") {
			int x, y, z, n;
			n = read();
			Split(root, pos + n, x, z), Split(x, pos, x, y);
			Print(y);
			putchar('\n');
			root = Merge(Merge(x, y), z);
		} else if(op == "Prev") pos--;
		else pos++;
	}
	
	return 0;
}

2023/12/19 22:32