题解：P10540 [THUPC 2024 决赛] 古明地枣的袜子

· · 题解

本题解并非正解的分块+分治，学习正解请看其他题解。

双倍经验

P13827 P10540 题目一模一样，后者数据较水。

题意

给定 n 个操作，每次询问求在执行 l\sim r 的操作后全局最大值，操作为将 a_1\sim a_x 加 y，可为负数。

做法

很容易想到 O(n \sqrt n\log n) 的莫队加线段树做法，理论复杂度只可以过这题的，但是由于线段树的超大常数，直接 T 飞了。

原本还想尝试分块代替线段树，可以做到 O(n^{\frac{7}{4}})，但是感觉这题不会这么简单，没有去试，直接去学正解了，结果写完发现有人写莫队过了，于是又想了一下分块，发现普通分块确实不行，但是分块 plus 好像可行。

分块 plus 就是可以做到 O(n^{\frac{1}{3}}) 修改和查询的分块，线段树1的板题写这个比大部分线段树都快，具体可以看这篇文章，这里我简单讲一下。普通分块是直接讲序列分块，但我们其实可以把每一块再次分块（理论上可以一直分下去，但常数会越来越大），每次更新修改所在小块和大块的贡献，查询直接查大块，假设小块块长为 b，大块块长为 B，则这个分块的复杂度为 O(\frac{n}{B}+\frac{B}{b}+b) 取 B=b=n^{\frac{1}{3}} 时复杂度最优。

接下来看这道题，注意到前缀加只会改变 x 所在块的最大值位置，其余只要在这个块上打一个 tag，然后查询时从后往前扫累加上每个块的 tag 即可。

设小块块长为 B，大块块长为 B^2，则复杂度为 O(nB\sqrt n+\frac{n^2}{B^2})，考虑到除法操作较慢， B 取 2 的幂次时可用位运算代替除法操作，综合考虑 B 取 8 最优。但这样任然无法通过，所以直接循环展开，最终代码跑得飞快，优于大部分正解。

但到这里交上去还是会WA，原因是在处理最后面的散块时会统计到 n 以外的数，如果答案小于 0 就会输出 0 。我们将全局的操作单独拎出来，这样若答案小于 0 ，则我们可以取第 n 个数使得答案为 0 ，最后加上全局的操作即可。

这样我们终于用暴力通过了这题，并且因为正解的超大常数，这种方法是优于大部分正解的。

代码

#include<bits/stdc++.h>
#define x first
#define y second
//不要乱开long long
#define ll long long
#define inf 1000000000000000000
#define max(A,B) (A)>(B) ? (A) : (B)
using namespace std;
const int N=5e5+10;
int n,m,pos[N],B=750;
ll w[N],tag1[(N>>3)+10],tag2[(N>>6)+10],mx1[(N>>3)+10],mx2[(N>>6)+10],ans[N],sum[N];
pair <int,int> a[N];
//莫队排序
struct node{
    int l,r,id;
    bool operator < (const node &t) const{
        return pos[l]==pos[t.l] ? ((pos[l]&1) ? r<t.r : r>t.r) : pos[l]<pos[t.l];
    }
}q[N];
//循环展开
#define c(p) tg+=w[p],mx=max(mx,tg)
#define cc(p) mx=max(mx,mx1[p]+tg),tg+=tag1[p]
#define ccc(p) mx=max(mx,mx2[p]+tg),tg+=tag2[p]
void update(int x,int y){
  //下标从0开始，便于分块。
    --x;
    w[x]+=y;
    tag1[x>>3]+=y;
    tag2[x>>6]+=y;
    ll tg=0,mx=-inf;
    int i=(x>>3)<<3;
    c(i+7),c(i+6),c(i+5),c(i+4),c(i+3),c(i+2),c(i+1),c(i);
    mx1[x>>3]=mx;
    tg=0,mx=-inf,i=(x>>6)<<3;
    cc(i+7),cc(i+6),cc(i+5),cc(i+4),cc(i+3),cc(i+2),cc(i+1),cc(i);
    mx2[x>>6]=mx;
}
ll query(){
    ll mx=-inf,tg=0,i=(n-1)>>6;
    for(;i>=7;i-=8) ccc(i),ccc(i-1),ccc(i-2),ccc(i-3),ccc(i-4),ccc(i-5),ccc(i-6),ccc(i-7);
    for(;i>=0;--i) ccc(i);
    return mx;
}
void add(int i){
    update(a[i].x,a[i].y);
}
void del(int i){
    update(a[i].x,-a[i].y);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y,pos[i]=(i-1)/B+1;
        if(a[i].x==n) sum[i]+=a[i].y,a[i].y=0;
        sum[i]+=sum[i-1];
    }
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1);
    int L=1,R=0;
  //莫队板子
    for(int i=1;i<=m;i++){
        while(R<q[i].r) add(++R);
        while(L>q[i].l) add(--L);
        while(R>q[i].r) del(R--);
        while(L<q[i].l) del(L++);
        ans[q[i].id]=max((ll)0,query())+sum[q[i].r]-sum[q[i].l-1];
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}

P13827提交记录 P10540提交记录