wxwoo's blog

评论系统

链接请填写OJ账户(luogu优先),选填
邮箱用于验证和回复通知,必须填写
无法匿名评论
头像请用你的邮箱,到gravatar设置
由于评论系统尚不完善,邮件回复仍在调试,暂时不会发送邮件,该BUG正在修复中

原题目链接

前置知识:不带修区间最大子段和

没做过请先右转GSS1

这题比GSS1多了一个对左右端点的区间限制,GSS1的做法不再适用

这时我们就要分两种情况讨论

情况1:左右端点的区间不相交,即$[x_1,y_1]\cap[x_2,y_2]=\varnothing$

此时$[y_1+1,x_2-1]$为必选区间,我们只能最大化$[x_1,y_1]$的后缀和和$[x_2,y_2]$的前缀和,加上$[y_1+1,x_2-1]$的和即为答案

情况2:左右端点的区间相交
,即$[x_1,y_1]\cap[x_2,y_2]\ne\varnothing$

设最终答案区间左右端点分别为$x_{ans},y_{ans}$

此时答案分4种情况:

  1. $\{y_1,x_2\}\subsetneqq[x_{ans},y_{ans}]$

  2. $\{y_1\}\subsetneqq[x_{ans},y_{ans}]$

  3. $\{x_2\}\subsetneqq[x_{ans},y_{ans}]$

  4. $\{y_1,x_2\}\nsubseteqq[x_{ans},y_{ans}]$

情况1即为刚才讨论的左右端点区间不相交的情况

情况2可以最大化$[x_1,y_1]$的后缀和和$[y_1,y_2]$的前缀和求出

情况3可以最大化$[x_1,x_2]$的后缀和和$[x_2,y_2]$的前缀和求出

情况4即为求$[x_2,y_1]$的最大子段和

答案即为这4种情况中的最大值

不难发现,若情况1为最优,则情况1,2,3相等

所以情况1可以通过情况2或3来求出

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<typename T> inline void read(T &x)
{
char ch=getchar();
T f=1;
x=0;
while(!('0'<=ch&&ch<='9'))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}
x*=f;
}
const int N=50010;
struct sgttree
{
int left,right,sum,ans;
}t[N<<2];
int n,m;
int a[N];
#define ls(p) p<<1
#define rs(p) p<<1|1
inline sgttree pushup(sgttree ls,sgttree rs)
{
sgttree tmp;
tmp.sum=ls.sum+rs.sum;
tmp.left=max(ls.left,ls.sum+rs.left);
tmp.right=max(rs.right,rs.sum+ls.right);
tmp.ans=max(max(ls.ans,rs.ans),ls.right+rs.left);
return tmp;
}
void build(int p,int l,int r)
{
if(l==r)
{
t[p].ans=t[p].sum=t[p].left=t[p].right=a[l];
return;
}
int mid=l+r>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
t[p]=pushup(t[ls(p)],t[rs(p)]);
}
sgttree query(int ql,int qr,int l,int r,int p)
{
if(ql>qr)
return (sgttree){0,0,0,0};
if(ql<=l&&r<=qr)
{
return t[p];
}
int mid=l+r>>1;
if(qr<=mid)
return query(ql,qr,l,mid,ls(p));
if(mid<ql)
return query(ql,qr,mid+1,r,rs(p));
sgttree ls,rs;
if(ql<=mid)
ls=query(ql,qr,l,mid,ls(p));
if(mid<qr)
rs=query(ql,qr,mid+1,r,rs(p));
return pushup(ls,rs);
}
int main()
{
int _;
read(_);
++_;
while(--_)
{
memset(t,0,sizeof(t));
read(n);
for(int i=1;i<=n;++i)
read(a[i]);
build(1,1,n);
read(m);
++m;
int ll,lr,rl,rr;
while(--m)
{
read(ll);
read(lr);
read(rl);
read(rr);
if(lr<rl)
printf("%d\n",query(lr+1,rl-1,1,n,1).sum+query(ll,lr,1,n,1).right+query(rl,rr,1,n,1).left);
else
{
int res=query(rl,lr,1,n,1).ans;
if(ll<rl)
res=max(res,query(ll,rl,1,n,1).right+query(rl,rr,1,n,1).left-a[rl]);
if(rr>lr)
res=max(res,query(ll,lr,1,n,1).right+query(lr,rr,1,n,1).left-a[lr]);
printf("%d\n",res);
}
}
}
return 0;
}

原题目链接

树上链最值查询

做法很多,LCT,树上倍增,树剖都可以

但由于LCT常数过大,树上倍增比树剖常数大,这里使用树链剖分

边权转点权是树剖常用套路,将边权转成深度较大的点的点权,查询时注意避开两点的LCA的权值

由于不带修改,树剖后用ST表维护,时间复杂度$\mathcal{O}(n\log n)$,比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log

在使用hexo博客和material-x等博客主题时,难免会遇到mathjax数学公式渲染失败或者与markdown渲染冲突的问题。

xaoxuu给出了解决方案,只需在_config.yml里加入mathjax: true即可解决,可以解决大量的mathjax公式渲染,但仍有部分复杂的公式渲染出现问题。

我在这里给出一种解决方案。

注:部分资料来自互联网


载入天数...载入时分秒...


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。