本代码需要开 O2。

#include<bits/stdc++.h>
using namespace std;
int n,m,bound,a[100010],b[100010],belong[100010],ans[25010],cnt[100010];
bool mark[25010];
void print(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)printf("%d",x/10);
    putchar(x%10+'0');
}
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct LINE
{
    int l,r,id;
    bool operator<(const LINE &A)const
    {
        return belong[l]==belong[A.l]?r<A.r:l<A.l;
    }
}line[76000];
bitset<100010>F[25010],f;
void update(int pos,bool flag)
{
    int x=a[pos];
    if(flag)
        ++cnt[x],f[x+cnt[x]-2]=1;
    else
        f[x+cnt[x]-2]=0,--cnt[x];
}
void solve(int t)
{
    bound=0;
    memset(mark,0,sizeof(mark));
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=t;i++)
    {
        for(int j=0;j<3;j++)
        {
            line[++bound].l=read(),
            line[bound].r=read(),
            line[bound].id=i;
            ans[i]+=line[bound].r-line[bound].l+1;
        }
    }
    sort(line+1,line+bound+1);
    f.reset();
    memset(cnt,0,sizeof(cnt));
    int L=1,R=0;
    for(int i=1;i<=bound;i++)
    {
        for(;R<line[i].r;update(++R,1));
        for(;L>line[i].l;update(--L,1));
        for(;R>line[i].r;update(R--,0));
        for(;L<line[i].l;update(L++,0));
        if(!mark[line[i].id])
            F[line[i].id]=f,mark[line[i].id]=1;
        else
            F[line[i].id]&=f;
    }
    for(int i=1;i<=t;i++)
    {
        ans[i]-=F[i].count()*3;
        cout<<ans[i]<<'\n';
    }
}
int main()
{
	n=read(),m=read();
    int S=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        b[i]=read(),a[i]=b[i];
        belong[i]=(i-1)/S+1;
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    while(m)
    {
        if(m<=25000)
            solve(m),m=0;
        else
            solve(25000),m-=25000;
    }
    return 0;
}