2022 Hangdian multi school field 2 1011 DOS card (line segment tree)

Title Description
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<j). Notice that i is less than j), and you will get a score of (ai+aj)×(ai−aj).

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.

Input description
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.

Output description
Print m integer for each case, indicating the maximum scores that can be obtained by selecting four cards (two matching pairs)

The question ：

Given length is n Sequence ,m Time to ask , Give out... Every time you ask l,r Represents the range of the interval , stay [l,r] Choose four numbers in , Pairing , Calculate two pairs $a_i\ast a_i-a_j\ast a_j,i<j$ The maximum of

Ideas ：

When you enter an array, you will $a_i$ Turn into $a_i\ast a_i$ Convenient for subsequent processing
It is equivalent to selecting four numbers , The contribution of each number to the answer can be positive or negative
But because of the conditions, there are still $i<j$, So only $++--$ and $+-+-$ The two combinations accord with the meaning of the topic
The maximum value of the interval can be maintained by the segment tree
$++--$ Can be divided into $+|+--,++|--,++-|-$
$+-+-$ Can be divided into $+|-+-,+-|+-,+-+|-$
Then the three are $+--,++-,-+-,+-+$
among $+--$ Can be divided into $+|--,+-|-$
And so on
pushup When , Transfer from the current value of the left and right subtrees and the maximum value of the combined value

Code ：

#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;
}

Reference resources