杭电多校第二场 DOS Card
评价一下这道题：我写过最爽的线段树题。
这道题真的非常令人身心愉悦，非常厉害的一道线段树入门题。我写这个一次调试都没有，过了样例就交了就过了，一切都是行云流水。
这道题的代码非常好看，也非常好写。
题面：
对序列 \(a\)，回答 \(q\) 次询问：
给定长度至少为 \(4\) 的区间 \([L,R]\)，在区间内选择 \(1\) 对 \((a_i,a_j)(L\leq i<j\leq R)\) 可以获取分数 \((a_i+a_j)(a_i-a_j)\) ，计算选择 \(2\) 对可以获取的最大分数之和。
注意：你选择的 \(2\) 对共 \(4\) 个数中不能有重复的位置
做法：
化为：选 \(2\) 对数，使得前面的数的平方减后面的数的平方之和最大。
\(a\) 直接变成原数的平方。
发现这 \(4\) 个数如果令加为 \(1\)，令减为 \(0\)，则合法的 \(4\) 个数的顺序只有 \(2\) 种：\(1010\) 和 \(1100\)。
然后线段树维护。对于一个区间，维护这两个顺序，需要枚举中间点，左边取左儿子区间的值，右边取右儿子区间的值。
然后也要维护这些更小的值。就先大型分类讨论一波（其实很好想），然后开写。
代码：
点击查看代码
#include <bits/stdc++.h>
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x)
{
bool flag=false;
x=0;register char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
flag=true;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(flag)
x=-x;
}
static char cc[10000];
template<typename item>
inline void print(register item x)
{
if(x==0)
{
cc[0]='0';
putchar(cc[0]);
return;
}
if(x<0)
{
cc[0]='-';
putchar(cc[0]);
x=-x;
}
register long long len=0;
while(x)cc[len++]=x%10+'0',x/=10;
while(len--)putchar(cc[len]);
}
long long max(long long a,long long b)
{
return a>b?a:b;
}
const int MAXN=1e6+50;
struct Tree
{
long long a1,a0,
a11,a00,a10,a01,
a010,a101,a100,a110,
a1010,a1100;
}tr[MAXN];
Tree Merge(Tree x,Tree y)
{
Tree z;
//Len1:
z.a0=max(x.a0,y.a0);
z.a1=max(x.a1,y.a1);
//Len2:
z.a11=max(x.a11,max(x.a1+y.a1,y.a11));
z.a00=max(x.a00,max(x.a0+y.a0,y.a00));
z.a10=max(x.a10,max(x.a1+y.a0,y.a10));
z.a01=max(x.a01,max(x.a0+y.a1,y.a01));
//Len3:
z.a010=max(x.a010,max(x.a01+y.a0,max(x.a0+y.a10,y.a010)));
z.a101=max(x.a101,max(x.a10+y.a1,max(x.a1+y.a01,y.a101)));
z.a100=max(x.a100,max(x.a10+y.a0,max(x.a1+y.a00,y.a100)));
z.a110=max(x.a110,max(x.a11+y.a0,max(x.a1+y.a10,y.a110)));
//Len4:
z.a1010=max(x.a1010,max(x.a101+y.a0,max(x.a10+y.a10,max(x.a1+y.a010,y.a1010))));
z.a1100=max(x.a1100,max(x.a110+y.a0,max(x.a11+y.a00,max(x.a1+y.a100,y.a1100))));
return z;
}
long long a[MAXN];
void Build(int u,int l,int r)
{
if(l==r)
{
tr[u].a0=-a[l];
tr[u].a1=a[l];
tr[u].a00=tr[u].a01=tr[u].a10=tr[u].a11=-1e18;
tr[u].a010=tr[u].a100=tr[u].a101=tr[u].a110=-1e18;
tr[u].a1010=tr[u].a1100=-1e18;
return;
}
int Mid=l+r>>1;
Build(u<<1,l,Mid);
Build(u<<1|1,Mid+1,r);
tr[u]=Merge(tr[u<<1],tr[u<<1|1]);
}
Tree Query(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
return tr[u];
}
int Mid=l+r>>1;
if((x<=Mid)&&(y>=Mid+1))
{
return Merge(Query(u<<1,l,Mid,x,y),Query(u<<1|1,Mid+1,r,x,y));
}
if(x<=Mid)
{
return Query(u<<1,l,Mid,x,y);
}
if(y>=Mid+1)
{
return Query(u<<1|1,Mid+1,r,x,y);
}
}
int N,Q;
int main()
{
int T;
read(T);
while(T--)
{
read(N);
read(Q);
for(int i=1;i<=N;i++)
{
read(a[i]);
a[i]*=a[i];
}
Build(1,1,N);
while(Q--)
{
int l,r;
read(l);
read(r);
Tree ans=Query(1,1,N,l,r);
print(max(ans.a1010,ans.a1100));
putchar('\n');
}
}
fwrite(obuf,p3-obuf,1,stdout);
}
