题意：
一个长为\(n\)的序列\(a\)，初始全为零。
\(n\)个操作，第\(i\)个操作形如给\(a_1,\cdots,a_{x_i}\)加上\(y_i\)。
\(m\)次查询，给定\(l,r\)，求对\(a\)执行第\(l\sim r\)个操作后数列\(a\)的全局最大值。
\(1\le n,m\le 5\cdot 10^5,1\le x_i,|y_i|\le n,1\le l\le r\le n\)，时间限制\(\texttt{10s}\)，空间限制\(\texttt{1024MB}\)。
分析：
将所有操作按\(x_i\)排序，那么每个操作有时间戳\(t_i\)，询问变为仅考虑时间戳在\([l,r]\)之间的操作时的最大值。
注意到\(a_i\)仅由排序后一段后缀的操作决定，考虑分块。每\(B\)个操作为一组，那么块前的操作无影响，块后的操作可以用前缀和解决，而块内只有\(B\)种不同的时间戳，离散化后本质不同的询问只有\(B^2\)种，即下文的\(f\)数组。
令\(f_{i,j}\)为仅考虑时间戳排在块内第\([i,j]\)名的操作时的后缀和最大值，如果能预处理出\(f\)数组，那么每块可以做到\(O(1)\)回答每个询问。
枚举\(i\)，扫描\(j\)，用线段树维护单点加、后缀最大值，可以做到\(O(B^2\log B)\)预处理。
但这并未充分利用操作已经按\(x\)排序的性质，考虑分治。
在solve(l,r)的过程中，仅考虑按\(x\)排序的第\([l,r]\)个操作，\(f_{i,j}\)表示考虑在这些操作中时间戳排在第\([i,j]\)名的操作时的后缀和最大值。
合并时对取最大值的后缀起点分类讨论，如果在左边就需要加上右边的贡献，用前缀和处理，如果在右边就不用管。
划重点：\(x_i\)可能相同是一件很烦人的事情，这意味着仅有从特定位置开始的后缀是合法的，将其它位置的初始值设置为
-inf。另外如果前面有合法的后缀开头但\([i,j]\)中没有仍然可以转移，理论上需要特判，只不过访问到该位置刚好是零所以代码中体现不出来。
分治过程中\(T(n)=2T(\frac n2)+\mathcal O(n^2)\)，由主定理\(T(B)=\mathcal O(B^2)\)。
时间复杂度\(\mathcal O(\frac nB(B^2+m))\)，取\(B=\sqrt n\)则时间复杂度为\(\mathcal O((n+m)\sqrt n)\)。
下面是经过丧心病狂卡常后的代码，可以在洛谷上通过，但是可读性几乎没有，所以更推荐去\(\texttt{Loj}\)上看卡常前有注释版本的代码，link。
#include<bits/stdc++.h>
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int B=708,maxn=5e5+5;
const ll inf=1e18;
int d,m,n;
int b[maxn],s[maxn],pl[maxn],pr[maxn];
int y[maxn],rid[maxn];
ll s1[maxn],s2[maxn];
ll f[B+5][B+5],g[B+5][B+5];
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
struct oper
{
int x,y,t;
bool operator<(const oper &c)
{
return x!=c.x?x<c.x:t<c.t;
}
}a[maxn],c[maxn];
struct quer
{
int l,r,id;
ll res;
bool operator<(const quer &c)
{
return l!=c.l?l<c.l:r<c.r;
}
}q[maxn];
int read()
{
int q=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch!='-'?1:-1,ch=getchar();
while(isdigit(ch)) q=10*q+ch-'0',ch=getchar();
return q*f;
}
void write(ll x)
{
if(x<0) return putchar('-'),write(-x);
if(x>=10) write(x/10);
putchar(x%10+'0');
}
void chmax(ll &a,ll b)
{
if(a<b) a=b;
}
void solve(int l,int r)
{
if(l==r) return f[l-d][r-d]=b[l]?a[l].y:-inf,void();
int m=(l+r)>>1;
solve(l,m),solve(m+1,r),s2[m]=0;
for(int j=m+1;j<=r;j++) s2[j]=s2[j-1]+a[j].y;
pl[l-1]=l-1,pr[l-1]=m;
for(int i=l,j=m+1,k=l;i<=m||j<=r;)
{
c[k]=j>r||(i<=m&&a[i].t<a[j].t)?a[i++]:a[j++];
pl[k]=i-1,pr[k]=j-1,k++;
}
for(int k=l;k<=r;k++) a[k]=c[k];
for(int i=l;i<=m;i++) for(int j=i;j<=m;j++) g[i-d][j-d]=f[i-d][j-d];
for(int i=m+1;i<=r;i++) for(int j=i;j<=r;j++) g[i-d][j-d]=f[i-d][j-d];
for(int i=l;i<=r;i++)
for(int j=i;j<=r;j++)
{
int l1=pl[i-1]+1,l2=pl[j],r1=pr[i-1]+1,r2=pr[j];
f[i-d][j-d]=-inf;
if(s[m]-s[l-1]) chmax(f[i-d][j-d],g[l1-d][l2-d]+s2[r2]-s2[r1-1]);
if(s[r]-s[m]) chmax(f[i-d][j-d],g[r1-d][r2-d]);
}
}
void work(int l,int r)
{
d=l-1;
for(int i=l;i<=r;i++) for(int j=i;j<=r;j++) f[i-d][j-d]=-inf;
solve(l,r);
pl[0]=l-1;
for(int i=1;i<=n;i++)
{
pl[i]=pl[i-1]+(pl[i-1]<r&&a[pl[i-1]+1].t<=i);
s1[i]=s1[i-1]+(rid[i]>r?y[i]:0);
}
for(int i=1;i<=m;i++)
{
int ql=pl[q[i].l-1]+1,qr=pl[q[i].r];
if(s[r]-s[l-1]) chmax(q[i].res,f[ql-d][qr-d]+s1[q[i].r]-s1[q[i].l-1]);
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i].x=read(),y[i]=a[i].y=read(),a[i].t=i;
for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i,q[i].res=-inf;
sort(a+1,a+n+1),a[n+1]={n,0,n+1},n++;
for(int i=1;i<=n;i++) rid[a[i].t]=i;
for(int i=1;i<=n;i++) b[i]=a[i].x!=a[i-1].x,s[i]=s[i-1]+b[i];
sort(q+1,q+m+1);
for(int l=1,r=B;l<=n;l+=B,r+=B) work(l,min(r,n));
for(int i=1;i<=m;i++) rid[q[i].id]=q[i].res;
for(int i=1;i<=m;i++) write(rid[i]),putchar('\n');
return 0;
}
总结：
- 如果操作具有可加性，可以将\(\mathcal O(n^2)\)变成\(\mathcal O(\frac nB\cdot B^2)\)从而有效降低复杂度。
- \(\mathcal O(n\sqrt n)\)次
cache miss真的很可怕！