Mo's algorithm

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+10;
const int rt=100;
const int B=110;

struct Query
{
    int l, r, idx;
    Query(): l(), r(), idx() {}
    Query(int L, int R, int I): l(L), r(R), idx(I) {}
} q[N];

int st[B], en[B], in[N], k;
int n, m, a[N], sol[N];
int l, r;

void init ()
{
    for (int i=1;i<=n;i+=rt)
    {
        st[++k]=i;
        for (int j=0;j<rt;j++)
        {
            if (i+j<=n) in[i+j]=k;
            else break;
        }
        en[k]=min(n, i+rt-1);
    }
}

inline bool cmp (Query a, Query b)
{
    if (in[a.l]==in[b.l]) return a.r<b.r;
    return in[a.l]<in[b.l];
}

inline void processQuery (int x)
{
    int ret=sol[q[x-1].idx];
    if (q[x].l<l) for (int i=q[x].l;i<l;i++) ret+=a[i];
    if (q[x].l>l) for (int i=l;i<q[x].l;i++) ret-=a[i];
    if (q[x].r>r) for (int i=r+1;i<=q[x].r;i++) ret+=a[i];
    if (q[x].r<r) for (int i=q[x].r+1;i<=r;i++) ret-=a[i];
    l=q[x].l;
    r=q[x].r;
    sol[q[x].idx]=ret;
}

int main()
{
    scanf ("%d%d", &n, &m);
    for (int i=1;i<=n;i++) scanf ("%d", &a[i]);
    init();
    for (int i=1;i<=m;i++)
    {
        int L, R;
        scanf ("%d%d", &L, &R);
        q[i]=*new Query(L, R, i);
    }

    sort (q+1, q+m+1, cmp);
    for (int i=q[1].l;i<=q[1].r;i++) sol[q[1].idx]+=a[i];
    l=q[1].l;
    r=q[1].r;
    for (int i=2;i<=m;i++) processQuery(i);
    for (int i=1;i<=m;i++) printf ("%d\n", sol[i]);

    return 0;
}