NFLSHC集训Day4
Joyce_Official
·
·
算法·理论
安排
早八上课下午答疑，中午睡一下，我又把手表戴上了
今日大纲
进阶线段树的应用
从今天开始就是疯狂的刷题时间了，题目也难了不少，来看看：
P1
这题难想在如何处理前缀，题目中的 L 和 R 我们可以分别用 0 和 1来代替，一个很自然的想法是用线段树维护答案区间的左右端点，但是问题在于直接这么写不仅麻烦还会TLE，有没有什么巧思呢？
先介绍一下代码里的数组：
$rans[i]$ ：线段树中第 $i$ 个节点所维护的区间的右端点；
$ans[i]$ ：线段树中第 $i$ 个节点所维护的区间的最长符合条件的区间长度；
这样可以 $ O(1) $ 完成信息的维护操作；
重点来考虑一下 $pushup$ 的操作，简单来说分成两块考虑：左边和右边可以拼；左边和右边不能拼，先看看我的 $pushup$ ：
```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](https://www.luogu.com.cn/problem/P5648)
这题被放在线段树的题单里，我一开始按照线段树的思路想，但我意识到一点：线段树最大的优点是啥？修改啊！但是题目和我写的线段树里怎么一点修改都不用呢？说明很重要的一点：用线段树完成这题太大材小用了！我仔细审视才发现一点，助手小李给个图例：
对啊！你不觉得像倍增吗？为什么不试试用倍增做呢？其中的异或操作顺题模拟就行，看看我写的：
```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](https://www.luogu.com.cn/problem/P5522)
这题真的是变态到一种境界，其变态之处在于要不断地优化自己的代码调整，否则老是会TLE，看看我的血泪史：
1. 发现过不去，把 define int long long 改掉了
2. 发现还是过不去，将所有的 *2 换成了位运算形式
3. 发现还是过不去，使用快速读入
4. 发现还是过不去，将 $cnt$ 数组改为 $bool$ 类型，将加运算改为或运算，终于过了
看看我的辛酸代码：
```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;
}
```