当前位置：网站首页>2022杭电多校第二场1011 DOS Card（线段树）

2022杭电多校第二场1011 DOS Card（线段树）

2022-08-01 06:40:00 【51CTO】

题目描述
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.

输入描述
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]里选择四个数，两两配对，计算两对的最大值

思路：

输入数组的时候就将变为方便后续处理
相当于选出四个数来，每个数对答案的贡献可以为正值也可以为负值
但是因为条件限制还有，所以只有和两种组合符合题意
区间的最值可以用线段树维护
可以划分为
可以划分为
然后三个的为
其中可以划分为
其他的依次类推
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;
       
}
      
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.