P14636 NOIP2025 T2#

第一步就没想到。

按照性价比大到小排序后，发现取不到最大值的情况是：

选的最后一个 $w=1$ （否则选取的一定是前缀，是最大的）。
此时选的情况应该是：...i222..(已选前缀)j222..(不选)k(选)...(钱花完了)，其中 $w_i=1,w_j=2,w_k=1$ 。
解释一下就是，先一直选，选到只剩 $1$ 块钱了，跳过中间为 $2$ 的连续段，选后面的第一个 $1$ 。
那么有可能不是最大的情况当且仅当： $a_i+a_k<a_j$ ，即可以通过把两个 $w=1$ 性价比最低的糖果换成一个性价比高的 $w=2$ 的糖果。

然后排序 $a$ ，枚举 $i,j$ ，让 $w_i=1,w_j=2$ ，因此要满足 $a_i<a_j<2a_i$ （满足 $i$ 性价比大于 $j$ ）。

原价大于 $a_j$ 的，一定会选（ $j$ 是必选前缀的后面第一个），这样的数有 $n-j$ 个。
原价大于 $a_i$ 小于 $a_j$ 的，只有 $w=1$ 时会被选。
原价大于 $\dfrac{a_j}{2}$ 小于 $a_i$ 的，如果 $w=1$ ，那么 $i,j$ 之间就不全是 $2$ ，所以， $w=2$ 。都不会被选。

那么 $k$ 如何求？我们找到满足 $a_k+a_i<a_j$ 的最大的 $k_m$ ，下面证明满足条件。 $a_{k_m}+a_i<a_j<2a_i \to a_{k_m} < a_i$

所以 $2a_{k_m}<a_{k_m}+a_i<a_j$ ，即 $k_m$ 的性价比比 $j$ 低。

那么，在 $k_m$ 及以前的 $a$ 都可能成为 $k$ ，这时，我们在前 $k_m$ 个中任意定价 $1,2$ 都满足要求，所以方案数是 $2^{k_m}$ 。

在 $k_m$ 到 $i$ 之间都是确定的，方案数为 $1$ 。到此时剩余价钱为 $m-2$ ，此时问题变成：

有 $j-i-1$ 个 zbj1 为 $0/1$ ，还有 $n-j$ 个 zbj2 为 $1/2$ 。满足所有 zbj 的总和为 $m-2$ ，求方案数。

不难想到，把 zbj2 的先扣去 1，变为 $(1+0/1)$ ，此时相当于在 $n-i-1$ 中选出 $m-2-(n-j)$ 个数的方案数。所以方案数为 $\binom{m-n+j-2}{n-i-1}$ 。

然后似乎就做完了。

1
#include <cstdio>
2
#include <algorithm>
3
using namespace std;
4

5
const int MOD = 998244353;
6
int n , m;
7
struct Num {
8
  int a , i;
9
  inline bool operator < (const Num b){ if(a == b.a) return i < b.i; return a < b.a; }
10
}a[5005];
11
int pw[10005] , C[10005][10005];
12

13
inline void init(int N){
14
  pw[0] = 1; for(int i = 1;i <= N;i++) pw[i] = pw[i - 1] * 2LL % MOD;
15
  C[0][0] = 1;
16
  for(int i = 1;i <= N;i++){
17
    C[i][0] = 1;
18
    for(int j = 1;j <= i;j++)
19
      if((C[i][j] = C[i - 1][j] + C[i - 1][j - 1]) >= MOD)
20
        C[i][j] -= MOD;
21
  }
22
}
23

24
int main(void){
25
  int c , T; scanf("%d%d" , &c , &T);
26
  init(10000);
27
  while(T--){
28
    scanf("%d%d" , &n , &m);
29
    for(int i = 1;i <= n;i++) scanf("%d" , &a[i].a) , a[i].i = i;
30
    sort(a + 1 , a + 1 + n);
31
    int ans = 0;
32
    for(int i = 1;i <= n;i++){
33
      int km = 0;
34
      for(int j = i + 1;j <= n;j++){
35
        if(a[j].a >= (a[i].a << 1)) break;
36
        while(km < i && a[km + 1].a + a[i].a < a[j].a) km++;
37
        if(m - n + j < 2 || a[i].a == a[j].a) continue;
38
//        printf("%d %d %lld\n" , i , j , 1LL * pw[km] * C[n - i - 1][m - n + j - 2] % MOD);
39
        if((ans += 1LL * pw[km] * C[n - i - 1][m - n + j - 2] % MOD) >= MOD)
40
          ans -= MOD;
41
      }
42
    }
43
    printf("%d\n" , (pw[n] - ans + MOD) % MOD);
44
  }
45
}

P14638 NOIP2025 T4#

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
#include <queue>
5
#include <vector>
6
using namespace std;
7

8
char buf[1 << 21] , *p1 , *p2;
9
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin) , p1 == p2)? EOF : *p1++)
10
inline long long read(){
11
  long long ret = 0; bool f = 0; char c = GC;
12
  while(c < '0' || c > '9'){
13
    if(c == '-') f = 1;
14
    c = GC;
15
  }
16
  while(c >= '0' && c <= '9'){
17
    ret = ret * 10 + (c ^ 48);
18
    c = GC;
19
  }
20
  return f? -ret : ret;
21
}
22

23
int n , q; long long a[50005];
24

25
long long st[50005][20]; int lg[50005];
26

27
namespace baoli {
28
  void solve(int L , int R){
29
    unsigned long long output = 0;
30
    for(int i = 1;i <= n;i++){
31
      long long ans = -1e16;
32
      for(int l = 1;l <= i;l++) {
33
        int rl = max(i , L + l - 1) , rr = min(n , R + l - 1);
34
        if(rl > rr) continue;
35
        int le = lg[rr - rl + 1];
36
        ans = max(ans , max(st[rl][le] , st[rr - (1 << le) + 1][le]) - a[l - 1]);
37
      }
38
      output ^= (unsigned long long)i * ans;
39
    }
40
    printf("%llu\n" , output);
41
  }
42
}
43

44
namespace A {
45
  deque <pair <long long , int> > qu;
46

47
  long long ans[50005];
48

49
  void solve(int L , long long ans[50005]){
50
    while(!qu.empty()) qu.pop_back();
51
    for(int l = 1;l + L - 1 <= n;l++){
52
      int r = l + L - 1;
53
      while(!qu.empty() && qu.front().second < l) qu.pop_front();
54
      while(!qu.empty() && qu.back().first < a[r] - a[l - 1]) qu.pop_back();
55
      qu.push_back(make_pair(a[r] - a[l - 1] , r));
56
      ans[l] = qu.front().first;
57
      //a[r] - a[l - 1];
58
    }
59
    for(int i = n - L + 2;i <= n;i++){
60
      while(!qu.empty() && qu.front().second < i) qu.pop_front();
61
      ans[i] = qu.front().first;
62
    }
63
  }
64

65
  void print(){
66
    unsigned long long output = 0;
67
    for(int i = 1;i <= n;i++) output ^= (unsigned long long)i * ans[i];
68
    printf("%llu\n" , output);
69
  }
70
}
71

72
namespace B {
73
  long long ans[33][50005];
74
  long long qwq[50005][33][6];
75

76
  void init(){
77
    for(int i = 1;i <= 32;i++) A::solve(i , ans[i]);
78
    for(int i = 1;i <= n;i++) for(int j = 1;j <= 32;j++) qwq[i][j][0] = ans[j][i];
79
    for(int o = 1;o <= n;o++){
80
      for(int k = 1;k <= 5;k++) for(int i = 1;i + (1 << k) <= 33;i++)
81
        qwq[o][i][k] = max(qwq[o][i][k - 1] , qwq[o][i + (1 << (k - 1))][k - 1]);
82
    }
83
  }
84

85
  void solve(int L , int R){
86
    unsigned long long output = 0;
87
    for(int i = 1;i <= n;i++){
88
      int le = lg[R - L + 1];
89
      output ^= (unsigned long long)i * max(qwq[i][L][le] , qwq[i][R - (1 << le) + 1][le]);
90
    }
91
    printf("%llu\n" , output);
92
  }
93
}
94

95
namespace AB {
96
  long long tmp[50005] , ans[50005];
97
  void solve(int L , int R){
98
    for(int j = 1;j <= n;j++) ans[j] = -1e16;
99
    for(int i = L;i <= R;i++){
100
      A::solve(i , tmp);
101
      for(int j = 1;j <= n;j++) ans[j] = max(ans[j] , tmp[j]);
102
    }
103
    unsigned long long output = 0;
104
    for(int i = 1;i <= n;i++) output ^= (unsigned long long)i * ans[i];
105
    printf("%llu\n" , output);
106
  }
107
}
108

109
int main(void){
110
  // freopen("query.in" , "r" , stdin);
111
  // freopen("query.out" , "w" , stdout);
112
  n = read();
113
  for(int i = 1;i <= n;i++) a[i] = read() + a[i - 1];
114
  for(int i = 1;i <= n;i++) st[i][0] = a[i];
115
  for(int i = 2;i <= n;i++) lg[i] = lg[i >> 1] + 1;
116
  for(int k = 1;k <= lg[n];k++) for(int i = 1;i + (1 << k) - 1 <= n;i++)
117
    st[i][k] = max(st[i][k - 1] , st[i + (1 << (k - 1))][k - 1]);
118
  q = read();
119
  B::init();
120
  for(int _ = 1;_ <= q;_++){
121
    int L , R; L = read(); R = read();
122
    if(R <= 32){ B::solve(L , R); continue; }
123
    if(L == R){
124
      A::solve(L , A::ans); A::print();
125
      continue;
126
    }
127
    if(R - L <= 32){ AB::solve(L , R); continue; }
128
    baoli::solve(L , R);
129
  }
130
}

可以发现，如果把区间放到矩形上，查询相当于一个梯形。

对于 $i$ ，实际上是绿色线的移动，移动是 $O(n)$ 级别的。而红线是不变的。

如果 $2L\ge R$ ，可以拆成平行于 $x$ 和平行于 $y$ 的两个平行四边形，直接用两个单调队列算，两个分别按 $l$ ，和 $r$ ，另一维可以用 st 表取区间最大值作为这个点的答案（特殊性质 D）。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
#include <queue>
5
using namespace std;
6
typedef long long ll;
7

8
char buf[1 << 21] , *p1 , *p2;
9
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin) , p1 == p2)? EOF : *p1++)
10
inline int read(){
11
  int ret = 0; char c = GC; bool f = 0;
12
  while(c < '0' || c > '9'){ if(c == '-') f = 1; c = GC; }
13
  while(c >= '0' && c <= '9'){
14
    ret = (ret << 1) + (ret << 3) + (c ^ 48);
15
    c = GC;
16
  }
17
  return f? -ret : ret;
18
}
19

20
int n , a[50005]; ll b[50005] , stmi[50005][20] , stmx[50005][20];
21

22
inline ll st_query(ll st[50005][20] , int l , int r){
23
  l = max(l , 1); r = min(r , n);
24
  if(l > r) return 1145141919810;
25
  int le = __lg(r - l + 1); return max(st[l][le] , st[r - (1 << le) + 1][le]);
26
}
27

28
deque <pair <int , ll> > q;
29
ll ans[50005];
30
inline void solve1(int L , int R){
31
  while(!q.empty()) q.pop_back();
32
  for(int i = 1;i <= n;i++){
33
    while(!q.empty() && q.front().first < i) q.pop_front();
34
    ll x = st_query(stmx , i + L - 1 , i + R - 1);
35
    if(x != 1145141919810){
36
      x -= b[i - 1];
37
      while(!q.empty() && q.back().second < x) q.pop_back();
38
      q.push_back(make_pair(i + L - 1 , x));
39
    }
40
    if(!q.empty()) ans[i] = max(ans[i] , q.front().second);
41
  }
42
}
43

44
inline void solve2(int L , int R){
45
  while(!q.empty()) q.pop_back();
46
  for(int i = n;i >= 1;i--){
47
    while(!q.empty() && q.front().first > i) q.pop_front();
48
    ll x = st_query(stmi , i - R + 1 , i - L + 1);
49
    if(x != 1145141919810){
50
      x += b[i];
51
      while(!q.empty() && q.back().second < x) q.pop_back();
52
      q.push_back(make_pair(i - L + 1 , x));
53
    }
54
    if(!q.empty()) ans[i] = max(ans[i] , q.front().second);
55
  }
56
}
57

58
int main(void){
59
  n = read();
60
  for(int i = 1;i <= n;i++){
61
    a[i] = read();
62
    stmx[i][0] = b[i] = b[i - 1] + a[i];
63
    stmi[i][0] = -b[i - 1];
64
  }
65
  for(int k = 1;k <= __lg(n);k++) for(int i = 1;i + (1 << k) - 1 <= n;i++)
66
    stmx[i][k] = max(stmx[i][k - 1] , stmx[i + (1 << (k - 1))][k - 1]) ,
67
    stmi[i][k] = max(stmi[i][k - 1] , stmi[i + (1 << (k - 1))][k - 1]);
68
  int T = read();
69
  while(T--){
70
    int L , R; L = read(); R = read();
71
    for(int i = 1;i <= n;i++) ans[i] = -1e16;
72
    //[l + L - 1 , L + R - 1]
73

74
    solve1(L , R);
75
    solve2(L , R);
76

77
    // for(int i = 1;i <= n;i++) printf("%lld " , ans[i]); putchar('\n');
78

79
    unsigned long long output = 0;
80
    for(int i = 1;i <= n;i++) output ^= (unsigned long long)i * ans[i];
81
    printf("%llu\n" , output);
82
  }
83
}

对于任意情况，我们可以把询问按照 $[2^i,2^{i+1}-1]$ 拆成 $\log n$ 段，是两散+连续整段，这样每段都满足 $2L\ge R$ ，可以用上面的方法。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
typedef long long ll;
6

7
char buf[1 << 21] , *p1 , *p2;
8
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin) , p1 == p2)? EOF : *p1++)
9
inline int read(){
10
  int ret = 0; char c = GC; bool f = 0;
11
  while(c < '0' || c > '9'){ if(c == '-') f = 1; c = GC; }
12
  while(c >= '0' && c <= '9'){
13
    ret = (ret << 1) + (ret << 3) + (c ^ 48);
14
    c = GC;
15
  }
16
  return f? -ret : ret;
17
}
18

19
int n , a[50005]; ll b[50005] , stmi[50005][20] , stmx[50005][20];
20

21
inline ll st_query(ll st[50005][20] , int l , int r){
22
  l = max(l , 1); r = min(r , n);
23
  if(l > r) return 1145141919810;
24
  int le = __lg(r - l + 1); return max(st[l][le] , st[r - (1 << le) + 1][le]);
25
}
26

27
struct QWQ_Deque{
28
  int st , ed;
29
  pair <int , ll> _q[50005];
30
  inline void clear(){ st = 1; ed = 0; }
31
  inline void push_back(pair <int , ll> x){ _q[++ed] = x; }
32
  inline bool empty(){ return st > ed; }
33
  inline void pop_back(){ ed--; }
34
  inline void pop_front(){ st++; }
35
  inline pair <int , ll> back(){ return _q[ed]; }
36
  inline pair <int , ll> front(){ return _q[st]; }
37
}q;
38

39
ll ans[50005];
40
inline void solve1(int L , int R){
41
  q.clear();
42
  for(int i = 1;i <= n;i++){
43
    while(!q.empty() && q.front().first < i) q.pop_front();
44
    ll x = st_query(stmx , i + L - 1 , i + R - 1);
45
    if(x != 1145141919810){
46
      x -= b[i - 1];
47
      while(!q.empty() && q.back().second < x) q.pop_back();
48
      q.push_back(make_pair(i + L - 1 , x));
49
    }
50
    if(!q.empty()) ans[i] = max(ans[i] , q.front().second);
51
  }
52
}
53

54
inline void solve2(int L , int R){
55
  q.clear();
56
  for(int i = n;i >= 1;i--){
57
    while(!q.empty() && q.front().first > i) q.pop_front();
58
    ll x = st_query(stmi , i - R + 1 , i - L + 1);
59
    if(x != 1145141919810){
60
      x += b[i];
61
      while(!q.empty() && q.back().second < x) q.pop_back();
62
      q.push_back(make_pair(i - L + 1 , x));
63
    }
64
    if(!q.empty()) ans[i] = max(ans[i] , q.front().second);
65
  }
66
}
67

68
int main(void){
69
  n = read();
70
  for(int i = 1;i <= n;i++){
71
    a[i] = read();
72
    stmx[i][0] = b[i] = b[i - 1] + a[i];
73
    stmi[i][0] = -b[i - 1];
74
  }
75
  for(int k = 1 , _ = __lg(n);k <= _;k++) for(int i = 1;i + (1 << k) - 1 <= n;i++)
76
    stmx[i][k] = max(stmx[i][k - 1] , stmx[i + (1 << (k - 1))][k - 1]) ,
77
    stmi[i][k] = max(stmi[i][k - 1] , stmi[i + (1 << (k - 1))][k - 1]);
78
  int T = read();
79
  while(T--){
80
    int L , R; L = read(); R = read();
81
    for(int i = 1;i <= n;i++) ans[i] = -1e16;
82
    //[l + L - 1 , L + R - 1]
83

84
    for(int i = 0 , _ = __lg(R);i <= _;i++){
85
      int l = (1 << i) , r = (1 << (i + 1)) - 1; r = min(r , n);
86
      if(l > R || r < L) continue;
87
      l = max(l , L); r = min(r , R);
88
      solve1(l , r); solve2(l , r);
89
      // if(L <= l && r <= R){
90
      // }
91
      // else{
92

93
      // }
94
    }
95

96
    // for(int i = 1;i <= n;i++) printf("%lld " , ans[i]); putchar('\n');
97

98
    unsigned long long output = 0;
99
    for(int i = 1;i <= n;i++) output ^= (unsigned long long)i * ans[i];
100
    printf("%llu\n" , output);
101
  }
102
}

优化可以散段上面方法暴力做，整段预处理+st 表区间查询，可以做到 $O(nq)$ 。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
typedef long long ll;
6

7
char buf[1 << 23] , *p1 , *p2;
8
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 23 , stdin) , p1 == p2)? EOF : *p1++)
9
inline int read(){
10
  int ret = 0; char c = GC; bool f = 0;
11
  while(c < '0' || c > '9'){ if(c == '-') f = 1; c = GC; }
12
  while(c >= '0' && c <= '9'){
13
    ret = (ret << 1) + (ret << 3) + (c ^ 48);
14
    c = GC;
15
  }
16
  return f? -ret : ret;
17
}
18

19
int n; ll b[50005] , chm[50005][16][5] , stmi[20][50005] , stmx[20][50005];
20

21
inline ll st_query(ll st[20][50005] , int l , int r){
22
  int le = __lg(r - l + 1); return max(st[le][l] , st[le][r - (1 << le) + 1]);
23
};
24

25
int st , ed;
26
pair <int , ll> _q[50005];
27

28
ll ans[50005];
29
inline void solve(int L , int R){
30
  st = 1; ed = 0;
31
  for(int i = 1 , _ = n + 1 - L;i <= n;i++){
32
    while(st <= ed && _q[st].first < i) st++;
33
    if(i <= _){
34
      ll x = st_query(stmx , i + L - 1 , min(i + R - 1 , n)) - b[i - 1];
35
      while(st <= ed && _q[ed].second <= x) ed--;
36
      _q[++ed] = make_pair(i + L - 1 , x);
37
    }
38
    else if(st > ed) break;
39
    ans[i] = max(ans[i] , _q[st].second);
40
  }
41
  st = 1; ed = 0;
42
  for(int i = n;i >= 1;i--){
43
    while(st <= ed && _q[st].first > i) st++;
44
    if(i >= L){
45
      ll x = b[i] + st_query(stmi , max(i - R + 1 , 1) , i - L + 1);
46
      while(st <= ed && _q[ed].second <= x) ed--;
47
      _q[++ed] = make_pair(i - L + 1 , x);
48
    }
49
    else if(st > ed) break;
50
    ans[i] = max(ans[i] , _q[st].second);
51
  }
52
}
53

54
int main(void){
55
  n = read();
56
  for(int i = 1;i <= n;i++) {
57
    stmx[0][i] = b[i] = b[i - 1] + read();
58
    stmi[0][i] = -b[i - 1];
59
  }
60
  for(int k = 1 , _ = __lg(n);k <= _;k++) for(int i = 1;i + (1 << k) - 1 <= n;i++)
61
    stmx[k][i] = max(stmx[k - 1][i] , stmx[k - 1][i + (1 << (k - 1))]) ,
62
    stmi[k][i] = max(stmi[k - 1][i] , stmi[k - 1][i + (1 << (k - 1))]);
63

64

65
  for(int i = 0 , _ = __lg(n);i <= _;i++){
66
    int l = (1 << i) , r = (1 << (i + 1)) - 1; r = min(r , n);
67
    for(int j = 1;j <= n;j++) ans[j] = -1e16;
68
    solve(l , r);
69
    for(int j = 1;j <= n;j++) chm[j][i][0] = ans[j];
70
  }
71

72
  for(int o = 1 , _ = __lg(n);o <= n;o++){
73
    for(int i = 0;i <= _ - 1;i++)
74
      chm[o][i][1] = max(chm[o][i][0] , chm[o][i + 1][0]);
75
    for(int i = 0;i <= _ - 3;i++)
76
      chm[o][i][2] = max(chm[o][i][1] , chm[o][i + 2][1]);
77
    for(int i = 0;i <= _ - 7;i++)
78
      chm[o][i][3] = max(chm[o][i][2] , chm[o][i + 4][2]);
79
    for(int i = 0;i <= _ - 15;i++)
80
      chm[o][i][4] = max(chm[o][i][3] , chm[o][i + 8][3]);
81
  }
82

83
  int T = read() , L , R;
84
  while(T--){
85
    L = read(); R = read();
86
    for(int i = 1;i <= n;i++) ans[i] = -1e16;
87

88
    int fszl = n , fszr = 0;
89
    for(int i = 0 , _ = __lg(R);i <= _;i++){
90
      int l = (1 << i) , r = (1 << (i + 1)) - 1; r = min(r , n);
91
      if(l > R || r < L) continue;
92
      if(L <= l && r <= R)
93
        fszl = min(fszl , i) , fszr = max(fszr , i);
94
      else{
95
        l = max(l , L); r = min(r , R);
96
        solve(l , r);
97
      }
98
    }
99

100
    // printf("%d %d\n" , fszl , fszr);
101
    if(fszl < n) for(int i = 1 , _ = __lg(fszr - fszl + 1) , __ = fszr - (1 << _) + 1;i <= n;i++)
102
      ans[i] = max(ans[i] , max(chm[i][fszl][_] , chm[i][__][_]));
103

104
    // for(int i = 1;i <= n;i++) printf("%lld " , ans[i]); putchar('\n');
105

106
    unsigned long long output = 0;
107
    for(int i = 1;i <= n;i++) output ^= (unsigned long long)i * ans[i];
108
    printf("%llu\n" , output);
109
  }
110
}

卡常：st 表要注意内存的连续访问。

QWQ_SenLin

P14636 NOIP2025 T2#

P14638 NOIP2025 T4#