线段树Tag ArchiveSubscribe

传送门

题目意思是依次给n个区间，长度为1或者2，让从里面选一些区间，使得1到m都被覆盖。并且选出区间的编号差要最小。

用双指针求取最短编号差。

难点在于怎么动态确定区间是否被覆盖了。

对于一个点，可能被三种区间覆盖，于是我们对于区间的端点进行分类。用_表示可以被填的方块类型。

“_LR” 代表区间左端点可以填为长度为1或者2的右端点，但右端点不超出。即可能向左超出
“LR_” 代表区间右端点可以填为长度为1或者2的左端点，但左端点不超出。即可能向右超出
“_LR_” 代表左右端点都有可能超出。
“L_R” 代表左右端点都不超出。

然后用线段树维护这四个值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 23;
struct Node{
    int l, r;
    int s, sl, sr, sn, lv, rv;
}tr[maxn * 4];
void pushup(Node &u, Node &l, Node &r)
{
    u.lv = l.lv;
    u.rv = r.rv;
    int mv = l.rv & (1 << 1);
    u.s = (l.s && r.s) || (l.sl && r.sr && mv);
    u.sl = (l.s && r.sl) || (l.sl 

… Read the rest

传送门

题意很简单，就是求矩阵的最大子矩阵。

数据范围是坐标很多，但是点最多有2000个。100组数据。

根据x坐标排序。对y坐标进行离散化。

枚举x坐标作为左边界，再依次加入某些x相同的点，这样就确定了右边界。

用线段树维护y方向的区间连续最大和。

总体来说就是枚举左右边界，用区间连续最大和来“确定”上下边界。

联动ACWING126

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2002;
typedef long long ll;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define max(a, b) (a) > (b) ? (a) : (b)
struct Node{
    ll l, r, lsum, rsum, sum, dat;
}t[maxn * 4];
void build(ll p, ll l, ll r)
{
    t[p].l = l; t[p].r = r;
    if(l == r) {t[p].lsum = 0, t[p].rsum = 0, t[p].sum 

… Read the rest

传送门

这个题目有两种做法

差分约束

设s [ i ]表示前i个里面取数的个数
* s[b] – s[a – 1] = ci
* s[k] – s[k – 1] = 0 (任何k要比k-1取得多)
* s[k] – s[k – 1] <= 1 (任何数只能取一次)

然后建图跑，从第一个点开始跑最长路。
注意最后只能用spfa来跑，因为djistra无法处理反边权的情况。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 233;
int h[maxn], e[maxn], pre[maxn], val[maxn], cnt;
void add(int u, int v, int w)
{
    e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt; 
}
int dis[maxn], vis[maxn];
void dji()
{
    memset(dis, 

… Read the rest

题意

给一段序列，长度小于3e5，给出多次(3e5)区间操作，每次在 [ l , r ] 依次从fib(1)加上斐波那契数列。
斐波那契数列即f[n] = f[n – 1] + f[n – 2]; 前5项为1，1，2，3，5；
比如[1，1，4，5，6]现在要求在[2，4]上增加，[1，1+1，4+1，5+2，6+3]

另外一个操作就是求区间和。
传送门

斐波那契数列的性质

1.fib[n] = fib[n+2]-fib[2]

这个性质由斐波那契数列的差分推出。
1,1,2,3,5,8,13,21…
..,0,1,1,2,3,5..,8..,13…
可以看出，斐波那契数列求差分以后还是一个斐波那契数列，而且每一位向后移动了两个位置。根据差分的性质：差分序列的N位前缀和即原序列的第N个数字。可以通过逆差分得到序列和。
所以如果想求斐波那契数列的和，也可求它的差分的和，反正都是一样的，但由于差分出来的斐波那契数列是往后移动了两位的。所以需要原序列也往后移动两位，即fib(n)=fib(n+2)-fib(2)

2.斐波那契数列的叠加还是斐波那契数列

这个性质很好理解。因为每个斐波纳妾数列都满足同样的齐次线性递推关系。多个斐波那契数列的每一项还是满足。

也可以通过多次差分的规律，看出逆差分即本性质。

3.类斐波那契数列的公式

形如
F(1)=a,F(2)=b,F(n)=F(n-1)+F(n-2)
的数列即类斐波那契数列。
这类数列可以转化为斐波那契数列相关的数列。即
F(n)=a\times fib(n-1)+b\times fib(n-2)
可以通过矩阵证明
\left[\begin{matrix} 1 & 1\end{matrix} \right] \times \left[\begin{matrix} 0 & 1\\ 1 & 1 \end{matrix} \right]^{n} = \left[\begin{matrix} fib_{n-1} & fib_{n}\end{matrix} \right]
初始值的不同相当于左边的矩阵每列有个系数

线段树维护序列

魔改lazy

由于斐波那契数列的性质3和2，可以对lazy标记的传递方式进行魔改。每个区间记录序列前两个，这样既可以推算出区间和，也可以推算出某项的值。

向下传递的时候不是简单的直接传值。需要把对应的F1和F2算出来。因为对于每个小区间而言，它的F1和F2不再是大区间的F1和F2，需要用性质3计算。

比如
【1，8】
【1，4】 【5，8】
【1，2】【3，4】【5，6】【7，8】
【1】【2】【3】【4】【5】【6】【7】【8】
现在更新【2，6】… Read the rest