线段树的一些题目

1. \(GSS\) 系列

排在最前面的当然是 毒瘤 有趣的 \(GSS\) 系列

线段树维护最大子段和

2. \(CF240F\) \(TorCoder\)

题目:

给定一个由小写字母组成的长为 \(n\) 的字符串 每次操作将 \([l, r]\) 范围内的字符进行重排 使得重排后的字符串为回文字符串 且字典序最小 如果无法构成回文字符串 则不进行操作 求 \(m\) 次操作后的字符串
\(1 \leq n, m \leq 10^5\)

题解:

对于每一个字母建一棵线段树 维护字符串中这一字母的位置 每一次操作都对 \(26\) 棵线段树同时操作

考虑如何构成回文

要求线段树支持区间求和 求给定区间某一字母的个数 显然 能构成回文串一定最多只有一个字母出现次数为奇数 如果有出现次数为奇数的字母 将这个字母放到中间 其他的字母依次枚举 按照字典序进行插入 所以要求线段树支持单点修改

复杂度 \(O(26n\log n)\)

注意:

线段树返回的时候直接返回结构体类型会 \(TLE\) 所以写成了 \(int\) 类型 也有可能只是我写的丑

代码:

/*
  Time: 5.26
  Worker: Blank_space
  Source: CF240F TorCoder
*/
/*--------------------------------------------*/
#include<cstdio>
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, m, rt, num[27];
char s[B];
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < ‘0‘ || ch > ‘9‘) {if(ch == ‘-‘) f = -1; ch = getchar();}
	while(ch >= ‘0‘ && ch <= ‘9‘) {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/
namespace Seg {
	#define ls(x) x << 1
	#define rs(x) x << 1 | 1
	struct node {
		int l, r, mid, sum, lzy, len;
		node(){l = r = mid = sum = len = 0; lzy = INF;}
	} t[27][B << 2];
	node operator + (node x, node y) {
		node z; z.l = x.l; z.r = y.r;
		z.mid = z.l + z.r >> 1; z.len = z.r - z.l + 1;
		z.sum = x.sum + y.sum;
		return z;
	}
	void build(node *t, int p, int l, int r) {
		t[p].l = l; t[p].r = r; t[p].len = r - l + 1; t[p].mid = l + r >> 1;
		if(l == r) {t[p].sum = (s[l] - 96) == rt; return ;}
		build(t, ls(p), l, t[p].mid); build(t, rs(p), t[p].mid + 1, r);
		t[p] = t[ls(p)] + t[rs(p)];
	}
	void f(node *t, int p, int k) {t[p].sum = k * t[p].len; t[p].lzy = k;}
	void push_down(node *t, int p) {f(t, ls(p), t[p].lzy); f(t, rs(p), t[p].lzy); t[p].lzy = INF;}
	void up_date(node *t, int p, int l, int r, int k) {
		if(l <= t[p].l && t[p].r <= r) {f(t, p, k); return ;}
		if(t[p].lzy != INF) push_down(t, p);
		if(l <= t[p].mid) up_date(t, ls(p), l, r, k);
		if(r > t[p].mid) up_date(t, rs(p), l, r, k);
		t[p] = t[ls(p)] + t[rs(p)];
	}
//	node query(node *t, int p, int l, int r) {
//		if(l <= t[p].l && t[p].r <= r) return t[p];
//		if(t[p].lzy != INF) push_down(t, p);
//		if(l <= t[p].mid) if(r > t[p].mid) return query(t, ls(p), l, r) + query(t, rs(p), l, r);
//		else return query(t, ls(p), l, r); else return query(t, rs(p), l, r);
//	}
	int query(node *t, int p, int l, int r) {
		if(l <= t[p].l && t[p].r <= r) return t[p].sum;
		if(t[p].lzy != INF) push_down(t, p); int res = 0;
		if(l <= t[p].mid) res += query(t, ls(p), l, r);
		if(r > t[p].mid) res += query(t, rs(p), l, r);
		return res;
	}
}
/*----------------------------------------函数*/
int main() {
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);

    n = read(); m = read(); scanf("%s", s + 1);
    for(int i = 1; i <= 26; i++) rt = i, Seg::build(Seg::t[i], 1, 1, n);
    while(m--)
    {
    	int x = read(), y = read(), cnt = 0, id = -1;
    	for(int i = 1; i <= 26; i++) num[i] = Seg::query(Seg::t[i], 1, x, y);
    	for(int i = 1; i <= 26; i++) if(num[i] & 1) cnt++, id = i;
    	if(cnt > 1) continue;
    	for(int i = 1; i <= 26; i++) Seg::up_date(Seg::t[i], 1, x, y, 0);
    	if(cnt) num[id]--, Seg::up_date(Seg::t[id], 1, x + y >> 1, x + y >> 1, 1);
    	int l = x, r = y;
    	for(int i = 1; i <= 26; i++) if(num[i])
    	{
    		Seg::up_date(Seg::t[i], 1, l, l + (num[i] >> 1) - 1, 1); l += num[i] >> 1;
    		Seg::up_date(Seg::t[i], 1, r - (num[i] >> 1) + 1, r, 1); r -= num[i] >> 1;
    	}
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= 26; j++)
		if(Seg::query(Seg::t[j], 1, i, i)) putchar(j + 96);
    
	fclose(stdin);
	fclose(stdout);
	return 0;
}

3. \(CF242E\) \(XOR\) \(on\) \(Segment\)

题目:

\(n\) 个数的序列 \(m\) 次操作
要求支持

1. 区间求和
2. 区间异或
   \(1 \leq n \leq 10 ^ 5\) \(1 \leq m \leq 5 \times 10 ^ 5\) \(1 \leq a_i \leq 10^6\)

题解:

拆位线段树 把序列中每一个数拆成二进制 对于序列中数的大小 可以看出拆 \(20\) 位就够了

每一棵线段树维护序列中数的每一位的情况 异或直接对区间中的数的每一位进行操作 求和的时候正常求和再乘上这一位的进制即可

复杂度 \(O(20n \log n)\)

注意:

空间卡的比较紧 不要 \(define\ int\ long\ long\)

代码:

/*
  Time: 5.28
  Worker: Blank_space
  Source: CF242E XOR on Segment
  区间异或 区间求和 拆位线段树 
*/
/*--------------------------------------------*/
#include<cstdio>
#define ll long long
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, m, a[B], pos;
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < ‘0‘ || ch > ‘9‘) {if(ch == ‘-‘) f = -1; ch = getchar();}
	while(ch >= ‘0‘ && ch <= ‘9‘) {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/
namespace Seg {
	#define ls(x) x << 1
	#define rs(x) x << 1 | 1
	struct node {
		int l, r, mid, len, sum, lzy;
		node() {l = r = mid = len = sum = lzy = 0;}
	} t[21][B << 2];
	node operator + (node x, node y) {
		node z; z.l = x.l; z.r = y.r;
		z.mid = z.l + z.r >> 1; z.len = z.r - z.l + 1;
		z.sum = x.sum + y.sum;
		return z;
	}
	void build(node *t, int p, int l, int r) {
		t[p].l = l; t[p].r = r; t[p].mid = l + r >> 1; t[p].len = r - l + 1;
		if(l == r) {t[p].sum = (a[l] & (1 << pos)) != 0; return ;}
		build(t, ls(p), l, t[p].mid); build(t, rs(p), t[p].mid + 1, r);
		t[p] = t[ls(p)] + t[rs(p)];
	}
	void f(node *t, int p) {t[p].sum = t[p].len - t[p].sum; t[p].lzy ^= 1;}
	void push_down(node *t, int p) {f(t, ls(p)); f(t, rs(p)); t[p].lzy = 0;}
	void up_date(node *t, int p, int l, int r) {
		if(l <= t[p].l && t[p].r <= r) {f(t, p); return ;}
		if(t[p].lzy) push_down(t, p);
		if(l <= t[p].mid) up_date(t, ls(p), l, r);
		if(r > t[p].mid) up_date(t, rs(p), l, r);
		t[p] = t[ls(p)] + t[rs(p)];
	}
	int query(node *t, int p, int l, int r) {
		if(l <= t[p].l && t[p].r <= r) return t[p].sum;
		if(t[p].lzy) push_down(t, p); int res = 0;
		if(l <= t[p].mid)  res += query(t, ls(p), l, r);
		if(r > t[p].mid) res += query(t, rs(p), l, r);
		return res;
	}
}
/*----------------------------------------函数*/
int main() {
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 0; i < 20; i++) pos = i, Seg::build(Seg::t[i], 1, 1, n);
	m = read();
	while(m--)
		if(read() == 1)
		{
			int x = read(), y = read(); ll res = 0;
			for(int i = 0; i < 20; i++) res += 1ll * Seg::query(Seg::t[i], 1, x, y) * (1 << i);
			printf("%lld\n", res);
		}
		else
		{
			int x = read(), y = read(), z = read();
			for(int i = 0; i < 20; i++) if(z & (1 << i)) Seg::up_date(Seg::t[i], 1, x, y);
		}
	return 0;
}

线段树的一些应用

原文：https://www.cnblogs.com/blank-space-/p/14823717.html