E 莫队, 为什么只能过80？

rt, 求调

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> PLL;

#define int ll
#define x first
#define y second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lep(i,a,b) for(int i=(a);i>=(b);i--)
#define sci(x) cin >> (x)
#define pli(x) cout << (x) << " ";
#define pll(x) cout << (x) << '\n';
#define yes cout << "Yes" << '\n';
#define no cout << "No" << '\n';
#define ls u << 1
#define rs u << 1 | 1
//cout << "? " << << ' ';
//printf("case:%d %d\n", );

struct fastmod {
    using u64 = uint64_t;
    using u128 = __uint128_t;
    int f, l; u64 m, d;
    fastmod(u64 d): d(d) {
        l = 64 - __builtin_clzll(d - 1);
        const u128 one = 1;
        u128 M = ((one << (64 + l)) + (one << l)) / d;
        if(M < (one << 64)) f = 1, m = M;
        else f = 0, m = M - (one << 64);
    }
    friend u64 operator/(u64 n, const fastmod &m) { // get n / d
        if (m.f) return u128(n) * m.m >> 64 >> m.l;
        else {
            u64 t = u128(n) * m.m >> 64;
            return (((n - t) >> 1) + t) >> (m.l - 1);
        }
    }
    friend u64 operator%(u64 n, const fastmod &m) { // get n % d
        return n - n / m * m.d;
    }
};

const int N = 1e6 + 10;
const ll p = 998244353;
ll n, m, c0, c1;

ll a[N], f[2], ans[N];
char s[N];

int len;
int get(int x) {return x / len;}

struct node
{
    int id, l, r;
    bool operator < (const node &V) const
    {
        if(get(l) != get(V.l)) return get(l) < get(V.l);
        return r > V.r;
    }
}q[N];

void add(ll x, ll &res)
{
    char c = s[x];
    if(c == '0')
    {
        c0++; (f[0] += x); f[0] %= p;
        (res += max(f[1] - c1 * x, c1 * x - f[1])) %= p;
    }
    else
    {
        c1++; (f[1] += x); f[1] %= p;
        (res += max(f[0] - c0 * x, c0 * x - f[0])) %= p;
    }
}

void del(ll x, ll &res)
{
    char c = s[x];
    if(c == '0')
    {
        c0--; (f[0] -= x) %= p;
        (res -= max(f[1] - c1 * x, c1 * x - f[1])) %= p;
    }
    else
    {
        c1--; (f[1] -= x) %= p;
        (res -= max(f[0] - c0 * x, c0 * x - f[0])) %= p;
    }
}

void solve()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s + 1;
    
    rep(i, 1, m)
    {
        int l, r;
        cin >> l >> r;
        q[i] = {i, l, r};
    }
    
    len = 1000;//pll(len)
    sort(q + 1, q + 1 + m);
    
    for(ll i = 0, j = 1, k = 1, res = 0; k <= m; k++)
    {
        ll l = q[k].l, r = q[k].r, id = q[k].id;
        while(i < r) add(++i, res); while(i > r) del(i--, res);
        while(j > l) add(--j, res); while(j < l) del(j++, res);
        res = (res % p + p) % p;
        ans[id] = res;
    }
    
    rep(i, 1, m) pll(ans[i]);
}

signed main()
{
    solve();
    return 0;
}