专栏文章

NFLSHC集训Day4

JJoyce_Official
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miot8q74
此快照首次捕获于
2025/12/03 00:46
3 个月前
此快照最后确认于
2025/12/03 00:46
3 个月前
查看原文

安排

早八上课下午答疑，中午睡一下，我又把手表戴上了
今日大纲
  • 学习进阶线段树的应用

进阶线段树的应用

从今天开始就是疯狂的刷题时间了，题目也难了不少，来看看：
P1
这题难想在如何处理前缀，题目中的 L 和 R 我们可以分别用 0 和 1来代替，一个很自然的想法是用线段树维护答案区间的左右端点，但是问题在于直接这么写不仅麻烦还会TLE，有没有什么巧思呢？
先介绍一下代码里的数组：
lans[i]lans[i] ：线段树中第 ii 个节点所维护的区间的左端点；
rans[i]rans[i] ：线段树中第 ii 个节点所维护的区间的右端点；
ans[i]ans[i] ：线段树中第 ii 个节点所维护的区间的最长符合条件的区间长度；
这样可以 O(1)O(1) 完成信息的维护操作；
重点来考虑一下 pushuppushup 的操作，简单来说分成两块考虑：左边和右边可以拼；左边和右边不能拼，先看看我的 pushuppushup ：
CPP
void pushup(int p, int l, int r)
{
	int cur = 0, mid = (l + r) / 2;
	cur = max(ans[p * 2], ans[p * 2 + 1]);
	if(a[mid] != a[mid + 1]) cur = max(cur, rans[p * 2] + lans[p * 2 + 1]);
	ans[p] = cur;
	lans[p] = lans[p * 2];
	if(ans[p * 2] == mid - l + 1 && a[mid] != a[mid + 1]) lans[p] = mid - l + 1 + lans[p * 2 + 1];
	rans[p] = rans[p * 2 + 1];
	if(ans[p * 2 + 1] == r - mid && a[mid] != a[mid + 1]) rans[p] = r - mid + rans[p * 2];
}
其余部分和板子差不多，看看我写的：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int ans[4 * N], lans[4 * N], rans[4 * N];
bool a[N];
void pushup(int p, int l, int r)
{
	int cur = 0, mid = (l + r) / 2;
	cur = max(ans[p * 2], ans[p * 2 + 1]);
	if(a[mid] != a[mid + 1]) cur = max(cur, rans[p * 2] + lans[p * 2 + 1]);
	ans[p] = cur;
	lans[p] = lans[p * 2];
	if(ans[p * 2] == mid - l + 1 && a[mid] != a[mid + 1]) lans[p] = mid - l + 1 + lans[p * 2 + 1];
	rans[p] = rans[p * 2 + 1];
	if(ans[p * 2 + 1] == r - mid && a[mid] != a[mid + 1]) rans[p] = r - mid + rans[p * 2];
}
void build(int p, int l, int r)
{
	if(l == r)
	{
		ans[p] = lans[p] = rans[p] = 1;
		return ;
	}
	int mid = (l + r) / 2;
	build(p * 2, l, mid);
	build(p * 2 + 1, mid + 1, r);
	ans[p] = lans[p] = rans[p] = 1;
}
void upd(int p, int l, int r, int x)
{
	if(l == r) return ;
	int mid = (l + r) / 2;
	if(x <= mid) upd(p * 2, l, mid, x);
	else upd(p * 2 + 1, mid + 1, r, x);
	pushup(p, l, r);
}

int main()
{
	int n, m, x;
	cin >> n >> m;
	build(1, 1, n);
	while(m--)
	{
		cin >> x;
		a[x] = !a[x];
		upd(1, 1, n, x);
		cout << ans[1] <<endl;
	}
	return 0;
}
P2
这题被放在线段树的题单里，我一开始按照线段树的思路想，但我意识到一点：线段树最大的优点是啥？修改啊！但是题目和我写的线段树里怎么一点修改都不用呢？说明很重要的一点：用线段树完成这题太大材小用了！我仔细审视才发现一点，助手小李给个图例：
对啊！你不觉得像倍增吗？为什么不试试用倍增做呢？其中的异或操作顺题模拟就行，看看我写的：
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int f[N][20], a[N];
int d[N][20], q[N];

signed main()
{
	int n, m;
	int u, v;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	int top = 0;
	for(int i = 1; i <= n; i++)
	{
		while(top > 0 && a[q[top]] < a[i])
		{
			d[q[top]][0] = i;
			f[q[top]][0] = a[q[top]] * (i - q[top]);
			top--;	
		}	
		q[++top] = i;
	} 
	while(top)
	{
		d[q[top]][0] = n + 1;
		f[q[top]][0] = a[q[top]] * (n - q[top] + 1);
		top--;
	}
	d[n + 1][0] = n + 1;
	f[n + 1][0] = 0;
	for(int j = 1; j < 19; j++)
	{
		for(int i = 1; i <= n + 1; i++)
		{
			d[i][j] = d[d[i][j - 1]][j - 1];
			f[i][j] = f[i][j - 1] + f[d[i][j - 1]][j - 1];
		} 
	} 
	int ans = 0;
	while(m--)
	{
		cin >> u >> v;
		int l = 1LL + (u ^ ans) % (long long)n, q = 1LL + (v ^ (ans + 1)) % ((long long)n - l + 1), r = l + q - 1;
		int p = l;
		ans = 0;
		for(int i = 18; ~i; i--)
		{
			if (d[p][i]<=r) 
			{
				ans += f[p][i];
				p = d[p][i];
			}
		}
		if(p <= r) ans += a[p] * (r - p + 1);
		cout << ans <<endl;
	}
	return 0;
}
写完我得到了重要的结果，不是所有打了线段树tag的题目都只能拿线段树写，具体问题具体分析
P3
这题真的是变态到一种境界，其变态之处在于要不断地优化自己的代码调整，否则老是会TLE，看看我的血泪史：
  1. 发现过不去，把 define int long long 改掉了
  2. 发现还是过不去，将所有的 *2 换成了位运算形式
  3. 发现还是过不去，使用快速读入
  4. 发现还是过不去，将 cntcnt 数组改为 boolbool 类型，将加运算改为或运算，终于过了
看看我的辛酸代码：
CPP
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 101000;
int n;
struct node
{
	bool cnt0[30], cnt1[30];
}cnt[N << 2];
char s[30];
int get() 
{
	int x = 0;
	char ch = getchar();
	while (!(ch>='0' && ch<='9')) 
	{
		ch = getchar();
	}
	while (ch>='0' && ch<='9') 
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x;
} 
node pushup(node x, node y)
{
	node res;
	for(int i = 0; i < n; i++)
	{
		res.cnt0[i] = x.cnt0[i] | y.cnt0[i];
		res.cnt1[i] = x.cnt1[i] | y.cnt1[i];
	}
	return res;
}
void upd(int p, int l, int r, int x)
{
	if(l == r)
	{
		memset(cnt[p].cnt0, 0, sizeof(cnt[p].cnt0));
		memset(cnt[p].cnt1, 0, sizeof(cnt[p].cnt1));
		for(int i = 0; i < n; i++)
		{
			if(s[i] == '0') cnt[p].cnt0[i] = 1;
			if(s[i] == '1') cnt[p].cnt1[i] = 1;
		}
		return ;
	} 
	int mid = l + r >> 1;
	if(x <= mid) upd(p << 1, l, mid, x);
	else upd(p << 1 | 1, mid + 1, r, x);
	cnt[p] = pushup(cnt[p << 1], cnt[p << 1 | 1]);
}
node qry(int p, int l, int r, int x, int y)
{
	if(l == x && y == r) return cnt[p];
	int mid = l + r >> 1;
	if(y <= mid) return qry(p << 1, l, mid, x, y);
	if(x > mid) return qry(p << 1 | 1, mid + 1, r, x, y);
	return pushup(qry(p << 1, l, mid, x, mid), qry(p << 1 | 1, mid + 1, r, mid + 1, y));
}
int getans(node cur)
{
	int p = 1;
	for(int i = 0; i < n; i++)
	{
		if(cur.cnt0[i] && cur.cnt1[i]) return 0;
		if(cur.cnt0[i] == 0 && cur.cnt1[i] == 0) p = p << 1;
	}
	return p;
} 

int main()
{
	int m, q, op, l, r, x;
	n = get();
	m = get();
	q = get();
	for(int i = 1; i <= m; i++)
	{
		scanf("%s", s);
		upd(1, 1, m, i);
	}
	int ans = 0;
	while(q--)
	{
		op = get();
		if(op == 0)
		{
			l = get();
			r = get();
			ans ^= getans(qry(1, 1, m, l, r));
		}
		else
		{
			x = get();
			scanf("%s", s);
			upd(1, 1, m, x);
		}
	}
	cout << ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...