[NOI2003]文本编辑器 [Fhq Treap]

[NOI2003]文本编辑器
没啥好说的就是个板子
#include <bits/stdc++.h>

// #define int long long

#define rep(a , b , c) for(int a = b ; a <= c ; ++ a)

#define Rep(a , b , c) for(int a = b ; a >= c ; -- a)

#define go(u) for(int i = G.head[u] , v = G.to[i] , w = G.dis[i] ; i ; v = G.to[i = G.nxt[i]] , w = G.dis[i])

using namespace std ;

using ll = long long ;

using pii = pair < int , int > ;

using vi = vector < int > ;

int read() {

  int x = 0 ; bool f = 1 ; char c = getchar() ;

  while(c < 48 || c > 57) { if(c == '-') f = 0 ; c = getchar() ; }

  while(c > 47 && c < 58) { x = (x << 1) + (x << 3) + (c & 15) ; c = getchar() ; }

  return f ? x : -x ;

}

template <class T> void print(T x , char c = '\n') {

  static char st[100] ; int stp = 0 ;

  if(! x) { putchar('0') ; }

  if(x < 0) { x = -x ; putchar('-') ; }

  while(x) { st[++ stp] = x % 10 ^ 48 ; x /= 10 ; }

  while(stp) { putchar(st[stp --]) ; } putchar(c) ;

}

template <class T> void cmax(T & x , T y) { x < y ? x = y : 0 ; }

template <class T> void cmin(T & x , T y) { x > y ? x = y : 0 ; }

const int _N = 1e6 + 10 ;

struct Group {

  int head[_N] , nxt[_N << 1] , to[_N] , dis[_N] , cnt = 1 ;

  Group () { memset(head , 0 , sizeof(head)) ; }

  void add(int u , int v , int w = 1) { nxt[++ cnt] = head[u] ; to[cnt] = v ; dis[cnt] = w ; head[u] = cnt ; }

} ;

const int N = 1e7 + 10  ;

typedef int arr[N] ;

int GB ;

int rt = 0 , cnt = 0 ;

char val[N] ;

int sz[N] , rnd[N] ;

int ch[N][2] ;

#define ls(x) ch[x][0]

#define rs(x) ch[x][1]

int NewNode(char c) {

	val[++ cnt] = c ;

	sz[cnt] = 1 ;

	rnd[cnt] = rand() ;

	return cnt ;

}

void pushup(int x) {

	sz[x] = sz[ls(x)] + sz[rs(x)] + 1 ;

}

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 ;

	}

}

void split(int cur , int k , int & x , int & y) {

	if(! cur) {

		x = y = 0 ;

		return ;

	}

	if(sz[ls(cur)] < k) {

		x = cur ;

		split(rs(x) , k - sz[ls(x)] - 1 , rs(x) , y) ;

		pushup(x) ;

		return ;

	}

	else {

		y = cur ;

		split(ls(y) , k , x , ls(y)) ;

		pushup(y) ;

		return ;

	}

}

void Move(int x) {

	GB = x ;

}

void Insert(int len) {

	int x , y ;

	split(rt , GB , x , y) ;

	int _cnt = 0 ; char c = getchar() ;

	int Newroot = 0 ;

	while(_cnt < len) {

		if(c >= 32 && c <= 126 && c != '\n') ++ _cnt , Newroot = merge(Newroot , NewNode(c)) ;

		c = getchar() ;

	}

	rt = merge(x , merge(Newroot , y)) ;

}

void Delete(int len) {

	int x , y , z ;

	split(rt , GB , x , y) ;

	split(y , len , y , z) ;

	rt = merge(x , z) ;

}

void dfs(int o) {

	if(ls(o)) dfs(ls(o)) ;

	putchar(val[o]) ;

	if(rs(o)) dfs(rs(o)) ;

}

void Get(int len) {

	int x , y , z ;

	split(rt , GB , x , y) ;

	split(y , len , y , z) ;

	dfs(y) ; putchar('\n') ;

	rt = merge(merge(x , y) , z) ;

}

void Prev() {

	-- GB ;

}

void Next() {

	++ GB ;

}

string s ;

signed main() {

	int q = read() ;

	while(q --) {

		cin >> s ;

		if(s == "Move") Move(read()) ;

		if(s == "Insert") Insert(read()) ;

		if(s == "Delete") Delete(read()) ;

		if(s == "Get") Get(read()) ;

		if(s == "Prev") Prev() ;

		if(s == "Next") Next() ;

	}

	return 0 ;

}
巴特西

[NOI2003]文本编辑器 [Fhq Treap]

最新文章

热门文章
