P2710 数列[fhq treap]

调了一辈子的fhq treap…

7个操作…

其中三个查询单点查询其实可以和区间查询写成一个（

fhq treap 的修改操作大概就是 \(split\) 完了然后把修改区间的根打上标记等着下传就完事了…

那这题没了…我给个好一点的小数据…反正我照着这个调了挺久的…

.in

50 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

GET 13

REVERSE 15 1

MAKE-SAME 1 1 3

REVERSE 21 8

GET-SUM 22 3

MAX-SUM 32 2

GET 8

DELETE 4 9

GET 36

REVERSE 34 2

.out

13

78

65

8

45

#include<cstdio>

#include<cstdlib>

#include<string>

#include<iostream>

int min(int x , int y) {

	return x < y ? x : y ;

}

int max(int x , int y) {

	return x > y ? x : y ;

}

void swap(int & x , int & y) {

	x ^= y ^= x ^= y ;

}

int read() {

	int x = 0 , f = 1 ;

	char c = getchar() ;

	while(c < 48 || c > 57) {

		if(c == '-') f = 0 ;

		c = getchar() ;

	}

	while(c >= 48 && c <= 57) {

		x = (x << 1) + (x << 3) + (c & 15) ;

		c = getchar() ;

	}

	return f ? x : -x ;

}

int n , m , rt , cnt ;

constexpr int N = 2e6 + 10 ;

constexpr int lim = 2333 ;

int a[N] ;

int rnd[N] , val[N] , sum[N] , sz[N] , ls[N] , rs[N] ;

int lmax[N] , rmax[N] , mx[N] ;

int tag[N] , rev[N] ;

void pushup(int o) {

	sz[o] = sz[ls[o]] + sz[rs[o]] + 1 ;

	sum[o] = sum[ls[o]] + sum[rs[o]] + val[o] ;

	lmax[o] = max(lmax[ls[o]] , sum[ls[o]] + max(0 , lmax[rs[o]]) + val[o]) ;

	rmax[o] = max(rmax[rs[o]] , sum[rs[o]] + max(0 , rmax[ls[o]]) + val[o]) ;

	mx[o] = max(0 , rmax[ls[o]]) + max(0 , lmax[rs[o]]) + val[o] ;

	if(ls[o]) mx[o] = max(mx[o] , mx[ls[o]]) ;

	if(rs[o]) mx[o] = max(mx[o] , mx[rs[o]]) ;

}

void reverse(int o) {

	swap(ls[o] , rs[o]) ;

	swap(lmax[o] , rmax[o]) ;

	rev[o] ^= 1 ;

}

void cover(int o , int v) {

	val[o] = tag[o] = v ;

	sum[o] = v * sz[o] ;

	lmax[o] = rmax[o] = mx[o] = max(sum[o] , v) ;

}

void pushdown(int o) {

	if(rev[o]) {

		if(ls[o]) reverse(ls[o]) ;

		if(rs[o]) reverse(rs[o]) ;

		rev[o] ^= 1 ;

	}

	if(tag[o] != lim) {

		if(ls[o]) cover(ls[o] , tag[o]) ;

		if(rs[o]) cover(rs[o] , tag[o]) ;

		tag[o] = lim ;

	}

}

int newnode(int k) {

	++ cnt ;

	rnd[cnt] = rand() ;

	val[cnt] = sum[cnt] = k ;

	lmax[cnt] = rmax[cnt] = mx[cnt] = k ;

	sz[cnt] = 1 ;

	tag[cnt] = lim ;

	ls[cnt] = rs[cnt] = 0 ;

	return cnt ;

}

int merge(int x , int y) {

	if(! x || ! y) return x | y ;

	if(rnd[x] < rnd[y]) {

		pushdown(x) ;

		rs[x] = merge(rs[x] , y) ;

		pushup(x) ;

		return x ;

	} else {

		pushdown(y) ;

		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 ;

	}

	pushdown(cur) ;

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

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

		rs[cur] = 0 ;

		pushup(cur) ;

		x = merge(cur , x) ;

	} else {

		split(ls[cur] , k , x , y) ;

		ls[cur] = 0 ;

		pushup(cur) ;

		y = merge(y , cur) ;

	}

}

int newrt(int len) {

	int _newrt = 0 ;

	for(int i = 1 ; i <= len ; i ++) _newrt = merge(_newrt , newnode(read())) ;

	return _newrt ;

}

void insert(int pos , int len) {

	int x , y ;

	split(rt , pos , x , y) ;

	rt = merge(merge(x , newrt(len)) , y) ;

}

void remove(int l , int r) {

	int x , y , z ;

	split(rt , l - 1 , x , z) ;

	split(z , r - l + 1 , y , z) ;

	rt = merge(x , z) ;

}

void rever(int l , int r) {

	int x , y , z ;

	split(rt , l - 1 , x , z) ;

	split(z , r - l + 1 , y , z) ;

	reverse(y) ;

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

}

void cover(int l , int r , int v) {

	int x , y , z ;

	split(rt , l - 1 , x , z) ;

	split(z , r - l + 1 , y , z) ;

	cover(y , v) ;

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

}

int query_sum(int l , int r) {

	int x , y , z ;

	split(rt , l - 1 , x , z) ;

	split(z , r - l + 1 , y , z) ;

	int res = sum[y] ;

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

	return res ;

}

int query_point(int pos) {

	int x , y , z ;

	split(rt , pos , x , z) ;

	split(x , pos - 1 , x , y) ;

	int res = val[y] ;

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

	return res ;

}

int query_max_sum(int l , int r) {

	int x , y , z ;

	split(rt , l - 1 , x , z) ;

	split(z , r - l + 1 , y , z) ;

	int res = mx[y] ;

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

	return res ;

}

int getopt(std :: string opt) {

	if(opt == "INSERT") return 1 ;

	if(opt == "DELETE") return 2 ;

	if(opt == "REVERSE") return 3 ;

	if(opt == "MAKE-SAME") return 4 ;

	if(opt == "GET-SUM") return 5 ;

	if(opt == "GET") return 6 ;

	if(opt == "MAX-SUM") return 7 ;

}

int main() {

	srand(19260817) ;

	n = read() , m = read() ;

	rt = newrt(n) ;

	while(m --) {

		std :: string s ;

		std :: cin >> s ;

		int opt = getopt(s) ;

		if(opt == 1) {

			int pos = read() , len = read() ;

			insert(pos , len) ;

		}

		if(opt == 2) {

			int pos = read() , len = read() ;

			remove(pos , pos + len - 1) ;

		}

		if(opt == 3) {

			int pos = read() , len = read() ;

			rever(pos , pos + len - 1) ;

		}

		if(opt == 4) {

			int pos = read() , len = read() , v = read() ;

			cover(pos , pos + len - 1 , v) ;

		}

		if(opt == 5) {

			int pos = read() , len = read() ;

			printf("%d\n" , query_sum(pos , pos + len - 1)) ;

		}

		if(opt == 6) printf("%d\n" , query_point(read())) ;

		if(opt == 7) {

			int pos = read() , len = read() ;

			printf("%d\n" , query_max_sum(pos , pos + len - 1)) ;

		}

	}

	return 0 ;

}

巴特西

P2710 数列[fhq treap]

最新文章

热门文章