[luogu] P2709 小B的询问 莫队初步

前言

传送门: https://www.luogu.com.cn/problem/P2709

思想

暴力做法 对于每一个询问 我们都 for 一次 那么 最终复杂度是 O(nm)的

但是如果 我们用离线的方法 进行操作的话 那么可以降到 O n√N

Q :如何操作呢? A :

• 对访问的数组进行排序
• 用双指针进行移动区间

这么一看 我们明面上是优化了 询问的 操作

但是因为双指针的存在 如果 询问不是O（1）的 那么时间复杂度爆炸

CODE

#include 
using namespace std;
const int N  =5e4+10;
using ll = unsigned long long;
ll c[N],sum[N];

struct node
{
    ll l,r,num;
} q[N];


ll ans[N];
ll block;
ll res =0;

bool cmp(node a,node b)
{
    return (a.r/block) ==(b.r/block)?a.ln>>m>>k;
    block  = sqrt(n);
    
    for(ll i = 1; i>c[i];

    for(ll i=1; i>q[i].l>>q[i].r;
        q[i].num = i;
    }
    sort(q+1,q+1+m,cmp);
    
    int l=1,r=0;

    for(ll i = 1; i