题目描述
DOS is a new single-player game that Kayzin came up with. At the beginning of the game you will be given n cards in a row, each with the number of value ai.
In each “matching” operation you can choose any two cards (we assume that the subscripts of these two cards are i,j(i
Kayzin will ask you m times. In the k-th query, you need to select four cards from the cards with subscripts Lk to Rk, and “match” these four cards into two pairs (i.e., two matching operations, but the subscripts of the cards selected in the two matching operations must be different from each other. That is, a card can only be matched at most once. e.g., if you select four tickets with subscripts a, b, c, and d, matching a with b and c with d, or matching a with c and b with d are legal, but matching a with b and b with c is not legal), please calculate the maximum value of the sum of the two matching scores.
Note that the queries are independent of each other.
输入描述
The first line contains an integer T(T≤100) . Then T test cases follow. For one case,
The first line contains two integer n (4≤n≤2×105) and m (1≤m≤105) , n denotes the total number of cards , m denotes the number of times Kayzin queries.
The second line contains n integers a1,a2,…,an (1≤ai≤108), denotes the value of each card.
The next m lines contain Kayzin’s queries. The kth line has two numbers, Lk and Rk (1≤Lk≤Rk≤n), the input guarantees that Rk−Lk≥3
It is guaranteed that the sum of n over all test cases doesn’t exceed 2×105 and the sum of m over all test cases doesn’t exceed 2×05.
输出描述
Print m integer for each case, indicating the maximum scores that can be obtained by selecting four cards (two matching pairs)
题意：
给出长度为n的序列，m次询问，每次询问给出l,r表示区间范围，在[l,r]里选择四个数，两两配对，计算两对a i ∗ a i − a j ∗ a j 的最大值
思路：
输入数组的时候就将a i
变为a i ∗ a i方便后续处理
相当于选出四个数来，每个数对答案的贡献可以为正值也可以为负值
但是因为条件限制还有i < j i
区间的最值可以用线段树维护
+ + − − 可以划分为+ ∣ + − − , + + ∣ − − , + + − ∣ −
+ − + −可以划分为+ ∣ − + − , + − ∣ + − , + − + ∣ −
然后三个的为+ − − , + + − , − + − , + − +
其中+ − − 可以划分为+ ∣ − − , + − ∣ −
其他的依次类推
pushup的时候，由左右子树当前值和组合的值的最大值转移
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+7; struct node{ int l,r; //add +; sub - ll aass,asas;//++--,+-+- ll a,s;//+ - ll aa,as,sa,ss;//++,+-,-+,-- ll aas,ass,asa,sas; //++-,+--,+-+,-+- void init(int ll,int rr){ ll=l,rr=r; aass=asas=a=s=aa=as=sa=ss=aas=ass=asa=sas=-1e18; } }tr[maxn*4]; ll n,m,a[maxn]; void push(node &u,node l,node r){ u.aass=max(l.aass,r.aass); u.asas=max(l.asas,r.asas); u.a=max(l.a,r.a); u.s=max(l.s,r.s); u.aa=max(l.aa,r.aa); u.as=max(l.as,r.as); u.sa=max(l.sa,r.sa); u.ss=max(l.ss,r.ss); u.aas=max(l.aas,r.aas); u.ass=max(l.ass,r.ass); u.asa=max(l.asa,r.asa); u.sas=max(l.sas,r.sas); u.aass=max(u.aass,max(l.a+r.ass,max(l.aa+r.ss,l.aas+r.s))); u.asas=max(u.asas,max(l.a+r.sas,max(l.as+r.as,l.asa+r.s))); u.aa=max(u.aa,l.a+r.a); u.as=max(u.as,l.a+r.s); u.sa=max(u.sa,l.s+r.a); u.ss=max(u.ss,l.s+r.s); u.aas=max(u.aas,max(l.a+r.as,l.aa+r.s)); u.ass=max(u.ass,max(l.a+r.ss,l.as+r.s)); u.asa=max(u.asa,max(l.a+r.sa,l.as+r.a)); u.sas=max(u.sas,max(l.s+r.as,l.sa+r.s)); } void pushup(int u){ push(tr[u],tr[u<<1],tr[u<<1|1]); } void build(int u,int l,int r){ tr[u].l=l; tr[u].r=r; tr[u].a=tr[u].aa=tr[u].aas=tr[u].aass=tr[u].as=tr[u].asa=tr[u].asas=tr[u].ass=tr[u].s=tr[u].sa=tr[u].sas=tr[u].ss=-1e18; if(l==r){ tr[u].a=a[l],tr[u].s=-1*a[l]; } else{ int mid=(l+r)/2; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } } node query(int u,int l,int r){ if(l<=tr[u].l&&r>=tr[u].r) return tr[u]; else{ int mid=(tr[u].l+tr[u].r)/2; if(r<=mid) return query(u<<1,l,r); if(l>mid) return query(u<<1|1,l,r); node ans; ans.init(0,0); push(ans,query(u<<1,l,r),query(u<<1|1,l,r)); return ans; } } int main() { int _;scanf("%d",&_); while(_--){ scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); a[i]=a[i]*a[i]; } build(1,1,n); while(m--){ int x,y; scanf("%d%d",&x,&y); node ans=query(1,x,y); printf("%lld\n",max(ans.aass,ans.asas)); } } return 0; }
