GSS 系列题解

GSS1

随便猫树或者线段树，就可以过了

猫树不说，线段树可以维护左边最大，右边最大，区间最大，区间值然后就做出来了。

//Isaunoya

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

using namespace std ;

inline int read() { register int x = 0 ; register int f = 1 ; register char c = getchar() ;

	for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;

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

	return x * f ;

} int st[105] ;

template < typename T > inline void write(T x , char c = '\n') { int tp = 0 ;

	if(x == 0) return (void) puts("0") ;

	if(x < 0) putchar('-') , x = -x ;

	for( ; x ; x /= 10) st[++ tp] = x % 10 ;

	for( ; tp ; tp --) putchar(st[tp] + '0') ;

	putchar(c) ;

}

//#define Online_Judge

const int N = 50000 + 10 ;

int n , m ;

int a[N] ;

int p[21][N << 2] , s[21][N << 2] ;

int Log[N << 2] , d[N << 3] ;

inline void build(int l , int r , int rt , int dep) {

	if(l == r) {

		d[l] = rt ;

		return ;

	}

	int mid = l + r >> 1 ;

	int sum = 0 , pre = 0 ;

	p[dep][mid] = s[dep][mid] = sum = pre = a[mid] ;

	if(sum < 0) sum = 0 ;

	for(register int i = mid - 1 ; i >= l ; i --) {

		pre += a[i] ;

		sum += a[i] ;

		p[dep][i] = max(p[dep][i + 1] , sum) ;

		s[dep][i] = max(s[dep][i + 1] , pre) ;

		if(sum < 0) sum = 0 ;

	}

	p[dep][mid + 1] = s[dep][mid + 1] = sum = pre = a[mid + 1] ;

	if(sum < 0) sum = 0 ;

	for(register int i = mid + 2 ; i <= r ; i ++) {

		pre += a[i] ;

		sum += a[i] ;

		p[dep][i] = max(p[dep][i - 1] , sum) ;

		s[dep][i] = max(s[dep][i - 1] , pre) ;

		if(sum < 0) sum = 0 ;

	}

	build(l , mid , rt << 1 , dep + 1) ;

	build(mid + 1 , r , rt << 1 | 1 , dep + 1) ;

}

inline int Query(int l , int r) {

	if(l == r) return a[l] ;

	int st = Log[d[l]] - Log[d[l] ^ d[r]] ;

	return max(max(p[st][l] , p[st][r]) , s[st][l] + s[st][r]) ;

}

signed main() {

#ifdef Online_Judge

	freopen("testdata.in" , "r" , stdin) ;

	freopen("testdata2.out" , "w" , stdout) ;

#endif

	n = read() ;

	for(register int i = 1 ; i <= n ; i ++) a[i] = read() ;

	int len = 2 ;

	for( ; len < n ; len <<= 1) ;

	for(register int i = 2 ; i <= len << 1 ; i ++) Log[i] = Log[i >> 1] + 1 ;

	build(1 , len , 1 , 1) ;

	m = read() ;

	for(register int i = 1 ; i <= m ; i ++) {

		int l = read() , r = read() ;

		write(Query(l , r)) ;

	}

	return 0 ;

}

GSS2

离线，用树状数组的方法加入数字，只不过是要维护历史最值，这题又没了。

#include <bits/stdc++.h>

#define rep(i , x , y) for(register int i = (x) , _## i = (y + 1) ; i < _## i ; i ++)

#define Rep(i , x , y) for(register int i = (x) , _## i = (y - 1) ; i > _## i ; i --)

using namespace std ;

using ll = long long ;

using pii = pair < int , int > ;

const static int _ = 1 << 20 ;

char fin[_] , * p1 = fin , * p2 = fin ;

inline char gc() { return (p1 == p2) && (p2 = (p1 = fin) + fread(fin , 1 , _ , stdin) , p1 == p2) ? EOF : * p1 ++ ; }

inline int read() {

	bool sign = 1 ; char c = 0 ; while(c < 48) ((c = gc()) == 45) && (sign = 0) ;

	int x = (c & 15) ; while((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15) ;

	return sign ? x : -x ;

}

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

	(x == 0) && (putchar(48)) , (x < 0) && (putchar(45) , x = -x) ;

	static char _st[100] ; int _stp = 0 ;

	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) ; }

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

int n , q ;

const int N = 1e5 + 10 ;

int a[N] ;

vector < pii > vr[N] ;

ll ans[N] ;

int mp[N << 1] ;

struct Node {

	ll mx , hsmx , tag , hstag ;

	Node operator + (const Node & other) const {

		Node c ;

		c.mx = max(mx , other.mx) ; c.hsmx = max(hsmx , other.hsmx) ;

		c.tag = c.hstag = 0 ; return c ;

	}

} s[N << 2] ;

inline void pushdown(int rt) {

  s[rt << 1].hsmx = max(s[rt << 1].hsmx , s[rt << 1].mx + s[rt].hstag) ;

  s[rt << 1].hstag = max(s[rt << 1].hstag , s[rt << 1].tag + s[rt].hstag) ;

  s[rt << 1].mx += s[rt].tag ; s[rt << 1].tag += s[rt].tag ;

  s[rt << 1 | 1].hsmx = max(s[rt << 1 | 1].hsmx , s[rt << 1 | 1].mx + s[rt].hstag) ;

  s[rt << 1 | 1].hstag = max(s[rt << 1 | 1].hstag , s[rt << 1 | 1].tag + s[rt].hstag) ;

  s[rt << 1 | 1].mx += s[rt].tag ; s[rt << 1 | 1].tag += s[rt].tag ;

  s[rt].tag = s[rt].hstag = 0 ;

}

void modify(int a , int b , int l , int r , int rt , int val) {

	if(a <= l && r <= b) {

		s[rt].mx += val ; s[rt].tag += val ;

		cmax(s[rt].hsmx , s[rt].mx) ; cmax(s[rt].hstag , s[rt].tag) ;

		return ;

	}

	int mid = l + r >> 1 ; pushdown(rt) ;

	if(a <= mid) modify(a , b , l , mid , rt << 1 , val) ;

	if(b > mid) modify(a , b , mid + 1 , r , rt << 1 | 1 , val) ;

	s[rt] = s[rt << 1] + s[rt << 1 | 1] ;

}

Node query(int a , int b , int l , int r , int rt) {

	if(a <= l && r <= b) return s[rt] ; pushdown(rt) ;

	int mid = l + r >> 1 ;

	if(b <= mid) return query(a , b , l , mid , rt << 1) ;

	if(a > mid) return query(a , b , mid + 1 , r , rt << 1 | 1) ;

	return query(a , b , l , mid , rt << 1) + query(a , b , mid + 1 , r , rt << 1 | 1) ;

}

signed main() {

#ifdef _WIN64

	freopen("testdata.in" , "r" , stdin) ;

#endif

	n = read() ;

	rep(i , 1 , n) a[i] = read() ;

	q = read() ;

	rep(i , 1 , q) {

		int l = read() , r = read() ;

		vr[r].push_back({ l , i }) ;

	}

	rep(i , 1 , n) {

		modify(mp[a[i] + N] + 1 , i , 1 , n , 1 , a[i]) ;

		mp[a[i] + N] = i ;

		for(auto x : vr[i]) ans[x.second] = query(x.first , i , 1 , n , 1).hsmx ;

	}

	rep(i , 1 , q) print(ans[i]) ;

	return 0 ;

}

GSS3

和 GSS1 一个样子，随便写，随便过了…

// Isaunoya

#include<bits/stdc++.h>

using namespace std ;

#define int long long

#define fi first

#define se second

#define pb push_back

inline int read() {

  register int x = 0 , f = 1 ;

  register char c = getchar() ;

  for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;

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

  return x * f ;

}

template < typename T > inline bool cmax(T & x , T y) {

  return x < y ? (x = y) , 1 : 0 ;

}

template < typename T > inline bool cmin(T & x , T y) {

  return x > y ? (x = y) , 1 : 0 ;

}

inline int QP(int x , int y , int Mod){ int ans = 1 ;

  for( ; y ; y >>= 1 , x = (x * x) % Mod)

    if(y & 1) ans = (ans * x) % Mod ;

  return ans ;

}

int n , q ;

struct node {

  int l , r , sum , res ;

} ;

const int N = 5e4 + 5 ;

int a[N] ;

node s[N << 2] ;

inline void pushup(int rt) {

  node l = s[rt << 1] , r = s[rt << 1 | 1] ;

  s[rt].sum = l.sum + r.sum ;

  s[rt].l = max(l.l , l.sum + r.l) ;

  s[rt].r = max(r.r , r.sum + l.r) ;

  s[rt].res = max(l.r + r.l , max(l.res , r.res)) ;

}

inline void build(int l , int r , int rt) {

  if(l == r) { s[rt] = {a[l] , a[l] , a[l] , a[l]} ; return ; }

  int mid = l + r >> 1 ;

  build(l , mid , rt << 1)  ;

  build(mid + 1 , r , rt << 1 | 1) ;

  pushup(rt) ;

}

inline void modify(int x , int l , int r , int rt , int val) {

  if(l == r) {

    s[rt] = {val , val , val , val} ;

    return ;

  }

  int mid = l + r >> 1 ;

  if(x <= mid) modify(x , l , mid , rt << 1 , val) ;

  else modify(x , mid + 1 , r , rt << 1 | 1 , val) ;

  pushup(rt) ;

}

inline node Merge(node x , node y) {

  if(x.l == -19260817 && y.l == -19260817) return {-19260817 , -19260817 , -19260817 , -19260817} ;

  if(x.l == -19260817) return y ;

  if(y.l == -19260817) return x ;

  node res ;

  res.sum = x.sum + y.sum ;

  res.l = max(x.l , x.sum + y.l) ;

  res.r = max(y.r , y.sum + x.r) ;

  res.res = max(x.r + y.l , max(x.res , y.res)) ;

  return res ;

}

inline node query(int a , int b , int l , int r , int rt) {

  if(a <= l && r <= b) return s[rt] ;

  int mid = l + r >> 1 ;

  node res1 , res2 ;

  res1 = {-19260817 , -19260817 , -19260817 , -19260817} ;

  res2 = {-19260817 , -19260817 , -19260817 , -19260817} ;

  if(a <= mid) res1 = query(a , b , l , mid , rt << 1) ;

  if(b > mid) res2 = query(a , b , mid + 1 , r , rt << 1 | 1) ;

  return Merge(res1 , res2) ;

}

signed main() {

  n = read() ;

  for(register int i = 1 ; i <= n ; i ++) a[i] = read() ;

  build(1 , n , 1) ;

  q = read() ;

  while(q --) {

    int opt = read() ;

    if(opt == 1) {

      int x = read() , y = read() ;

      printf("%lld\n" , query(x , y , 1 , n , 1).res) ;

    }

    else {

      int x = read() , y = read() ;

      modify(x , 1 , n , 1 , y) ;

    }

  }

  return 0 ;

}

GSS4

确实水，像是一道分块蓝题…但是线段树也可以做，维护一个区间最值…常用套路？

然后显然是可以做的，这题没了。

#include<bits/stdc++.h>

using namespace std ;

int n , m ;

const static int N = 1e5 + 10 ;

long long a[N] ;

template < typename T > class SegMentTree {

	public :

		T mx[N << 2] , sum[N << 2] ;

		inline T max(T x , T y) {

			return x > y ? x : y ;

		}

		inline void Push_Up(int rt) {

			mx[rt] = max(mx[rt << 1] , mx[rt << 1 | 1]) ;

			sum[rt] = sum[rt << 1] + sum[rt << 1 | 1] ;

		}

		inline void build(int l , int r , int rt) {

			if(l == r) {

				mx[rt] = sum[rt] = a[l] ;

				return ;

			}

			int mid = l + r >> 1 ;

			build(l , mid , rt << 1) ;

			build(mid + 1 , r , rt << 1 | 1) ;

			Push_Up(rt) ;

		}

		inline void Change(int a , int b , int l , int r , int rt) {

			if(mx[rt] == 1) return ;

			if(l == r) {

				mx[rt] = sum[rt] = sqrt(sum[rt]) ;

				return ;

			}

			int mid = l + r >> 1 ;

			if(a <= mid) Change(a , b , l , mid , rt << 1) ;

			if(b > mid) Change(a , b , mid + 1 , r , rt << 1 | 1) ;

			Push_Up(rt) ;

		}

		inline T Query(int a , int b , int l , int r , int rt) {

			if(a <= l && r <= b) return sum[rt] ;

			int mid = l + r >> 1 ;

			T ans = 0 ;

			if(a <= mid) ans += Query(a , b , l , mid , rt << 1) ;

			if(b > mid) ans += Query(a , b , mid + 1 , r , rt << 1 | 1) ;

			return ans ;

		}

} ;

SegMentTree < long long > T ;

signed main() {

	int cnt = 0 ;

	while(scanf("%d" , & n) != EOF) {

		printf("Case #%d:\n", ++ cnt) ;

		for(register int i = 1 ; i <= n ; i ++) scanf("%lld" , & a[i]) ;

		T.build(1 , n , 1) ;

		scanf("%d" , & m) ;

		for( ; m -- ; ) {

			int opt , l , r ;

			scanf("%d %d %d" , & opt , & l , & r) ;

			if(l > r) l ^= r ^= l ^= r ;

			if(opt == 0) T.Change(l , r , 1 , n , 1) ;

			if(opt == 1) printf("%lld\n" , T.Query(l , r , 1 , n , 1)) ;

		}

		puts("") ;

	}

	return 0 ;

}

GSS5

猫树，不想说，就是板子

线段树就分类讨论一下情况，这题没了

// Isaunoya

#include<bits/stdc++.h>

using namespace std ;

using LL = long long ;

using uint = unsigned int ;

#define int long long

#define fir first

#define sec second

#define pb push_back

#define mp(x , y) make_pair(x , y)

template < typename T > inline void read(T & x) { x = 0 ; int f = 1 ; register char c = getchar() ;

  for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;

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

  x *= f ;

}

template < typename T > inline void print(T x) {

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

  static int st[105] ;

  if(x < 0) putchar('-') , x = -x ;

  int tp = 0 ;

  while(x) st[++ tp] = x % 10 , x /= 10 ;

  while(tp) putchar(st[tp --] + '0') ;

}

template < typename T > inline void print(T x , char c) { print(x) ; putchar(c) ; }

template < typename T , typename ...Args > inline void read(T & x , Args & ...args) { read(x) ; read(args...) ; }

template < typename T > inline void sort( vector < T > & v) { sort(v.begin() , v.end()) ; return ; }

template < typename T > inline void unique( vector < T > & v) { sort(v) ; v.erase(unique(v.begin() , v.end()) , v.end()) ; }

template < typename T > inline void cmax(T & x , T y) { if(x < y) x = y ; return ; }

template < typename T > inline void cmin(T & x , T y) { if(x > y) x = y ; return ; }

const int Mod = LLONG_MAX ;

inline int QP(int x , int y) { int ans = 1 ;

  for( ; y ; y >>= 1 , x = (x * x) % Mod)

    if(y & 1) ans = (ans * x) % Mod ;

  return ans ;

}

template < typename T > inline T gcd(T x , T y) { if(y == 0) return x ; return gcd(y , x % y) ; }

template < typename T > inline T lcm(T x , T y) { return x * y / gcd(x , y) ; }

template < typename T > inline void mul(T & x , T y) { x = 1LL * x * y ; if(x >= Mod) x %= Mod ; }

template < typename T > inline void add(T & x , T y) { if((x += y) >= Mod) x -= Mod ; }

template < typename T > inline void sub(T & x , T y) { if((x -= y) < 0) x += Mod ; }

int n , q ;

const int N = 2e5 + 10 ;

int a[N] , pos[N] , p[16][N] , f[16][N] , sum[16][N] , e_sum[16][N] , lg[N << 2] ;

#define rep(i , j , n) for(register int i = j ; i <= n ; i ++)

#define Rep(i , j , n) for(register int i = j ; i >= n ; i --)

inline void build(int l , int r , int k , int d) {

  if(l == r) { pos[l] = k ; return ; }

  int sum1 = 0 , sum2 = 0 , mid = l + r >> 1 ;

  p[d][mid] = f[d][mid] = sum[d][mid] = e_sum[d][mid] = sum1 = sum2 = a[mid] ;

  cmax(sum2 , 0LL) ;

  Rep(i , mid - 1 , l) { sum1 += a[i] , sum2 += a[i] ;

    p[d][i] = max(p[d][i + 1] , sum1) ;

    f[d][i] = max(f[d][i + 1] , sum2) ;

    sum[d][i] = sum1 ;

    e_sum[d][i] = sum2 ;

    cmax(sum2 , 0LL) ;

  }

  p[d][mid + 1] = f[d][mid + 1] = sum[d][mid + 1] = e_sum[d][mid + 1] = sum1 = sum2 = a[mid + 1] ;

  cmax(sum2 , 0LL) ;

  rep(i , mid + 2 , r) { sum1 += a[i] , sum2 += a[i] ;

    p[d][i] = max(p[d][i - 1] , sum1) ;

    f[d][i] = max(f[d][i - 1] , sum2) ;

    sum[d][i] = sum1 ;

    e_sum[d][i] = sum2 ;

    cmax(sum2 , 0LL) ;

  }

  build(l , mid , k << 1 , d + 1) ;

  build(mid + 1 , r , k << 1 | 1 , d + 1) ;

}

inline int s_query(int l , int r) {

  if(l > r) return 0 ;

  if(l == r) return a[l] ;

  int d = lg[pos[l]] - lg[pos[l] ^ pos[r]] ;

  return sum[d][l] + sum[d][r] ;

}

inline int pre_query(int l , int r) {

  if(l > r) return 0 ;

  if(l == r) return a[l] ;

  int d = lg[pos[l]] - lg[pos[l] ^ pos[r]] ;

  return max(e_sum[d][l] , sum[d][l] + p[d][r]) ;

}

inline int suc_query(int l , int r) {

  if(l > r) return 0 ;

  if(l == r) return a[l] ;

  int d = lg[pos[l]] - lg[pos[l] ^ pos[r]] ;

  return max(e_sum[d][r] , sum[d][r] + p[d][l]) ;

}

inline int m_query(int l , int r) {

  if(l > r) return 0 ;

  if(l == r) return a[l] ;

  int d = lg[pos[l]] - lg[pos[l] ^ pos[r]] ;

  return max(max(f[d][l] , f[d][r]) , p[d][l] + p[d][r]) ;

}

inline int query(int l, int r , int l2 , int r2) {

  int ans = 0 ;

  if(r < l2) return s_query(r + 1 , l2 - 1) + suc_query(l , r) + pre_query(l2 , r2) ;

  ans = m_query(l2 , r) ;

  if(l < l2) cmax(ans , suc_query(l , l2) + pre_query(l2 , r2) - a[l2]) ;

  if(r2 > r) cmax(ans , suc_query(l , r) + pre_query(r , r2) - a[r]) ;

  return ans ;

}

signed solve() {

  read(n) ;

  memset(a , 0 , sizeof(a)) ;

  for(register int i = 1 ; i <= n ; i ++) read(a[i]) ;

  read(q) ;

  int len = 2 ; while(len < n) len <<= 1 ;

  build(1 , len , 1 , 1) ;

  while(q -- ) {

    int l , r , l2 , r2 ; read(l , r , l2 , r2) ;

    print(query(l , r , l2 , r2) , '\n') ;

  }

  return 0 ;

}

signed main() {

  for(register int i = 2 ; i <= N ; i ++) lg[i] = lg[i >> 1] + 1 ;

  int t ; read(t) ;

  while(t --) {

    solve() ;

  }

}

GSS6

没有NOI2005的那题难，随便写fhq就能过。

不想写了…代码咕着

事实证明这玩意改改就能过

#include<bits/stdc++.h>

using namespace std ;

const static int _ = 1 << 20 ;

char fin[_] , * p1 = fin , * p2 = fin ;

inline char gc() { return (p1 == p2) && (p2 = (p1 = fin) + fread(fin , 1 , _ , stdin) , p1 == p2) ? EOF : * p1 ++ ; }

inline int read() {

	bool sign = 1 ; char c = 0 ; while(c < 48) ((c = gc()) == 45) && (sign = 0) ;

	int x = (c & 15) ; while((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15) ;

	return sign ? x : -x ;

}

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

	(x == 0) && (putchar(48)) , (x < 0) && (putchar(45) , x = -x) ;

	static char _st[100] ; int _stp = 0 ;

	while(x) _st[++ _stp] = x % 10 ^ 48 , x /= 10 ;

	while(_stp) putchar(_st[_stp --]) ; putchar(c) ;

}

int n , m , rt , cnt = 0 ;

constexpr int N = 2e5 + 10 ;

int a[N] ;

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

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

int max(int x , int y) {

	return x > y ? x : y ;

}

int min(int x , int y ){

	return x < y ? x : y ;

}

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]]) ;

}

int newnode(int k) {

	++ cnt ;

	rnd[cnt] = rand() ;

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

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

	sz[cnt] = 1 ;

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

	return cnt ;

}

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) {

		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) ;

}

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 main() {

#ifdef _WIN64

	freopen("testdata.in" , "r" , stdin) ;

#endif

	srand(19260817) ; n = read() ; rt = newrt(n) ; m = read() ;

	while(m --) {

		char opt = gc() ;	while(opt < 'D' || opt > 'R') opt = gc() ;

		if(opt == 'I') {

			int pos = read() ; pos -- ;

			insert(pos , 1) ;

		}

		if(opt == 'D') {

			int pos = read() ;

			remove(pos , pos) ;

		}

		if(opt == 'R') {

			int pos  = read() ;

			remove(pos , pos) ; pos -- ;

			insert(pos , 1) ;

		}

		if(opt == 'Q') {

			int l = read() , r = read() ;

			print(query_max_sum(l , r)) ;

		}

	}

	return 0 ;

}

GSS7

只需要管一下合并，左链翻转/右链翻转，这题就没了。

虽然说tag初值=0调了好久就是了

#include <bits/stdc++.h>

#define rep(i , x , y) for(register int i = (x) , _## i = (y + 1) ; i < _## i ; i ++)

#define Rep(i , x , y) for(register int i = (x) , _## i = (y - 1) ; i > _## i ; i --)

using namespace std ;

using ll = long long ;

using pii = pair < int , int > ;

const static int _ = 1 << 20 ;

char fin[_] , * p1 = fin , * p2 = fin ;

inline char gc() { return (p1 == p2) && (p2 = (p1 = fin) + fread(fin , 1 , _ , stdin) , p1 == p2) ? EOF : * p1 ++ ; }

inline int read() {

	bool sign = 1 ; char c = 0 ; while(c < 48) ((c = gc()) == 45) && (sign = 0) ;

	int x = (c & 15) ; while((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15) ;

	return sign ? x : -x ;

}

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

	(x == 0) && (putchar(48)) , (x < 0) && (putchar(45) , x = -x) ;

	static char _st[100] ; int _stp = 0 ;

	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) ; }

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

struct Node {

	int mx , lmx , rmx , sum , tag ;

	void operator = (int x) { sum = x ; mx = lmx = rmx = max(0 , sum) ; }

} ;

Node Merge(Node x , Node y) {

	Node res ;

	res.lmx = max(x.lmx , x.sum + y.lmx) ;

	res.rmx = max(y.rmx , y.sum + x.rmx) ;

	res.sum = x.sum + y.sum ;

	res.mx = max(max(x.mx , y.mx) , x.rmx + y.lmx) ;

	res.tag = 1e7 ;

	return res ;

}

int n , q ;

const int N = 1e5 + 10 ;

const int inf = 1e7 ;

Node s[N << 2] ;

vector < int > G[N] ;

int v[N] , a[N] , fa[N] , id[N] , idx = 0 , d[N] , sz[N] , son[N] , top[N] ;

void dfs(int u) {

	sz[u] = 1 ; for(auto v : G[u]) {

		if(v == fa[u]) continue ;

		fa[v] = u ; d[v] = d[u] + 1 ;

		dfs(v) ; sz[u] += sz[v] ;

		if(sz[v] > sz[son[u]]) son[u] = v ;

	}

}

void dfs(int u , int t) {

	top[u] = t ; a[id[u] = ++ idx] = v[u] ;

	if(son[u]) dfs(son[u] , t) ;

	for(auto v : G[u]) {

		if(v == fa[u] || v == son[u]) continue ;

		dfs(v , v) ;

	}

}

void build(int l , int r , int rt) {

	s[rt].tag = inf ;

	if(l == r) { s[rt] = a[l] ; return ; }

	int mid = l + r >> 1 ;

	build(l , mid , rt << 1) ;

	build(mid + 1 , r , rt << 1 | 1) ;

	s[rt] = Merge(s[rt << 1] , s[rt << 1 | 1]) ;

}

void cover(int rt , int l , int r , int val) {

	s[rt] = (r - l + 1) * val ;

	s[rt].tag = val ;

}

void pushdown(int rt , int l , int r) {

	if(s[rt].tag == inf) return ;

	int mid = l + r >> 1 ;

	cover(rt << 1 , l , mid , s[rt].tag) ;

	cover(rt << 1 | 1 , mid + 1 , r , s[rt].tag) ;

	s[rt].tag = inf ;

}

void change(int a , int b , int l , int r , int rt , int val) {

	if(a <= l && r <= b) {

		cover(rt , l , r , val) ;

		return ;

	}

	pushdown(rt , l , r) ;

	int mid = l + r >> 1 ;

	if(a <= mid) change(a , b , l , mid , rt << 1 , val) ;

	if(b > mid) change(a , b , mid + 1 , r , rt << 1 | 1 , val) ;

	s[rt] = Merge(s[rt << 1] , s[rt << 1 | 1]) ;

}

Node query(int a , int b , int l , int r , int rt) {

	if(a <= l && r <= b) return s[rt] ;

	pushdown(rt , l , r) ;

	int mid = l + r >> 1 ;

	Node L = { 0 , 0 , 0 , 0 , 0 } , R = { 0 , 0 , 0 , 0 , 0 } ;

	if(a <= mid) L = query(a , b , l , mid , rt << 1) ;

	if(b > mid) R = query(a , b , mid + 1 , r , rt << 1 | 1) ;

	return Merge(L , R) ;

}

void change(int x , int y , int val) {

	while(top[x] != top[y]) {

		if(d[top[x]] < d[top[y]]) swap(x , y) ;

		change(id[top[x]] , id[x] , 1 , n , 1 , val) ;

		x = fa[top[x]] ;

	}

	if(d[x] > d[y]) swap(x , y) ;

	change(id[x] , id[y] , 1 , n , 1 , val) ;

}

Node query(int x , int y) {

	Node L = { 0 , 0 , 0 , 0 } , R = { 0 , 0 , 0 , 0 } ;

	while(top[x] ^ top[y]) {

		if(d[top[x]] > d[top[y]]) {

			L = Merge(query(id[top[x]] , id[x] , 1 , n , 1) , L) ;

			x = fa[top[x]] ;

		}

		else {

			R = Merge(query(id[top[y]] , id[y] , 1 , n , 1) , R) ;

			y = fa[top[y]] ;

		}

	}

	if(d[x] > d[y]) {

		L = Merge(query(id[y] , id[x] , 1 , n , 1) , L) ;

	}

	else {

		R = Merge(query(id[x] , id[y] , 1 , n , 1) , R) ;

	}

	swap(L.lmx , L.rmx) ;

	return Merge(L , R) ;

}

signed main() {

#ifdef _WIN64

	freopen("testdata.in" , "r" , stdin) ;

	freopen("testdata.out" , "w" , stdout) ;

#endif

	n = read() ;

	rep(i , 1 , n) v[i] = read() ;

	rep(i , 2 , n) {

		int u = read() , v = read();

		G[u].push_back(v) ;

		G[v].push_back(u) ;

	}

	dfs(1) ;

	dfs(1 , 1) ;

	build(1 , n , 1) ;

	q = read() ;

	while(q --) {

		int opt = read() ;

		if(opt == 1) {

			int x = read() , y = read() ;

			print(query(x , y).mx) ;

		}

		else {

			int x = read() , y = read() , val = read() ;

			change(x , y , val) ;

		}

	}

	return 0 ;

}

GSS8

还没写，咕着。

巴特西

GSS 系列题解

最新文章

热门文章