如题，虽然我也不知道为啥$\mathcal O(n\sqrt n)$的分治做法还要卡常，目前在10.1s左右波动/kel

#include<bits/stdc++.h>
#define ll long long
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];
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;
}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');
}
bool cmp(quer a,quer b)
{
    return a.l!=b.l?a.l<b.l:a.r<b.r;
}
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,cmp);
    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;
}