竹子听

4月8日 莫队算法

int l = 0, r = 0, nowAns = 0;

inline void move(int pos, int sign) 

{// update nowAns}

void solve() 

{

    BLOCK_SIZE = int(ceil(pow(n, 0.5)));

      sort(querys, querys + m);

    for (int i = 0; i < m; ++i) {

        const query &q = querys[i];

        while (l > q.l) move(--l, 1);

        while (r < q.r) move(r++, 1);

        while (l < q.l) move(l++, -1);

        while (r > q.r) move(--r, -1);

        ans[q.id] = nowAns;

    }

}