解题报告-SP1716 Can you answer these queries III
题目总结
带修改区间最长连续子序列和
数据范围
N<=50000
解题思路
法一
当然，此题可以参考GSS 1，利用线段树维护前缀最大和，后缀最大和，区间最大和，搞一搞就好；
法二
很骚气的办法，用线段树维护矩阵连乘积；
考虑没有修改、查询全局最大子段和时候的方法；
假如可修改，那么这就是动态DP了
接下来我们重新定义矩阵乘法；
memset(res.m, 0xc0, sizeof (res.m));
for (ri i = 1; i <= sz; i++) {
for (ri k = 1; k <= sz; k++) {
for (ri j = 1; j <= sz; j++)
res.m[i][j] = max(res.m[i][j], m[i][k] + x.m[k][j]);
}
}相比于普通的乘法，我们把对应元素相乘改为相加，统计答案时，把相加改为取最大值；
手玩一下发现这是正确的；
然后用线段树维护一个区间的矩阵乘法；
易错误区
统计答案时选好位置；
不要忘了初始化sz；
代码展示
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<bitset>
#include<deque>
using namespace std;
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
#define int ll
il char gc() {
static const int BS = 1 << 22;
static unsigned char buf[BS], *st, *ed;
if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);
return st == ed ? EOF : *st++;
}
#define gc getchar
template<class T>void in(T &x)
{
x = 0; bool f = 0; char c = gc();
while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}
while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
if (f) x = -x;
}
#undef gc
void out(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) out(x / 10);
putchar(x % 10 + '0');
}
#define N 50010<<2
#define Maxsz 5
struct Mat {
int sz;
int m[Maxsz][Maxsz];
il void clear() {mem0(m);}
Mat () {sz = 0; clear();}
Mat operator*(const Mat &x)const {
Mat res; res.sz = sz;
memset(res.m, 0xc0, sizeof (res.m));
for (ri i = 1; i <= sz; i++) {
for (ri k = 1; k <= sz; k++) {
for (ri j = 1; j <= sz; j++)
res.m[i][j] = max(res.m[i][j], m[i][k] + x.m[k][j]);
}
}
return res;
}
void operator*=(const Mat &x) {
*this = (*this) * x;
}
void print() {
for (ri i = 1; i <= sz; i++) {
for (ri j = 1; j <= sz; j++)
printf("%lld ", m[i][j]);
puts("");
}
}
il int ans() {
return max(m[1][2], m[3][2]);
}
};
#define ls (x<<1)
#define rs (x<<1|1)
#define gm int mid=(l+r)>>1
#define now tre[x]
Mat tre[N];
Mat bs;
int n, m, a[N], rt;
il void up(int x) {
tre[x] = tre[ls] * tre[rs];
}
void build(int x, int l, int r) {
now.sz = 3;
if (l == r) {
bs.m[1][1] = bs.m[1][2] = bs.m[3][1] = bs.m[3][2] = a[l];
memcpy(now.m, bs.m, sizeof (now.m));
//now.print();
return;
}
gm;
build(ls, l, mid);
build(rs, mid + 1, r);
up(x);
//printf("B %lld %lld %lld\n",l,r,now.ans());
}
void update(int x, int l, int r, int &t, int &k) {
if (l == r) {
bs.m[1][1] = bs.m[1][2] = bs.m[3][1] = bs.m[3][2] = k;
memcpy(now.m, bs.m, sizeof (now.m));
return;
}
gm;
if (t <= mid) update(ls, l, mid, t, k);
else update(rs, mid + 1, r, t, k);
up(x);
}
Mat query(int x, int l, int r, int &ql, int &qr) {
if (ql <= l && r <= qr) {
return tre[x];
}
gm;
Mat ret;
if (ql <= mid && mid < qr) ret = query(ls, l, mid, ql, qr) * query(rs, mid + 1, r, ql, qr);
else if (ql <= mid) ret = query(ls, l, mid, ql, qr);
else ret = query(rs, mid + 1, r, ql, qr);
//printf("Q %lld %lld %lld\n",l,r,ret.ans());
return ret;
}
void print() {
for (ri i = 1; i <= n; ++i) {
printf("%lld\n", query(rt, 1, n, i, i).ans());
}
}
signed main() {
bs.m[1][3] = bs.m[2][1] = bs.m[2][3] = -inf;
bs.m[2][2] = bs.m[3][3] = 0;
in(n);
for (ri i = 1; i <= n; ++i) in(a[i]);
build(rt = 1, 1, n);
in(m);
int op, x, y;
while (m--) {
//print();
in(op), in(x), in(y);
if (op == 0) {
update(rt, 1, n, x, y);
}
else {
printf("%lld\n", query(rt, 1, n, x, y).ans());
}
}
return 0;
}